Question? Leave a message!




Open addressing

Open addressing
ECE 250 Algorithms and Data Structures Open addressing Douglas Wilhelm Harder, M.Math. LEL Department of Electrical and Computer Engineering University of Waterloo Waterloo, Ontario, Canada ece.uwaterloo.ca dwharderalumni.uwaterloo.ca © 20062013 by Douglas Wilhelm Harder. Some rights reserved.Open addressing 2 Outline Chained hash tables require special memory allocation – Can we create a hash table without significant memory allocation We will deal with collisions by storing collisions elsewhere – We will define an implicit rule which tells us where to look nextOpen addressing 3 Background Explicitly storing references to the next object due to a collision requires memory – Linked lists require a pointer to the next node – Scatter tables require a pointer to the next cell We will implicit rules which dictate where to look nextOpen addressing 4 Open Addressing Suppose an object hashes to bin 5 – If bin 5 is empty, we can copy the object into that entry Open addressing 5 Open Addressing Suppose, however, another object hashes to bin 5 – Without a linked list, we cannot store the object in that bin Open addressing 6 Open Addressing We could have a rule which says: – Look in the next bin to see if it is occupied – Such a rule is implicit—we do not follow an explicit linkOpen addressing 7 Open Addressing The rule must be general enough to deal with the fact that the next cell could also be occupied – For example, continue searching until the first empty bin is found – The rule must be simple to follow—i.e., fastOpen addressing 8 Open Addressing We could then store the object in the next location – Problem: we can only store as many objects as there are entries in the array: the load factor l ≤ 1Open addressing 9 Open Addressing Of course, whatever rule we use in placing an object must also be used when searching for or removing objectsOpen addressing 10 Open Addressing Recall, however, that our goal is Q(1) access times – We cannot, on average, be forced to access too many binsOpen addressing 11 Open Addressing There are numerous strategies for defining the order in which the bins should be searched: – Linear probing – Quadratic probing – Double hashing There are many alternate strategies, as well: – Last come, first served • Always place the object into the bin moving what may be there already – Cuckoo hashingOpen addressing 12 Summary This short topic introduces the concept of open addressing – Use a predefined sequence of bins which should be searched – We need a fast rule that can be easily followed – We must ensure that we are not making too many searches – The load factor will never be greater than oneOpen addressing 13 References Wikipedia, http://en.wikipedia.org/wiki/Hashfunction 1 Cormen, Leiserson, and Rivest, Introduction to Algorithms, McGraw Hill, 1990. rd 2 Weiss, Data Structures and Algorithm Analysis in C++, 3 Ed., Addison Wesley. These slides are provided for the ECE 250 Algorithms and Data Structures course. The material in it reflects Douglas W.Harder’s best judgment in light of the information available to him at the time of preparation. Any reliance on these course slides by any party for any other purpose are the responsibility of such parties. Douglas W. Harder accepts no responsibility for damages, if any, suffered by any party as a result of decisions made or actions based on these course slides for any other purpose than that for which it was intended.
sharer
Presentations
Free
Document Information
Category:
Presentations
User Name:
Dr.SethPatton
User Type:
Teacher
Country:
United Kingdom
Uploaded Date:
22-07-2017