Open Addressing (“Closed Hashing”)

Cuckoo Hashing

This builds upon Double Hashing, where in addition to using two independent hash functions $h_0,h_1$, we also use two tables $T_0,T_1$.

Main idea: An item with key $k$ can only be at $T_0[h_0(k)]$ or $T_1[h_1(k)]$.

• search and delete then take constant time.
• insert always initially puts a new item into $T_0[h_0(k)]$

If $T_0[h_0(k)]$ is occupied: “kick out” the other item, which we then attempt to re-insert into its alternate position $T_1[h_1(k)]$

Be careful

Cuckoo hashing may lead to a loop of “kicking out”. We detect this by aborting after too many attempts (doing at most $2n$ times).

In case of failure: rehash with a larger $M$ and new hash functions.

For an example, see the CS240 slides.