# Cuckoo Hashing Lookup

# 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

```text id="0fu185"
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

```python id="zw0zjz"
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
```

```go id="zcs00m"
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
}
```