Chaining Scheme

Loading...

来自 University of California San Diego 的课程

Data Structures

1563 个评分

University of California San Diego

Data Structures

1563 个评分

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

In this video,

we will study chaining, which is one of the most frequently used techniques for

using hashing to store mappings from one type of object to another type of object.

So, let us define a map.

We often want to store mapping from some objects to some other object.

For example, I'm mapping from IP addresses to integer numbers.

Or from filenames to the physical location of those files on the disk.

From student ID to the name of the student.

Or from contact name in your phone book to the contact phone number.

The general definition of a map from set of objects S

to the set of values V is a data structure which has three methods.

HasKey, which tells us whether there is an entry

in the map corresponding to object O from set S.

Method Get, which returns to us the value corresponding to the object O,

if there is one.

If there is no such value, it returns a special value

telling us that there is no entry corresponding to this object O in the map.

And the last method is set, the most important method,

which sets the value corresponding to object O to V.

Here, objects O are all from the set S and values V are from the set big V.

We want to implement a map, using hash function, and

some combination of ideas from direct addressing, and

least based solution from one of the previous videos.

So what we'll do is called chaining.

We will create an array of size m, where m is the cardinality of the hash function,

and in this case, let m be eight.

This won't be an array of integers, though.

This will be an array of lists.

So in each cell of this array, we will store a list.

And this will be a list of pairs.

And each pair will consist of an object, O.

And a value V, corresponding to this object.

Let's look at an example.

For example, our objects are IP addresses, and

the values are the corresponding counters.

As in our initial problem about web service, and IP addresses of its class.

Now we're processing the log, and we see an IP address, starting with 173.

And it so happens that the value of hash function on this IP address is four.

Then, we look at the cell four, the list there is now empty.

But we append, in the pair of our IP address.

And the corresponding counter one, to this list.

The value is one because this is the first time that we encounter this AB.

Now we'll look at the next IP in the log.

It starts with 69, and the hash value for this IP is one.

So we'll look at the cell number one, and

we append the pair of this IP address and the corresponding counter one to the list.

Again the counter is one because this is the first time we see this IP address.

Now it looks at the next IP address in the log and we see that it again starts

with 173 and actually it coincides with the first IP that we've already seen.

And the hash value is again four, because hash function is deterministic,

it always returns the same number for same object.

So we'll look at the cell number four, we'll look through the whole list and

we find out that there is already a pair containing this IP address as the key.

So instead of appending this IP address again to the list,

we will increase the value of the counter

by one because this is the second time we've seen our IP address.

Of course in the interface of a general map, there is no method for

incrementing a counter, there is a method to set so we will need to first use

method get to get the value corresponding to this IP address, we will get one.

We will then increase it by one ourselves, get two.

And then we will call set for this IP address and value two.

And it will just rewrite the value from one to two in this list element.

Then, we'll look at the next line in our log, and

we see that this is IP starting from 91.

And it so happens that the hash value for this IP address, again,

is four, although this is a different IP address.

And that has to happen at some point, because there are many,

many different IP addresses, and only eight entries in our array.

So what do we do?

If we look at the cell number four, there is a non-empty list there.

We go through the whole list, but

we see that our new IP address starting from 91 is not in the list.

So we add our new IP address to the end of this list

along with the corresponding counter of one.

And these two IP addresses in the list for

cell number four already make a chain together.

And if we go further and further through the log, and we add some

IP addresses to this map, some of the chains will become longer.

If where some point we'll need to remove

some IP address from the list we can do that and the chain can become shorter.

But anyway, you see the general structure that a chain maybe empty,

maybe non-empty, starts in any cell of the array.

The array size is m, which is equal to the cardinality of the hash function.

And for each such cell we store a list with all the IP addresses which

occurred before and which have hash value the same as the number of the cell.

探索我们的目录

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

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

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

通过 App Store 下载

通过 Google Play 获取