Cuckoo Hashing Lookup

Cuckoo hashing stores each key in one of several possible table positions. In the common two hash version, a key can live at either $h_1(k)$ or $h_2(k)$. Lookup is therefore simple: compute both positions and check them.

The search operation is fast because it does not scan a bucket or probe a long sequence. The cost is moved mostly to insertion, where an existing key may be displaced and moved to its alternate position.

Problem

Given a cuckoo hash table and a key $k$, return the associated value if it exists.

Model

A two hash cuckoo table has:

• table $T$
• size $m$
• hash functions $h_1$ and $h_2$

A stored key $k$ must satisfy:

Algorithm

cuckoo_lookup(T, k):
    i = h1(k)
    if T[i] is occupied and T[i].key == k:
        return T[i].value

    j = h2(k)
    if T[j] is occupied and T[j].key == k:
        return T[j].value

    return NOT_FOUND

Example

Let:

• $m = 11$
• $h_1(k) = k \bmod 11$
• $h_2(k) = 1 + (k \bmod 10)$

For key $24$:

Lookup checks only positions 2 and 5.

So the value stored with key $24$ is returned.

Correctness

The cuckoo hashing invariant says that every stored key appears in one of its candidate positions. For the two hash version, these positions are exactly $h_1(k)$ and $h_2(k)$.

The lookup checks both candidate positions. If either contains $k$, it returns the associated value. If neither contains $k$, then the invariant implies that $k$ is not present in the table.

Complexity

For a fixed number of hash functions, lookup checks a fixed number of cells.

Space

The table stores entries directly. Practical cuckoo hash tables often keep the load factor below a chosen threshold to avoid insertion cycles and frequent rebuilds.

When to Use

Cuckoo hashing lookup is appropriate when:

• worst case constant lookup time matters
• lookups are much more frequent than insertions
• predictable memory access is useful
• the implementation can tolerate more complex insertion logic

It is less convenient when insertions are extremely frequent or when resizing and rehashing must be avoided.

Implementation

class CuckooHashTable:
    def __init__(self, m=16):
        self.m = m
        self.table = [None] * m

    def _h1(self, key):
        return hash(("h1", key)) % self.m

    def _h2(self, key):
        return hash(("h2", key)) % self.m

    def get(self, key):
        i = self._h1(key)
        if self.table[i] is not None:
            k, v = self.table[i]
            if k == key:
                return v

        j = self._h2(key)
        if self.table[j] is not None:
            k, v = self.table[j]
            if k == key:
                return v

        return None

type Entry[K comparable, V any] struct {
	Key   K
	Value V
	Used  bool
}

type CuckooHashTable[K comparable, V any] struct {
	Table []Entry[K, V]
	M     int
}

func (h *CuckooHashTable[K, V]) h1(key K) int {
	return int(uintptr(any(key))) % h.M
}

func (h *CuckooHashTable[K, V]) h2(key K) int {
	return (int(uintptr(any(key))) / h.M) % h.M
}

func (h *CuckooHashTable[K, V]) Get(key K) (V, bool) {
	i := h.h1(key)
	if h.Table[i].Used && h.Table[i].Key == key {
		return h.Table[i].Value, true
	}

	j := h.h2(key)
	if h.Table[j].Used && h.Table[j].Key == key {
		return h.Table[j].Value, true
	}

	var zero V
	return zero, false
}