The Full Wiki

More info on Dynamic perfect hashing

Dynamic perfect hashing: Wikis

Advertisements

Note: Many of our articles have direct quotes from sources you can cite, within the Wikipedia article! This article doesn't yet, but we're working on it! See more info or our list of citable articles.

Encyclopedia

From Wikipedia, the free encyclopedia

Dynamic perfect hashing is a programming technique for resolving collisions in a hash table data structure [1].

In this method, the entries that hash to the same slot of the table are organized as separate second-level hash table. If there are k entries in this set, the second-level table is allocated with k2 slots, and its hash function is selected at random from a universal hash function set so that it is collision-free (i.e. a perfect hash function). Therefore, the lookup cost is guaranteed to be constant in the worst-case.

Although each second-level table requires quadratic space, if the keys inserted into the first-level hash table are uniformly distributed, the structure as a whole occupies expected O(n) space, since bucket sizes are small with high probability.

If a collision occurs during the insertion of a new entry, the bucket's second-level table is rebuilt with a different randomly-selected hash function. Because the load factor of the second-level table is kept low (1/k), rebuilding is infrequent, and the amortized cost of insertions is low.

References

  1. ^ Erik Demaine, Jeff Lind. 6.897: Advanced Data Structures. MIT Computer Science and Artificial Intelligence Laboratory. Spring 2003. http://courses.csail.mit.edu/6.897/spring03/scribe_notes/L2/lecture2.pdf

Advertisements






Got something to say? Make a comment.
Your name
Your email address
Message