Dynamic perfect hashing

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

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 k² slots, and its hash function is selected at random from a universal hash function set so that its 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 insertion of a new item, the bucket's 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.