Universal Family

Loading...

From the course by University of California San Diego

Data Structures

1470 ratings

University of California San Diego

Data Structures

1470 ratings

Course 2 of 6 in the Specialization Data Structures and Algorithms

A good algorithm usually comes together with a set of good data structures that allow the algorithm to manipulate the data efficiently. In this course, we consider the common data structures that are used in various computational problems. You will learn how these data structures are implemented in different programming languages and will practice implementing them in our programming assignments. This will help you to understand what is going on inside a particular built-in implementation of a data structure and what to expect from it. You will also learn typical use cases for these data structures. A few examples of questions that we are going to cover in this class are the following: 1. What is a good strategy of resizing a dynamic array? 2. How priority queues are implemented in C++, Java, and Python? 3. How to implement a hash table so that the amortized running time of all operations is O(1) on average? 4. What are good strategies to keep a binary tree balanced? You will also learn how services like Dropbox manage to upload some large files instantly and to save a lot of storage space!

From the lesson

Hash Tables

In this module you will learn about very powerful and widely used technique called hashing. Its applications include implementation of programming languages, file systems, pattern search, distributed key-value storage and many more. You will learn how to implement data structures to store and modify sets of objects and mappings from one type of objects to another one. You will see that naive implementations either consume huge amount of memory or are slow, and then you will learn to implement hash tables that use linear memory and work in O(1) on average! In the end, you will learn how hash functions are used in modern disrtibuted systems and how they are used to optimize storage of services like Dropbox, Google Drive and Yandex Disk!

Phone Book Problem4:16

Phone Book Problem - Continued6:49

Universal Family9:42

Hashing Integers9:17

Proof: Upper Bound for Chain Length (Optional)8:43

Proof: Universal Family for Integers (Optional)11:40

Hashing Strings9:33

Hashing Strings - Cardinality Fix7:00

Meet the Instructors

Alexander S. Kulikov
Visiting Professor
Department of Computer Science and Engineering
Michael Levin
Lecturer
Computer Science
Daniel M Kane
Assistant Professor
Department of Computer Science and Engineering / Department of Mathematics
Neil Rhodes
Adjunct Faculty
Computer Science and Engineering

Hi, in the previous video you learned that for any deterministic hash function,

there is a bad input on which it will have a lot of collisions.

And in this video, you will learn to solve that problem.

And the idea starts from, remember when you started QuickSort algorithm?

At first, you learned that it can work as slow as m squared time.

But then you learned that adding a random pivot to the partition procedure helps,

because now you know that QuickSort works on average in n log n time.

And in practice, it works usually faster than the other sorting algorithms.

So we want to use the same randomization idea here for hash functions.

But we already know that we cannot just use a random hash function because

it must be deterministic.

So instead, we will first create a whole set of hash functions

called a family of hash functions.

And we'll choose a random function from this family to use in our algorithm.

Not all families of hash functions are good, however, and so

we will need a concept of universal family of hash functions.

So let U be the universe, the set of all possible keys that we want to hash.

And then a set of hash functions denoted by calligraphic letter H,

set of functions from U to numbers between 0 and m- 1.

So hash functions with the same cardinality.

Such set is called a universal family if for

any two keys in the universe the probability of collision is small.

So, what does that mean?

Our hash function is a deterministic function, so for

any two keys it either has a collision for those two keys or not.

So, what does it mean that the probability of collision for

two different keys is small?

It means that if we look at our family calligraphic H,

then at most 1/m part of all hash functions in this family,

at most 1/m of them have a collision for these two different keys.

And if we select a random hash function from the family with

probability at least one minus one over m, which is very close to one,

there will be no collision for this hash function and these two keys.

And of course it is essential that the keys are different.

Because if keys are equal then any deterministic hash function will have

the same value on these two keys.

So, this collision property with small probability is only for

two different keys in the universe, but for

any two different keys in the universe this property should be satisfied.

It might seem that it is impossible but later you will learn how to build

a universal family of hash functions and practice.

So how are randomization idea works in practice.

One approach would be to just make one hash function which returns a random

value between 0 and m-1, each value with the same probability.

Then the probability of collision for any two keys is exactly 1/m.

But that is not a universal family.

Actually we cannot use this family at all because the hash function is

not deterministic and we can only use deterministic hash functions.

So instead, we need to have some set of hash functions

