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 secondlevel hash table. If there are k entries in this set, the secondlevel table is allocated with k^{2} slots, and its hash function is selected at random from a universal hash function set so that it is collisionfree (i.e. a perfect hash function). Therefore, the lookup cost is guaranteed to be constant in the worstcase.
Although each secondlevel table requires quadratic space, if the keys inserted into the firstlevel 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 secondlevel table is rebuilt with a different randomlyselected hash function. Because the load factor of the secondlevel table is kept low (1/k), rebuilding is infrequent, and the amortized cost of insertions is low.
