#Cuckoo Hashing: Worst-Case O(1)

The primary technical contribution of Pagh and Rodler was the displacement mechanism that gives the data structure its name. Cuckoo hashing uses two hash functions, $h_1$ and $h_2$, and two tables. A key $x$ is always stored in either $T_1[h_1(x)]$ or $T_2[h_2(x)]$. When a new key is inserted, it attempts to occupy its first possible location. If that slot is already taken by another key $y$, the new key 'kicks out' $y$. Key $y$ then moves to its own alternative location in the other table, potentially displacing yet another key. This sequence of moves continues until all keys find a home or a predetermined number of displacements is reached, at which point the tables are rehashed. This technical mechanism ensures that every lookup requires examining at most two specific memory locations.

The technical significance of Cuckoo Hashing lies in its achievement of $O(1)$ worst-case lookup time while maintaining near-optimal space usage. Unlike traditional hashing methods like chaining or linear probing, where lookups can degrade to $O(n)$ or $O(\log n)$ in the worst case, Cuckoo Hashing provides a rigid guarantee of constant-time performance. The authors proved that as long as the load factor of the table is kept below a certain threshold—typically 50%—the expected time for insertions is also $O(1)$. This finding revealed that the core difficulty of maintaining a fast dictionary is a function of the data structure's ability to self-organize through local displacements rather than global reordering.

Pagh and Rodler's work demonstrated that the complexity of computational systems can be minimized by limiting the number of possible states a piece of information can inhabit. The engineering choice to restrict each key to exactly two locations revealed that high-speed retrieval is possible without the need for complex collision resolution strategies. This realization remains the central theme of modern hardware-efficient data structures and the development of high-performance caches and networking equipment. It proved that the most robust way to manage a large-scale dictionary is to ensure that the path to any specific piece of data is both short and deterministic.