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

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

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

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
}