Hash Tables and Hash Indexes¶

Why storage engineers care about hash tables¶

Hash tables are everywhere inside a storage engine even when the on-disk index is a tree: the buffer pool's page table, the block cache, the table cache, lock managers, the in-memory key directory of hash-indexed stores like Bitcask, and hash joins in query engines. Their performance is dominated by memory layout, not by Big-O — all designs are O(1) on average, and they differ by how many cache misses a lookup costs and how they behave when full. This page covers in-memory designs first, then hash indexes on disk.

Hash functions¶

A hash table needs a function that spreads keys uniformly over buckets and is fast. Two failure modes:

• Poor mixing. A power-of-two table — the fast choice, where the bucket is hash & mask — uses only the low bits of the hash. With a weak hash (the identity, as several languages' standard libraries use for integers), keys that are multiples of 4096 (page offsets, aligned addresses, IDs allocated in strides) all land in the same few buckets. A finalizer that mixes every input bit into the low bits fixes it; the splitmix64 steps in the code below cost a few cycles. Measured below: 1,562-slot probe runs with the identity, 14 with splitmix64. Go's built-in map hashes with a strong, per-process seeded function (AES-based where the CPU supports it), so it does not have this problem.
• Adversarial keys. If attackers choose keys (HTTP headers, user IDs), a predictable hash lets them send thousands of colliding keys and turn lookups into O(n) — hash flooding. Use a keyed hash (SipHash, or a per-process random seed) for externally supplied keys.

Collision resolution: chaining vs. open addressing¶

Separate chaining stores a linked list of nodes per bucket. Every element is a separate heap allocation, and a lookup costs a bucket-array access plus at least one pointer chase: typically two or more cache misses. It is what you get when an API promises that references to elements stay valid across rehashing (which rules out moving elements); Redis's main keyspace uses it.

Open addressing stores entries directly in one array. On a collision, it probes other slots in a fixed sequence. A lookup usually touches one or two adjacent cache lines. This is why modern general-purpose tables — Abseil's flat_hash_map, Rust's HashMap, and Go's built-in map since Go 1.24 (a Swiss table, see Memory Layout of Go Values) — use open addressing. One consequence visible in Go: map entries are not addressable (&m[k] does not compile), because growth moves them.

Load factor¶

Load factor α = entries / slots. As α grows, collisions grow:

(Knuth's approximations for linear probing: ½(1 + 1/(1−α)) and ½(1 + 1/(1−α)²).) Unsuccessful lookups degrade far faster — and in a storage engine many lookups are for absent keys. Tables therefore resize (typically double) when α crosses a threshold: 0.75–0.875 for linear probing, higher for SIMD designs like Swiss tables.

Probing schemes¶

A linear-probing map, with deletion done right¶

Deletion is the subtle part of open addressing. Simply clearing a slot breaks lookups of keys that probed past it: their search would stop at the new empty slot. Two fixes:

• Tombstones: mark the slot "deleted"; lookups skip it, inserts may reuse it. Simple, but tombstones accumulate and lengthen probes until a rehash.
• Backward-shift deletion: after removing an entry, shift later entries of the same probe run back to fill the hole. No tombstones; the table stays as if the key had never been inserted.

// Open addressing with linear probing and backward-shift deletion.
// Keys are uint64; key 0 is reserved to mean "empty slot".
type slot struct{ key, value uint64 }

type Map struct {
    slots []slot // length is a power of two
    mask  uint64
    size  int
}

func splitmix64(x uint64) uint64 { // finalizer: mixes every bit into the low bits
    x ^= x >> 30
    x *= 0xbf58476d1ce4e5b9
    x ^= x >> 27
    x *= 0x94d049bb133111eb
    x ^= x >> 31
    return x
}

func (m *Map) Put(key, value uint64) {
    if (m.size+1)*8 > len(m.slots)*7 { // keep load factor <= 7/8
        m.grow() // double and reinsert everything
    }
    i := splitmix64(key) & m.mask
    for m.slots[i].key != 0 && m.slots[i].key != key {
        i = (i + 1) & m.mask
    }
    if m.slots[i].key == 0 {
        m.size++
    }
    m.slots[i] = slot{key, value}
}

func (m *Map) Get(key uint64) (uint64, bool) {
    for i := splitmix64(key) & m.mask; m.slots[i].key != 0; i = (i + 1) & m.mask {
        if m.slots[i].key == key {
            return m.slots[i].value, true
        }
    }
    return 0, false // hit an empty slot: absent
}

func (m *Map) Delete(key uint64) bool {
    i := splitmix64(key) & m.mask
    for m.slots[i].key != key {
        if m.slots[i].key == 0 {
            return false
        }
        i = (i + 1) & m.mask
    }
    // Backward shift: pull later entries of the same probe run into the
    // hole, so lookups never stop early at a gap. No tombstones needed.
    hole := i
    for j := (i + 1) & m.mask; m.slots[j].key != 0; j = (j + 1) & m.mask {
        home := splitmix64(m.slots[j].key) & m.mask
        // Move j into the hole only if its home is not in the cyclic range (hole, j].
        if (j-home)&m.mask >= (j-hole)&m.mask {
            m.slots[hole] = m.slots[j]
            hole = j
        }
    }
    m.slots[hole] = slot{}
    m.size--
    return true
}

The shift condition, (j-home)&mask >= (j-hole)&mask, says: entry j may move into hole only if its home slot is not between the hole and j (cyclically) — otherwise moving it earlier would put it before its home, where lookups would never find it. This map was checked against Go's built-in map over 2 million random put/get/delete operations on a key range of 5,000 (heavy collisions and deletions).

Measured (Go 1.26.4, Apple M1 Pro):

A specialized table beats the general one by about 1.6x here — it hashes with a few multiplies instead of a seeded general hash and stores keys and values inline — which is only worth the code in a measured hot path. The probe-length row is the important one: the same table with a weak hash degrades from O(1) to scanning over a thousand slots per miss.

Resizing and latency¶

Doubling a table rehashes every entry at once: a table of 100 million entries pauses one insert for a long time. Latency-sensitive systems resize incrementally: Redis keeps two tables during a rehash and moves a few buckets on each operation; lookups check both. Another option is to size tables up front when the count is known (a block cache with a fixed capacity).

Concurrent hash tables¶

Sharding is usually enough: with 16–64 shards, contention on any one lock is low, and each shard's code is the simple single-threaded table. Pick the shard with different hash bits from those used for the bucket index inside the shard, or each shard's table will see only a fraction of its buckets used.

Hash indexes on disk¶

Bitcask: an in-memory hash over an on-disk log¶

Bitcask (the storage engine behind Riak) appends every write to a log file and keeps an in-memory hash table — the keydir — from each key to (file id, offset, size) of its latest value.

A read is one hash lookup plus one disk read; a write is one sequential append. Merging (compaction) rewrites live values into new files. Limits: all keys must fit in RAM, and there are no range queries — neighboring keys are unrelated in a hash table. Startup must rebuild the keydir (Bitcask writes "hint files" to speed this up).

Extendible hashing¶

Extendible hashing grows an on-disk hash index one bucket at a time, without rehashing everything.

• A directory of 2^G pointers to bucket pages, where G is the global depth; a key's bucket is chosen by the first G bits of its hash.
• Each bucket has a local depth L ≤ G: how many hash bits its keys actually share. Several directory entries can point to one bucket.
• When a bucket overflows:
• If L < G: split it into two buckets with depth L+1, redistribute its keys by bit L+1, and repoint half of the directory entries that pointed to it.
• If L = G: first double the directory (G+1, each entry duplicated), then split.

Worked example (bucket capacity 2). G=1: directory 0 → A, 1 → B, both local depth 1. Insert keys with hashes 00, 01, then 00... A holds 00, 01 and overflows on the third 0x key. A's L=1 equals G=1, so the directory doubles to G=2: 00 → A, 01 → A, 10 → B, 11 → B. A splits into A0 (prefix 00) and A1 (prefix 01), both L=2; entries 00 → A0, 01 → A1. B is untouched, still L=1, pointed to by two entries. Only one bucket's keys moved.

Linear hashing¶

Linear hashing avoids the directory: buckets split in a fixed round-robin order, tracked by a split pointer, whenever the load factor crosses a threshold — regardless of which bucket overflowed (overflowing buckets use overflow pages meanwhile). A key's bucket is h mod 2^i, or h mod 2^(i+1) if that bucket has already been split this round. Growth is smooth and the address computation needs no directory. Berkeley DB's hash access method is based on it.

Where hash indexes are used¶

Most databases still default to B+Trees or LSM trees because they support range scans and ordering, which hash indexes cannot; hash structures appear as accelerators beside them.

Common pitfall¶

Writing a custom power-of-two open-addressing table "to beat the built-in map" and hashing integer keys with the identity (or key % something) because it is fastest. Keys that share low bits — page offsets that are multiples of 4096, aligned addresses, IDs allocated in strides — collapse into a handful of slots, probe runs grow to thousands (1,562 measured above), and an O(1) table behaves like a linear scan. The built-in map never had the problem, so it appears exactly when the code is "optimized." Always pair hash & mask indexing with a mixing hash, and measure the maximum probe length, not just the average.