such that all the hash functions in the set are deterministic.

And then, we will select a random function h from this set of hash functions,

and we will use the same fixed function h throughout the whole algorithm.

So that we can correctly find all the objects that we store in the hash table,

for example.

So, there is a Lemma about running time of operations

with hash table if we use universal family.

If hash function h is chosen at random from a universal family

then on average the length of the longest chain in our hash table

will be bounded by O(1 + alpha), where alpha is the load factor.

Load factor is the ratio of number of keys that we store in our hash table

to the size of the hash table allocated.

Which is the same as the chronology of the hash functions

in the universal family that we use.

So, it makes sense.

If the load factor is small it means that we only store a few keys in a large

hash table, and so longest chain will be short.

But as our table gets filled up, the chains grow.

This Lemma says, however,

that if we chose a random function from a universal family they won't grow to much.

On average, the longest chain will still be of length just (1 + alpha).

And probably that is just a small number because alpha

is usually below one, you don't want to store more keys in

the hash table than the size of the hash table allocated.

So alpha will be below 1 most of the time and

then (1+ alpha) is just two, so this is a constant actually.

So, the corollary is that if h is chosen at random from the universal family,

then operations with hash table will run on average in a constant time.

Now the question is, how to choose the size of your hash table?

Of course, it control the amount of memory used with m which is your

chronology of the hash functions and which is equal to the size of the hash table.

But you also control the speed of the operations.

So ideally, in practice, you want your load factor alpha to be between 0.5 and 1.

You want it to be below 1 because otherwise you store too much keys in

the same hash table and then everything could becomes slow.

But also you don't want alpha to be too small because that way you will

waste a lot of memory.

If alpha is at least one-half, then you basically use linear memory

to store your n keys and your memory overhead is small.

And operations still run in time, O(1 + alpha) which is a constant time,

on average if alpha is between 0.5 and 1.

The question is what to do if you don't know in advance how

many keys you want to store in your hash table.

Of course, there is a solution to start with a very big hash table, so

that definitely all the keys will fit.

But this way you will waste a lot of memory.

So, what we can do is copy the idea you learned in the lesson about

dynamic arrays.

You start with a small hash table and

then you grow it organically as you put in more and more keys.

Basically, you resize the hash table and

make it twice bigger as soon as alpha becomes too large.

And then, you need to do what is called a rehash.

You need to copy all the keys from the current hash table to the new bigger hash

table.

And of course,

you will need a new hash function with twice the chronology to do that.

So here is the code which tries to keep loadfFactor below 0.9.

And 0.9 is just a number I selected, you could put 1 here or

0.8, that doesn't really matter.

So first we compute the current loadFactor, which is the ratio

of the number of keys stored in the table to the size of the hash table.

And if that loadFactor just became bigger than 0.9,

we create a new hash table of twice the size of our current hash table.

We also choose a new random hash function from the universal family

with twice the cardinality coresponding to the new hash table size.

And then we take each object from our current hash table, and

we insert it in the new hash table using the new hash function.

So we basically copy all the keys to the new hash table.

And then we substitute our current hash table with the bigger one and the current

hash function with the hash function corresponding to the new hash table.

That way, the loadFactor decreases roughly twice.

Because we added, probably just added one new element,

the loadFactor became just a little more than 0.9.

And then we increase the size of the hash table twice while the number of keys

stayed the same, so the loadFactor became roughly 0.45,

which is below 0.9, which is what we wanted.

So to achieve that, you need to call this procedure rehash after

each operation which inserts something in your hash table.

And it could work slowly when this happens because the rehash

procedure needs to copy all the keys from your current hash

table to the new big hash table, and that works in linear time.

But similarly to dynamic arrays, the amortized running time will still be

constant on average because their hash will happen only rarely.

So you reach a certain level of load factor and

you increase the size of our table twice.

And then it will take twice longer to again reach too high value of load factor.

And then you'll again increase your hash table twice.

So the more keys you put in, the longer it takes until the next rehash.

So their hashes will be really rare, and

that's why it won't influence your running time with operations, significantly.

Explore our Catalog

Join for free and get personalized recommendations, updates and offers.

Coursera provides universal access to the world’s best education, partnering with top universities and organizations to offer courses online.

© 2018 Coursera Inc. All rights reserved.

Download on the App Store

Get it on Google Play