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:

$$ k \text{ is stored at } T[h_1(k)] \text{ or } T[h_2(k)] $$

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$:

$$ h_1(24) = 2 $$

$$ h_2(24) = 5 $$

Lookup checks only positions 2 and 5.

step	index	result
1	2	no match
2	5	match

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

case	time
worst	$O(1)$
average	$O(1)$

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

Space

$$ O(m) $$

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
}