Hash tables are usually discussed with chaining or linear probing, both of which have O(1) average lookups. Cuckoo hashing is the answer when an interviewer asks: "Can you guarantee constant-time lookups in the worst case?"
Use two tables T1 and T2 and two independent hash functions h1 and h2. Every key lives in exactly one of two possible slots: T1[h1(k)] or T2[h2(k)]. A lookup checks those two slots and nothing else, so it is O(1) in the worst case.
def insert(k):
for _ in range(MAX_KICKS):
k, T1[h1(k)] = T1[h1(k)], k # place k, evict occupant
if k is None: return
k, T2[h2(k)] = T2[h2(k)], k # evicted key tries its other slot
if k is None: return
rehash_with_new_functions(); insert(k)
Like a cuckoo chick pushing eggs out of a nest, the new key takes its slot and the previous occupant moves to its alternative location, possibly evicting someone else.
Eviction chains can form a cycle. Implementations cap the number of kicks (often around log n) and, if reached, pick new hash functions and rebuild. With two tables the load factor must stay below about 50% for inserts to succeed with high probability; using buckets of 4 slots pushes usable load above 90%.
Network switches and packet classifiers like it for predictable lookup time. Cuckoo filters store short fingerprints in the same layout and support deletion, which plain Bloom filters do not, a good point to bring up in a system design round about membership tests.
Lead with the guarantee (two possible homes per key), then the eviction loop, then the failure case and the rehash. Interviewers care most that you know why the load factor limit exists.
Disclosure: I help build Linkjob AI, a real-time interview copilot. These notes are general study material.