Cuckoo Hashing

It is a probabilistic data structure.

Look-up (search) is \(O(1)\).
Insertion can be expensive \(O(n)\).
Lock-free parallel insertion and look-up. This is the paper. Rust implementation.

Questions

Let \(h_1\) and \(h_2\) be two hash functions.
Maintain two hash tables \(T_1\) and \(T_2\).
When inserting \(x\), compute \(h_1(x)\) and insert there if there is space.
- If there is no space in \(T_1\), repeat by computing \(h_2(x)\) and check \(T_{2}\).
- If there is no space in \(T_2\), insert it in \(T_1\) and remove \(y\) from \(T_1\).
- Repeat the process with \(y\)
Repeat the above process \(num\) times.
On failure, abort or increase the table size or the number of hash functions.