Phone Book Problem - Continued

Loading...

來自 University of California San Diego 的課程

Data Structures

1917 個評分

University of California San Diego

Data Structures

1917 個評分

課程 2（共 6 門，Specialization 数据结构与算法）

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!

從本節課中

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

與講師見面

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

Another scheme that we know from the previous lesson is chaining.

To use that we first select the hash function with some cardinality m,

then we create an array name again of size m.

But instead of storing the names themselves in the array,

we store chains or lists.

And in these lists, we'll store both names and the phone numbers.

And to determine where to put name and phone number, we first convert the phone

number to integer, then we'll apply hash function to it and get a hash value.

And put both name and

phone number in the chain corresponding to the cell with such index.

Here is how it looks like.

For example, we have a contact of Steve and his phone number is 223-23-23.

We first convert it to the number 2 million and a few thousand, and

then we compute the hash value of this integer number and it turns out to be 1.

Then we put both Steve's name and his phone number in

the chain corresponding to the cell number 1 in our array Name.

Then we do the same for Natalie and her phone number.

And it turns out that the hash value of the integer corresponding to her phone

number is 6, so we put her contact in the 6th cell.

And then we do the same for Sasha, and

the hash value of his phone number turns out again to be 1.

So Sasha gets in the same cell as Steve.

There are the following parameters of the chaining scheme.

First, n is the total number of phone numbers stored in our phone book.

m is the cardinality of the selected hash function,

which is the same as the size of our area name, which works as a hash table.

c is the length of the longest chain in our hash table.

We use big O(n + m) memory to store the phone book.

And also alpha, which is n/m,

the number of phone numbers stored divided by the size of the hash table,

which measures how filled up is our hash table, is called the load factor.

And we will need it later.

So we know that the operations with a hash table run in time big O(c + 1).

And so we want both small m to use fewer memory and small c so

that everything works faster.

And here's a good example.

We see a hash table of size 8 with a few chains and we see that the length of

the chains are relatively the same, with the longest chain being of length just 2.

So everything will work fast.

And here's a bad example.

When we again have hash table of size 8, but all the keys fell in the same cell 1.

And they make up a very long chain of size m, in this case, it is 8.

So this is what we want to avoid.

Let's try a few hash functions that come to our mind.

First, let's select cardinality of 1000.

And choose the first three digits as the hash value for the phone number.

For example for this phone number it will be 800,

because the first three digits are 800.

However there is a problem with this hash function because the area code, which

is the first three digits will be the same for many, many people in your phone book.

Probably because they live In the same city with you, and so

they will have the same area code.

And the hash values for their phone numbers will be the same, and

they will make up a very long chain.

Another idea is to take the last digits, again the cardinality is 1,000, and

we take the last three digits as the hash value.

So for this number, it will be 567.

But still, there can be a problem if there are many phone numbers in your phone book,

which, for example, end in three zeros, or

in some other combinations of three digits.

So, another approach is to just select a random value as the hash function,

a random number between 0 and 999.

And then the distribution of hash values will be very good,

probably the longest chain will be short.

However, we cannot use such hash function actually because

when we'll call the hash function again to look up the phone number we

stored in the phone book we won't find it because we are looking in the wrong place.

Because the value of the hash function changed because it's not deterministic.

So we learned that the hash function must be deterministic, that is return

the same value if given the same phone number as the input each time.

So good hash functions are deterministic.

Fast to compute because we do that every time we need to store something or

modify something or find something in our hash table.

And they should distribute the keys well in different cells and

have few collisions.

Unfortunately, there is no universal hash function.

Most specifically, the Lemma says that the number of all possible keys,

the sizes of the universe with keys is large enough.

Much larger than the cardinality of the hash function that we want to use

to save memory.

Then for any specific deterministic hash function there is a bad input,

which results in many, many collisions.

Why is that?

Well, let's look at the universe U and select some cardinality for example, 3.

Then, our universe will be divided into three groups.

All the keys that have hash value 0, all the keys that have hash value 1,

and all the keys that have hash value of 2.

Now, let's select the biggest of those groups.

In this case, it's the group with hash value of 1.

This group will definitely be of size at least one-third of the whole universe and

it can be even bigger.

In this case for example, around 42%.

And then, if we take all these keys or a significant part of

these keys as an input, they will have the same hash value.

And so, all of them will make collisions between themselves and they will

form a very long chain in the hash table and everything will work very slowly.

Of course, if we change the hash function for this particular input,

it will distribute the keys more uniformly among hash values.

But for this particular hash function, this will be a bad input.

And for any specific hash function with any cardinality,

we'll be able to select a bad input this way.

And in the next video, you will learn how to solve this problem.

探索我們的目錄

免費加入並獲得個性化推薦、更新和優惠。

Coursera 致力於普及全世界最好的教育，它與全球一流大學和機構合作提供在線課程。

© 2019 Coursera Inc. 保留所有權利。

通過 App Store 下載

通過 Google Play 獲取