Explore
For Enterprise
Join for Free
Log In

Blättern
Suche
Für Unternehmen
Anmelden
Kostenlose Teilnahme

Chaining Implementation and Analysis

Loading...

Datenstrukturen

University of California San Diego

4.7 (2,213 Bewertungen) | 95K Teilnehmer angemeldet

Kurs 2 von 6 in Datenstrukturen und Algorithmen Spezialisierung

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

Lehrplan anzeigen

Kompetenzen, die Sie erwerben

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

Bewertungen

4.7 (2,213 Bewertungen)

5 stars
1,623 ratings
4 stars
478 ratings
3 stars
77 ratings
2 stars
13 ratings
1 star
22 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!

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

Unterrichtet von

Alexander S. Kulikov
Visiting Professor
Michael Levin
Lecturer
Daniel M Kane
Assistant Professor
Neil Rhodes
Adjunct Faculty

Skript

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.

Produkte

Zertifikate
Katalog
MasterTrack™-Zertifikate
Abschlüsse

Enterprise
Regierung

Community

Kursteilnehmer
Entwickler
Beta-Tester
Übersetzer
Tech-Blog

Coursera

Info
Jobs
Partner
Presse
Blog
Partnerunternehmen
Kontakt
Hilfe

© 2019 Coursera Inc. All rights reserved.

Datenschutz
Nutzungsbedingungen/AGB
Barrierefreiheit
Verzeichnis