Explore
For Enterprise
Join for Free
Log In

浏览
搜索
企业版
登录
免费加入

Chaining Scheme

Loading...

数据结构

加州大学圣地亚哥分校

4.7（2,273 个评分） | 97K 名学生已注册

课程 2（共 6 门，数据结构与算法专项课程）

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! Do you have technical problems? Write to us: coursera@hse.ru

查看授课大纲

您将学习的技能

Binary Search Tree, Priority Queue, Hash Table, Stack (Abstract Data Type), List

审阅

4.7（2,273 个评分）

5 stars
1,665 ratings
4 stars
491 ratings
3 stars
80 ratings
2 stars
14 ratings
1 star
23 ratings

VK

Jul 16, 2018

Amazing course.\n\nInteresting exercises help with learning and understanding of internal mechanisms basic data structures, how some of them work, the pros and cons of each.\n\nThanks!

SC

Feb 27, 2019

Perfect course for learning more about fundamental data structures, except for presentations on few difficult topics like splay trees, where explanations can be made more elaborate!

从本节课中

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
Michael Levin
Lecturer
Daniel M Kane
Assistant Professor
Neil Rhodes
Adjunct Faculty

脚本

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 致力于普及全世界最好的教育，它与全球一流大学和机构合作提供在线课程。

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

通过 Google Play 获取

Coursera
关于
管理团队
工作机会
目录
证书
MasterTrack™ 证书
学位
企业版
政府版
面向校园

社区
Learners
Partners
Developers
Beta Testers
Translators

连接
博客
Facebook
领英
Twitter
Instagram
YouTube
技术博客

更多
条款
隐私
帮助
内容访问
媒体
联系我们
目录
附属公司