Chaining Implementation and Analysis

Loading...

Aus dem Kurs von University of California San Diego

Data Structures

1956 Bewertungen

University of California San Diego

Data Structures

1956 Bewertungen

Kurs 2 von 6 in Specialization Data Structures and Algorithms

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!

Aus der Unterrichtseinheit

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

Treffen Sie die Kursleiter

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

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.

Durchsuchen Sie unseren Katalog

Melden Sie sich kostenlos an und erhalten Sie individuelle Empfehlungen, Aktualisierungen und Angebote.

Coursera arbeitet mit erstklassigen Universitäten und Organisationen zusammen, um Online-Kurse anzubieten und dadurch universellen Zugriff auf die weltweit beste Ausbildung zu ermöglichen.

© 2019 Coursera Inc. Alle Rechte vorbehalten.

Aus dem App Store herunterladen

Erhältlich bei Google Play