Cuckoo hashing utilizes hashing with the power of not only one choice but two choices.

Array A of size m.

two random hash functions g h u -> m

Try to insert x into array g x.

agx potentially kicking out the item that is already in the choices. There is random hash functions. When x is to be inserted. Insert G of X.

If the sequence of item moves, go on for less than log n steps. We give up. We pick a new g of h. Rebuild the entire data structure.

Claim E of time insert is less than or equal to O (i) a constant.

Citation Youtube Harvard University

The Cukoo graph has m vertices, one per cell of A. For each x we connect g of x h of h.

Insert x. x2 x3 and x4 to create a path.