Cuckoo Hashing

One of the most fundamental data-structure problems is the dictionary problem: given a set $D$ of words, you want to quickly decide whether any query string $q$ belongs to $D$. Hashing is a classic solution. You design a fast, deterministic hash function $h : \Sigma^* \to [0..n-1]$ that maps every string into the integer range $\{0, 1, \dots, n-1\}$, allocate an empty table $T$ of size $n$, and for each word $w \in D$ set $T[h(w)] = w$. To answer a query $q$ you compute $h(q)$ and check whether $T[h(q)] = q$.

The catch is collisions: two different words may hash to the same slot (recall the birthday paradox — in a class of 24 pupils there is already more than a 50% chance that two share a birthday). On average you can only store about $\sqrt{n}$ words before a collision occurs, which wastes a lot of space.

Cuckoo hashing is a stronger variant that uses two hash functions $h_1$ and $h_2$, so each word has two candidate slots. To answer a query $q$ you compute both $h_1(q)$ and $h_2(q)$ and report that $q \in D$ if $T[h_1(q)] = q$ or $T[h_2(q)] = q$.

The name comes from how the table is built. Start with an empty table and insert the words one by one. To insert a word $d$:

• If $T[h_1(d)]$ is free, set $T[h_1(d)] = d$.
• Otherwise, if $T[h_2(d)]$ is free, set $T[h_2(d)] = d$.
• Otherwise both slots are occupied. Like a cuckoo pushing other birds' eggs out of the nest, evict the word $r$ currently in $T[h_1(d)]$, set $T[h_1(d)] = d$, and reinsert $r$ into its alternative slot. If that slot is also occupied, evict its word and relocate it in the same way, and so on.

This relocation chain may never terminate. If it loops forever, the table has to be rebuilt with different hash functions. Fortunately, with high probability this does not happen as long as $D$ contains at most $n/2$ words.

Given, for every word, the two slots it hashes to, decide whether all words can be inserted in the given order without falling into an infinite relocation loop.

(Cuckoo hashing was proposed by R. Pagh and F. F. Rödler in 2001.)

The first line contains a single integer $t$ ($1 \le t \le 50$), the number of test cases.

Each test case starts with a line containing two integers $m$ and $n$ ($1 \le m \le n \le 10000$), where $m$ is the number of words in the dictionary and $n$ is the size of the hash table. Each of the next $m$ lines describes one word $d_i$ (in insertion order) by two integers $h_1(d_i)$ and $h_2(d_i)$ ($0 \le h_1(d_i), h_2(d_i) < n$), its two hash values. The two values may be equal.

For each test case, print a single line: successful hashing if all words can be inserted in the given order, or rehash necessary if it is impossible.