Are you an EPFL student looking for a semester project?
Work with us on data science and visualisation projects, and deploy your project as an app on top of Graph Search.
Concept
Dynamic perfect hashing
Summary
In computer science, dynamic perfect hashing is a programming technique for resolving collisions in a hash table data structure.
While more memory-intensive than its hash table counterparts, this technique is useful for situations where fast queries, insertions, and deletions must be made on a large set of elements.
static hashing#FKS Hashing
The problem of optimal static hashing was first solved in general by Fredman, Komlós and Szemerédi. In their 1984 paper, they detail a two-tiered hash table scheme in which each bucket of the (first-level) hash table corresponds to a separate second-level hash table. Keys are hashed twice—the first hash value maps to a certain bucket in the first-level hash table; the second hash value gives the position of that entry in that bucket's second-level hash table. The second-level table is guaranteed to be collision-free (i.e. perfect hashing) upon construction. Consequently, the look-up cost is guaranteed to be O(1) in the worst-case.
In the static case, we are given a set with a total of x entries, each one with a unique key, ahead of time.
Fredman, Komlós and Szemerédi pick a first-level hash table with size buckets.
To construct, x entries are separated into s buckets by the top-level hashing function, where . Then for each bucket with k entries, a second-level table is allocated with 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) and stored alongside the hash table. If the hash function randomly selected creates a table with collisions, a new hash function is randomly selected until a collision-free table can be guaranteed. Finally, with the collision-free hash, the k entries are hashed into the second-level table.
The quadratic size of the space ensures that randomly creating a table with collisions is infrequent and independent of the size of k, providing linear amortized construction time.
Official source
About this result
This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.