Explore
For Enterprise
Join for Free
Log In

Rutgers University
Become a skilled supply chain leader in 4 months
Earn the Supply Chain Excellence MasterTrack™ Certificate from a top-ranked business school.
University of Illinois
Are you a working parent looking to grow your data science career?
Join our special webinar on 1/29 to hear from Illinois MCS-DS students about balancing parenting with school.

浏览 Coursera 的全部课程

浏览
顶级课程
企业版
登录
免费加入

Chaining Scheme

Loading...

数据结构

加州大学圣地亚哥分校

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

课程 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,456 个评分）

5 stars
1,810 ratings
4 stars
519 ratings
3 stars
88 ratings
2 stars
15 ratings
1 star
24 ratings

AS

Sep 19, 2019

The best data structures course that I have taken!\n\nThe complex topics are made simpler at the expense of teaching style that allowed me to make it applicable in a real world situations.

AS

Nov 23, 2019

The lectures and the reading material were great. The assignments are challenging and require thought before attempting. The forums were really useful when I got stuck with the assignments

从本节课中

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

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

社区

学生
合作伙伴
开发者
Beta 测试人员
专业译员
博客
技术博客

更多

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

随时随地学习

关注我们

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