Cuckoo Hashing

overview

Summary

cuckoo_hashing is a hash table scheme using two_hash_functions and often two_tables. Each key has two possible positions. On insert, place the key; if occupied, eviction relocates it to its alternate position. This repeats until a spot is free or a cycle happens. When cycles appear, use a small stash or trigger rehashing. Lookups check both positions with constant_lookup_time. Typical load_factor is high but stays below 1.