Explore
For Enterprise
Join for Free
Log In

Kunst und Geisteswissenschaften
Wirtschaft
Informatik
Datenverarbeitung
Informationstechnologie
Gesundheit
Mathematik und Logik
Persönliche Entwicklung
Physik und Ingenieurwesen
Sozialwissenschaften
Sprachen lernen
學位
證書

瀏覽 Coursera 的全部課程

瀏覽
搜索
企業版
登錄
免費加入

Chaining Implementation and Analysis

Loading...

Datenstrukturen

University of California San Diego

4.7（2,104 個評分） | 91K 名學生已註冊

課程 1（共 6 門，Datenstrukturen und Algorithmen 專項課程）

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!

查看授課大綱

您將學習的技能

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

審閱

4.7（2,104 個評分）

5 stars
1,548 ratings
4 stars
452 ratings
3 stars
72 ratings
2 stars
12 ratings
1 star
20 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

腳本

How to implement this in code?

Well, let's just assume that we have a hash function h from the set of all

possible objects S to the set of numbers from 0 to m-1.

And let us denote by O and O prime objects from set S and

by v and v prime values from set big V.

And let us have an array A, which consists of m lists,

where m is the cardinality of the hash function.

And those lists we'll call also chains, and

those chains consist of pairs of objects O and values v.

Now let us implement the first method, HasKey, which would return whether

there is an entry in our table or in our map for the object O.

First, we compute the value of hash function on the object O.

We'll look at the corresponding cell in the array A, and

we'll take the list out from there.

Then we go through this list and when we go through it,

we'll look at pairs O prime, v prime that are elements of this list.

If for some pair O prime is the same as the object O for

which we are looking, we return true because it means that there is an entry in

our map corresponding to the object O.

If we don't find any corresponding pair in the list,

return false because that means there is no such object and

there is no key corresponding to this object in our map.

Because it only could be in the list corresponding to the cell with

number h of O and we didn't find it there.

Next let's implement method Get,

which should return the value corresponding to object O if there is one.

Otherwise, return some special value telling us that there is no

entry corresponding to object O.

Again, we start with computing value of hash function on object O and

looking at the cell number h of O in the array A and

take the list, which is stored in that cell.

Then we again go through all the pairs in that list L,

pairs O prime, v prime, and if for some of the pairs,

O prime is the same as the object O for which we are looking, then we'll return

the corresponding value v prime as the value corresponding to that object O.

If we go through the whole list and we don't find corresponding player,

we'll return special value n/a, which means that there is no

value corresponding to object O in our map.

Why is that?

Because if there was some value, it has to be in the list corresponding to

the cell number h of O because that's the way we store our chains,

and if we didn't find it there, then there is no entry corresponding to the object O.

Now the last, most interesting method, Set, which accepts two arguments,

object O and the value v, which we need to set corresponding to this object.

We need to either rewrite this value if there was already an entry corresponding

to the object O with different value.

Or we need to create a new value in the map corresponding to the object O if

it didn't happen to be in the map before.

We again start with computing the hash function on the object O and looking at

the corresponding cell in the array A and we'll take the list, we just start there.

Now we go through all the pairs p in that list L, and

each pair p contains two fields, first field is p.O,

which is the object of that pair, and p.v, which is the value of that pair.

If for some pair, we see that the object of that pair is the same

as object O for which we need to set the value v,

then we just assign the value to the p.v, the new value.

We will write the old value with the new value for that object O and

then we return, we exit from the function.

Because we've already done everything we need.

If we go through the whole list and

we don't find any pair corresponding to our object O, it means that there was no

entry in our map corresponding to the object O previously.

And it means that we need to add a new pair to our list, and

we just append a new pair containing object O and

value v to the list L, corresponding to the cell number h of O.

Now let's look at the SM project of the chaining scheme.

The first lemma says that if c is the length of the longest chain in A,

then the running time of all three methods is theta of c+1.

First, if we look at the list corresponding to some object O,

the list in the cell number h of O,

then the length of this list can be c, this can be the longest list itself.

And if object O is not in this list and would call some of the methods for

this object, we will need to scan the full list so

we'll need to scan all c items in this list.

Also, if c is 0 so that our map is empty, our array A is comprised of m after this.

We still need constant time to check that.

So that's why c+1 and not just c.

Another lemma is talking about memory consumption.

So let n be the number of different keys that we're storing in the map and

m is the cardinality of the hash function.

Then the memory consumption is theta of n+m.

That is very easy to prove.

First, we need to store n pairs of objects and corresponding values in the map.

That's where we get theta of n.

And we get additional theta of m to store the array of m lists.

Although those lists can be empty, we'll still need to use

some memory to store the pointers to the heads of those lists,

and that's why memory consumption is theta of n+m.

探索我們的目錄

免費加入並獲得個性化推薦、更新和優惠。

Coursera provides universal access to the world’s best education, partnering with top universities and organizations to offer courses online.

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

通過 App Store 下載

通過 Google Play 獲取

Coursera
關於
管理團隊
工作機會
目錄
證書
MasterTrack™ 證書
學位
企業版
政府版

社區
Learners
Partners
Developers
Beta Testers
Translators

連接
博客
Facebook
領英
Twitter
Instagram
YouTube
技術博客

更多
條款
隱私
幫助
內容訪問
媒體
聯繫我們
目錄
附屬公司