Hashing Strings - Cardinality Fix

Loading...

From the course by University of California San Diego

Data Structures

1917 ratings

University of California San Diego

Data Structures

1917 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

>> Now we know of polynomial hash family or hashing strings.

But there's a problem with that family.

All the hash functions in that family have a cardinality of P,

where P is a very big prime number.

And what we want is the cardinality of hash functions

to be the same as the size of our hash table.

So, once a small cardinality.

So, we won't be able to use this binomial hashing family directly

in our hash tables.

We want to somehow fix the cardinality of the functions in the polynomial family.

And a good way to do that is the following.

We design a new complex transformation from strings to numbers,

from zero, to m minus one.

So, we select the cardinality m, and

we want to design a function from strings to numbers, between zero, and m minus one.

And, to that,

we first apply our random hash function from the polynomial family to the string.

And we get some integer number module P, and

then we can apply a random hash function from the universal family for

integers less than P, and get a number between 0 and m -1,

if we select it from universal family from cardinality m.

So, we now have a complex transformation which is two stage.

First, take a stream and

apply a random function from the polynomial family and then

apply a random function from the universal family for integers to the result.

And you get a number from zero to m-1 from the string.

Note that it is very important that we first select both random function from

the polynomial family and

the random function from the universal family of our integers.

And we fix them, and we use the same pair of functions for the whole algorithm.

And then, the whole function from string to integer number from between zero and

minus one is a deterministic hash function.

And it can be shown that the family of functions define this way

is a very good family.

It is not a universal family, but it is a very good family with [INAUDIBLE].

More specifically, if you take any two different strings S1 and

S2 of length at most L + 1, and you choose a cardinality m, and

you apply the process described to build a hash family from strings

of length at most L + 1 to integers numbers between zero and m minus 1.

Then the probability of collision for

random function from that family is at most 1 over m + L over p.

So, that is not an universal family because for

a universal family there shouldn't be any summon L over p the probability of

collision should be at most 1 over M.

But we can be very, very close to universal family because we can control P.

We can make P very big.

And then L over p will be very small.

And so, the probability of collision will be at most will 1 over m

plus some very small number.

And so, it will be either even less than 1 over m or very close to it.

So 1 mL hash, and then universal hash for

integers is a good construction of a family of hash functions.

A Corollary from the previous Lemma is that,

if we specifically select the prime number p to be bigger than m multiplied by L,

then the probability of collision will be, at most of 1 over m,

so it won't be less than 1 over m itself, but

it will be at most 1 over m multiplied by some constant.

Why is that?

Well, because if we rewrite 1 over m plus L over p by 1 over m + L over mL.

Then the second expression will be bigger because P is bigger than mL.

And then it is equal is 2 over m which is big O(1 over m).

So that way, we proved that combination of polynomial hashing with

universal hashing for integers, is a really good family of hash functions.

Now what if we take this new family of hash functions and

apply it to build a hash table?

Well, I say that for big enough prime number p,

we'll again have running time on average c=O(1 + a).

The length of the longest chain will be O(1 + a).

Where alpha is the lowest factor of our hash table.

And so, by wisely controlling this size of the hash table on the lowest factor

as we learned in the previous videos.

We can control the running time and the memory consumption.

Of course, computing the hash function itself on sum string s

is not a constant time operation, because the string can be very long.

And we need to look through the whole string to compute our hash function.

But in the case when the lengths of the strings in question are bounded,

like for example with names definitely there are no names longer than a few

hundred characters I think, so all they are bounded by some constant L.

And so computing hash function on the names, tags,

of course go off the length of the stream time, but

it is also we go off constant time because L is a constant itself, and

so we can implement a map from names to phone numbers using chaining,

using the newly created family of hash functions, which is complex.

It first applies polynomial hashing to the stream, to the name, and

then applies universal family or integers to the result.

So we can choose a random hash function from this two staged family.

And store our names, and phone numbers in the hash table, using this hash function.

In conclusion, you learned how to hash integers, and strings, really good, so

that probability of collision is small.

You learned that a phone book can be implemented as two maps,

as two hash tables, one from phone numbers to names, and another one back,

from names to phone numbers.

And if you manage to do that in such a way you don't waste too much memory where all

factors of your hash table is between one five and one, and search and

modification, on average, work in constant time, which is great.

And then the next lesson.

We'll learn to apply hash functions to different problems such as searching for

patterns in text.

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.

© 2019 Coursera Inc. All rights reserved.

Download on the App Store

Get it on Google Play