Cuckoo hashing

Cuckoo hashing is a scheme in computer programming for resolving hash collisions among the values of hash functions in a table, and it gives worst-case constant lookup time. Its name comes from the behavior of some species of cuckoo, whose chick pushes the other eggs or young out of the nest when it hatches, a variation of brood parasitism. In the same way, inserting a new key into a cuckoo hash table may push an older key out to a different location in the table. The scheme is therefore a collision-resolution strategy for hash tables that trades a more involved insertion procedure for fast, predictable lookups.