# Hopscotch Hashing Lookup

# Hopscotch Hashing Lookup

Hopscotch hashing maintains the invariant that each key resides within a small fixed distance from its home bucket. This distance is called the neighborhood size. Lookup only scans this bounded region, so it remains fast and cache friendly even at high load.

You search by computing the home index and checking a compact neighborhood using a bitmap or mask that records which nearby slots are occupied by keys belonging to that bucket.

## Problem

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

## Model

* Table $T$ of size $m$
* Hash function $h(k)$
* Neighborhood size $H$

Each bucket $i$ owns positions:

$$
[i, i + H - 1] \bmod m
$$

A bitmap at $T[i]$ marks which offsets in this range contain keys whose home is $i$.

## Algorithm

```text id="u2r9kx"
hopscotch_lookup(T, k):
    i = h(k)
    mask = T[i].bitmap

    for offset from 0 to H - 1:
        if mask has bit offset set:
            j = (i + offset) mod m
            if T[j].key == k:
                return T[j].value

    return NOT_FOUND
```

## Example

Let:

* $m = 10$
* $H = 4$
* $h(k) = k \bmod 10$

Suppose bucket 3 has bitmap:

```
bitmap = 1010
```

This means keys for bucket 3 appear at offsets 1 and 3:

| offset | index |
| -----: | ----: |
|      1 |     4 |
|      3 |     6 |

Search for a key with home bucket 3:

* compute $i = 3$
* check positions 4 and 6
* compare keys until match found or exhausted

## Correctness

Insertion ensures that every key stays within its home bucket neighborhood and that the bitmap correctly records its position. Lookup reads this bitmap and checks exactly those positions.

If the key exists, it must appear in one of these marked offsets. If none match, the key does not exist.

## Complexity

| case    | time   |
| ------- | ------ |
| worst   | $O(H)$ |
| average | $O(1)$ |

Since $H$ is a fixed constant, lookup runs in constant time.

## Space

$$
O(m)
$$

Each bucket stores a small bitmap in addition to the table entries.

## When to Use

Hopscotch hashing is appropriate when:

* high load factors are required
* predictable constant time lookup is needed
* cache locality is important
* concurrent or lock free variants are desired

It offers better locality and stability than linear probing while keeping lookup bounded.

## Implementation

```python id="q8t1zn"
class HopscotchHashTable:
    def __init__(self, m=16, H=4):
        self.m = m
        self.H = H
        self.table = [None] * m
        self.bitmap = [0] * m

    def _hash(self, key):
        return hash(key) % self.m

    def get(self, key):
        i = self._hash(key)
        mask = self.bitmap[i]

        for offset in range(self.H):
            if (mask >> offset) & 1:
                j = (i + offset) % self.m
                k, v = self.table[j]
                if k == key:
                    return v

        return None
```

```go id="n6y2wb"
type Entry[K comparable, V any] struct {
	Key   K
	Value V
}

type HopscotchHashTable[K comparable, V any] struct {
	Table  []Entry[K, V]
	Bitmap []uint32
	M      int
	H      int
}

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

func (h *HopscotchHashTable[K, V]) Get(key K) (V, bool) {
	i := h.hash(key)
	mask := h.Bitmap[i]

	for offset := 0; offset < h.H; offset++ {
		if (mask>>offset)&1 == 1 {
			j := (i + offset) % h.M
			if h.Table[j].Key == key {
				return h.Table[j].Value, true
			}
		}
	}

	var zero V
	return zero, false
}
```