Hashing Integers

Loading...

University of California San Diego의 강좌에서

Data Structures

2021개의 평가

University of California San Diego

Data Structures

2021개의 평가

Specialization Data Structures and Algorithms에서 6의 강좌 2

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

Hi, in the previous video,

you've learned the concept of universal family of hash functions and you learned

how to use it to make operations with your hash table really fast.

However, now we need to actually build a universal family and you will

start with a universal family for the most important object which is integer number.

Because any object on your computer is represented as a series of bits or

bytes, and so you can think of it as a sequence of integer numbers.

And so first, we need to learn to hash integers efficiently.

So we will build a universal family for hashing integers.

But we will look at our example with phone numbers because

we need to store contacts in our phone.

So first, we will consider only phone numbers up to length seven and for

example we will consider phone number 148-2567.

And again, we'll convert all of those phone numbers,

we want to start from integers from zero to the number consisting of seven nines.

And for example, our selected phone number

will convert to 1,482,567.

And then we will hash those integers to which we convert our phone numbers.

So to hash them, we will need to also choose a big prime number,

bigger than 10 to the power of 7, for

example, 10,000,019 is a suitable prime number.

And we will also need to choose the hash table size which is the same as

the chronology of the hash function that we need.

So now that we selected p and m, we are ready to define universal family for

integers between 0 and 10 to the power of 7 minus 1.

So the Lemma says that the following family of hash functions is

a universal family.

What is this family?

It is indexed by p, p is the prime number, 10,000,019, in this case that we choose.

And it also has parameters a and b, so those parameters are different for

different hash functions in these family.

Basically, if you fix a and b, you fix a hash function from

this hash functions family, calligraphic H with index p.

And x is the key, it is the integer number that we want to hash,

and it is required that x is less than p.

It is from 0 to p minus 1, or less than p minus 1, but

definitely, it is less than p.

So, to create a value of this

integer x with some hash function, we first make a linear transform of this x.

We multiply it by a, corresponding to this hash function, and add b,

corresponding to this hash function.

Then we take the result, modulo our big prime number p.

And after that, we again take the result modulo the size of our hash table or

the chronology of the hash functions that we need.

So all these hash functions indexed by a and b will have the same chronology m.

And the size of this hash family, what do you think it is?

Well, it is equal to b multiply by p minus 1, why is that?

Because there are p minus 1 variance for

a, and independently from that, there are p variance for b.

So the total number of pairs, a and b, is p multiplied by p minus 1,

that is the size of our universal family.

And the Lemma states that it really will be a universal family for

integers between 0 and p minus 1.

We will prove this Lemma in a separate, optional video.

And here, we'll look at an example of how this universal family works.

So, for example, we selected hash function corresponding to a = 34 and

b = 2, so this hash function h is h index by p, 34, and 2.

And we will compute the value of this hash function on number

1,482,567 because this integer

number corresponds to the phone number who we're interested in which is 148-2567.

Well, remember that p that we chose is a prime number 10,000,019.

So first, we multiply our number x by 34 and add 2,

and after that, we take the result modulo b,

modulo 10,000,019, and the result is 407,185.

Then we take this result and

take it again modulo 1,000, and the result is 185.

And so the value for our selected hash function on number x is 185.

And for any other number x, you would do the same, you would multiply x by 34,

add 2, take the result modulo b, then take the result modulo 1,000.

And so any value of our hash function is a number between 0 and 999 as we want.

And if we do different a and b, instead of 34 and 2,

we'll just multiply x by different a, add different b.

Take a modulo b, take the result modulo m, and get the value for our hash function.

So in the general case, when the phone numbers can be longer than seven,

we first define the maximum allowed length, L, of the phone number.

And again, convert all the phone numbers to integers which will derive from 0 to 10

to the power of L- 1, and then we'll hash those integers.

To hash those integers, we'll choose a sufficiently large number p,

p must be more than 10 to the power of L for the family to be universal.

Because otherwise, if we take some p less than 10 to the power of L,

there will exist two different integer numbers between 0 and

10 to the power of L- 1, which differ by exactly p.

And then, when we compute the value of some hash function on both those numbers

and we take linear transformation of those keys,

modulo b, the value of those transformations will be the same.

And then when we take, again, module m, the value again will be the same.

And that means that for any hash function from our family,

the value of its function on these two keys will be the same.

So there will be a collision for any hash function from the family, but

that contradicts the definition of universal family.

Because for a universal family and for two fixed different keys, no more than

1 over m part of all hash functions can have collision for these two keys.

And in our case, all hash functions have a collision for these two keys, so

this is definitely not a universal family.

So we must take p more than 10 to the power of L, and

in fact, that is sufficient.

Then, we choose hash table of size m, and

then we use our universal family, calligraphic H with index p.

We choose a random hash function from this universal family, and to choose a random

hash function from this family, we need to actually choose two numbers, a and b.

And a should be a random number between 1 and p-1,

and b should be an independent random number from 0 to p-1.

If we selected those two numbers, we define our hash function completed.

So now we know how to solve the problem of phone book

in the direction from phone numbers to names.

So we first define the longest allowed length of the phone number.

We convert all the phone numbers to integers from 0 to 10

to the power of L -1.

We choose a big prime number, bigger than 10 to the power of L.

We choose the size of the hash table that we want based on the techniques

you learned in the previous video and then you add

the context to your phone book as a hash table of size m.

Hashing them by a hash function randomly selected from

the universal family, calligraphic H with index p.

And that is the solution in the direction from phone numbers to names.

This solution will take bit of m memory, and you can control for m,

and it will work on average in constant time if you select m wisely

using the techniques from the previous video.

And now we also need to solve our phone book problem in the different direction,

from names to phone numbers.

And that we will do in the next video.

Coursera 카탈로그 살펴보기

무료로 참여해 맞춤화된 추천, 업데이트 및 제안을 받아보세요.

Coursera는 세계 최고의 교육에 대한 보편적인 접근 기회를 제공하며, 최고의 대학 및 기관들과 제휴하여 온라인 강좌를 제공합니다.

© 2019 Coursera Inc. All rights reserved.

앱스토어에서 다운로드하기

구글 플레이에서 받기