Hash Functions

Loading...

来自 University of California San Diego 的课程

Data Structures

1517 个评分

University of California San Diego

Data Structures

1517 个评分

课程 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!

Applications of Hashing2:37

Analysing Service Access Logs7:52

Direct Addressing7:21

List-based Mapping8:10

Hash Functions3:18

Chaining Scheme6:08

Chaining Implementation and Analysis5:59

Hash Tables6:27

与讲师见面

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 this video, you will learn what a hash function is,

how could we apply it to solve our problem with IP addresses, and

why it is not straightforward to make it to work.

Remember the direct addressing approach worked particularly fast, but

it used a lot of memory that's because it encoded IP with numbers and

those numbers were sometimes huge.

So we had to create an array of size 2 to the power of 32 just to store all

those numbers.

What if we could encode our IP addresses with smaller numbers,

for example, numbers from 0 to 999?

We'll still need the code for different IP addresses, which are active currently

to be different because we want a separate counter for each IP in our solution.

Let's define a hash function.

So if you have universal object S for example.

A set of all IP addresses or a set of all files stored on your computer or a set

of all words or cures in the programming language, so that is our universe.

And we will call it a set S.

And now we want to encode each object from that universe with a small number.

A number from 0 to m- 1 where m is a positive integer number.

While any function, which encodes some object from S

as a number from 0 to m- 1, is called a hash function.

And m is called the cardinality of hash function h.

So what are the desirable properties of the hash function in our problem?

First, h should be fast to compute because we need to encode some object for

each query.

Second, we want different values for different objects

because we want a separate counter for each IP address in our problem from them.

And also, we want to use direct addressing scheme because it was very fast,

but we want to use a direct addressing scheme with a small amount of memory.

And it's only logical to use in this case direct addressing scheme with O(m)

memories.

Just create an area a of size m, and then encode each ID with some value from

0 to m- 1, and store the corresponding counter In the cell of this array.

The problem is that we want small cardinality m and it won't work

if m is smaller than the number of different objects in the universe.

Because if we have for example 25 object in the universe and

m is only 10, then at least two objects will have the same code from

0 to 9 because there are only 10 different codes and there are 25 different objects.

So that won't work for all possible universes and for small m.

In this situation, when the values of the hash function are the same, but

the objects which are being encoded are different, is called a collision.

So collisions cause us problems.

Because of collisions, we cannot just directly

apply the scheme called direct addressing with O(m) memory.

And in the next lecture, we will see how to overcome this problem.

探索我们的目录

免费加入并获得个性化推荐、更新和优惠。

Coursera 致力于普及全世界最好的教育，它与全球一流大学和机构合作提供在线课程。

© 2018 Coursera Inc. 保留所有权利。

通过 App Store 下载

通过 Google Play 获取