Hash Tables from Scratch

01Why hash tables

The renderer asks for the compiled shader that matches this draw's feature flags, thousands of times a frame. Keep the shaders in a sorted array and each request is a binary search; keep them in a hash table and each request goes almost straight to the right slot. The difference is small for a hundred shaders and large for a million cached entries.

A hash table works by turning the key into a number (the hash) and using that number to pick a slot in an array. A sorted array gives O(log n) lookup via binary search; a hash table gives O(1) expected lookup, insert and delete. On a table too large for the cache, a hash lookup typically costs one or two cache misses (roughly 100 ns each from DRAM), while a binary search over a million keys makes about 20 dependent probes, most of the later ones misses^[23]. For lookups an engine makes many times per frame, such as the string interning table (which maps every distinct string to one canonical ID) or the shader permutation cache, that is the difference between a couple of hundred nanoseconds and a couple of microseconds per lookup.

Hash tables show up wherever you need a key-value mapping with fast access:

• Entity lookups. An ECS maps each entity ID to its component data. Most ECS designs do this with a directly indexed array rather than a hash table, because entity IDs are small, dense integers the engine hands out itself (§12). Hash tables take over when the keys are sparse or come from outside, such as network object IDs or asset GUIDs.
• Asset registries. The content browser maps asset paths (strings) to metadata. String-keyed hash tables, often over interned keys, are the usual structure here.
• Shader variant caches. A shader may compile into thousands of permutations (feature flags, platform toggles). The key is a bitmask or a small struct; the value is a compiled shader object. Lookup happens on the render thread, so it must be fast.
• String interning. The engine maps every unique string to a single canonical pointer. Subsequent comparisons become pointer equality (one instruction) instead of strcmp. Unreal's FName system is built on one.
• Deduplication. Content pipelines deduplicate textures, meshes, and animation curves by content hash. The dedup index is a hash table.

02A short history

Hashing is nearly as old as the stored-program computer: the first descriptions come from IBM in 1953. Two things from its history matter in practice. The core analysis (how many slots a lookup checks as the table fills) dates from Knuth in the 1960s and still holds, so the formulas in §5 are not new. And the designs engines ship today, Swiss tables and their relatives, are from 2017 on: they leave the theory alone and cut the constant factors with SIMD and cache-aware layouts.

03Hash functions

An asset registry is keyed by paths like textures/rock_01 and textures/rock_02, which differ in one character. If the hash maps them to the same or neighboring slots, every lookup in that corner of the table slows down. The hash function decides how evenly keys spread out.

A hash function maps a key of any size to a fixed-size integer. The table uses that integer, reduced to the table size, as a slot index. Two properties matter:

• Uniformity. The hash should distribute keys uniformly across the output range. Non-uniform hashes pile keys into the same slots, increasing probe lengths.
• The avalanche effect. Flipping one input bit should flip roughly half the output bits. A hash that fails this test (e.g., the identity function on sequential integers) creates patterns in the slot assignments that interact badly with power-of-2 table sizes.

Integer hashing

Division method: h(k) = k mod m. Simple, but the choice of m matters. If m is a power of 2, k mod m is just the low bits of k, and sequential keys land in sequential slots (no mixing). If m is prime, the distribution is better, but prime-modulo division is slow (an integer divide).

Fibonacci hashing (multiplication method): h(k) = (k * 2654435769) >> (32 - log2(m)). The magic constant is 2³²/φ, truncated. The multiply carries every input bit into the higher output bits, and the right shift keeps the top bits, which depend on the most input bits. The Linux kernel's hash_32() and hash_64() use this scheme.

String hashing

FNV-1a^[6]: XOR each byte into the hash, then multiply by a prime. One XOR and one multiply per byte: simple and fast on short keys, though its avalanche is weak (xxHash's benchmark table flags FNV64 for poor avalanche^[7]). The 64-bit variant uses offset basis 0xcbf29ce484222325 and prime 0x00000100000001B3.

xxHash^[7]: XXH64 processes 32 bytes per iteration using four 64-bit accumulators with multiply-rotate-accumulate rounds. Throughput-optimized for bulk data: the project's own reference benchmark puts XXH3 at 31.5 GB/s and XXH64 at 19.4 GB/s on an i7-9700K, against 3.0 GB/s for SipHash. XXH3 takes a 64-bit seed or, separately, a custom secret (192 bytes by default, at least 136). All variants pass SMHasher.

wyhash^[8]: very fast on short keys, which suits hash-table use. Uses wide multiplies (64-bit × 64-bit = 128-bit) to mix bits. Go's runtime has used a wyhash-derived function since Go 1.17 on CPUs without the AES instructions its main hash relies on.

For string interning, the hash needs to be fast on short strings, and deterministic across runs (no random seed) if hash values are baked into cooked data or used as persistent IDs. FNV-1a is a common choice. For tables keyed by untrusted input (network-facing code), use a keyed hash with a random per-process key, such as SipHash, to prevent hash flooding. Seeding a fast hash such as wyhash raises the bar, but those hashes aren't designed as keyed PRFs.

04Chaining

Two asset paths hash to the same slot. That's a collision, and with more keys than a handful it's guaranteed to happen, so every hash table needs a rule for it. The simplest rule is to let a slot hold more than one entry. Separate chaining does exactly that: each slot holds a pointer to a linked list of entries that hash to that slot. Insert adds a node to the list. Lookup walks the list comparing keys. Delete removes the node.

The expected list length is the load factor α = n/m. Under the SUHA, an unsuccessful search examines α entries on average; a successful search examines roughly 1 + α/2^[3].

Chaining tolerates load factors above 1.0 (more keys than slots). Java's HashMap defaults to a maximum α of 0.75 and doubles its bucket array when it crosses that threshold^[18] (std::unordered_map defaults to 1.0), but correctness doesn't depend on staying below 1.0.

The problem is cache behavior. Each lookup dereferences a pointer to the list head, then follows next pointers through heap-allocated nodes scattered across memory. Each pointer chase is a potential DRAM miss (roughly 100 ns on modern hardware^[23]). At α = 0.75, the average chain is short, but even one miss per lookup adds up at engine-frame frequency. Open addressing (next section) keeps all entries in a flat array, giving the CPU prefetcher something to work with.

Chaining still ships widely: std::unordered_map, Java's HashMap, Redis's dict and Unreal's TMap all chain. It keeps elements in place (pointers to them survive a rehash), tolerates load factors above 1, and never moves large values. Where none of that matters, open addressing is usually faster on modern hardware.

05Open addressing: linear probing

Every node in a chained table is a separate allocation, so every chain hop can be a cache miss. A shader cache on the render thread would rather keep all its entries in one flat array that the CPU can read in order. Open addressing stores all entries directly in the table array. No linked lists, no per-entry allocations, no pointer chasing. When a key hashes to an occupied slot, the table probes forward through the array until it finds an empty slot (for insert) or the target key (for lookup).

Linear probing is the simplest variant: the probe sequence for slot h is h, h+1, h+2, ... (mod m). Insert walks forward until it finds an empty slot. Lookup walks forward until it finds the key or an empty slot (proof that the key isn't present).

The catch is that the fuller the table, the longer the walk. At half full, most keys sit at or next to their home slot. At 90% full, a lookup for a missing key has to walk past long runs of occupied slots before it finds an empty one.

Knuth's analysis^[3] gives those expected probe counts under uniform hashing, the same simple-uniform-hashing assumption CLRS chapter 11 works from^[25]. The formulas tell you how many slots a lookup checks at a given fullness, which is what decides when the table should grow:

In words: a lookup that finds its key checks about half of 1 + 1/(1 − α) slots, and one that misses checks about half of 1 + 1/(1 − α)². Both are small while the table is half empty (1.5 and 2.5 probes at α = 0.5) and blow up as α nears 1, the miss cost fastest because of the square. That's why open-addressing tables resize well before α = 1.

The failure mode is primary clustering. When several keys hash to nearby slots, their probe runs merge into a single long cluster. New keys that hash anywhere into the cluster join it, making it longer. A cluster's chance of growing is proportional to its length, so long clusters grow fastest^[3]. The widget below makes this visible: as the load factor increases, the table fills with long contiguous runs of occupied slots.

06Quadratic probing and double hashing

The clustering widget showed one run swallowing 44 of 64 slots at load factor 0.9. Linear probing's clustering problem comes from the step size: +1 every time, so any key that lands anywhere in a run extends it. The fix is to step further on each probe, so that keys starting at nearby slots fan out instead of queuing behind each other. Two mitigations:

Quadratic probing: the probe sequence is h, h+1, h+3, h+6, h+10, ... (adding 1, 2, 3, 4, ... to the previous offset, i.e., triangular numbers). This breaks primary clustering because keys that hash to different slots follow different probe paths. It introduces a weaker problem called secondary clustering: keys that hash to the same slot still follow the same sequence, but keys at different slots don't pile up.

There is a coverage guarantee: if the table size m is a power of 2, the triangular offsets 0, 1, 3, 6, ..., m(m−1)/2 are all distinct mod m, so the sequence visits every slot exactly once before repeating.

Double hashing: the step size is a second hash function h₂(key). The probe sequence is h₁(key), h₁(key) + h₂(key), h₁(key) + 2·h₂(key), ... The step size must share no factor with m (with a power-of-2 table, force h₂ odd) so the sequence reaches every slot. Because the step depends on the key, keys with the same home slot usually follow different sequences, which removes both primary and secondary clustering. With a good second hash the expected probe counts come close to the uniform-probing ideal: 1/(1 - α) for unsuccessful search, (1/α) ln(1/(1 - α)) for successful search. At α = 0.75 that's 4 probes for a miss and about 1.85 for a hit, against linear probing's 8.5 and 2.5.

The downside: double hashing's non-sequential probe pattern defeats the CPU prefetcher. Linear probing's sequential scan loads the next cache line automatically; double hashing jumps around the array, incurring a cache miss on most probes. In practice, linear probing with a good hash function and a moderate load factor (α ≤ 0.7) often beats double hashing on wall-clock time despite having higher probe counts, because most of its probes land on a cache line that is already loaded.

07Robin Hood hashing

In a linear-probing table a few unlucky keys can end up ten or more slots from home while most sit at home. The average lookup is fine; the worst ones are slow, and a frame budget cares about the worst ones. Robin Hood hashing^[4] evens that out. It is linear probing with one added rule: during insert, if the new key's probe distance exceeds the incumbent key's probe distance at the current slot, swap them. The displaced incumbent continues probing from where the new key took over. The invariant: "steal from the rich (short probe distance), give to the poor (long probe distance)."

For successful searches, the effect is on the spread only. For a fixed key set and hash function, Robin Hood insertion occupies exactly the same slots as plain linear probing: it only changes which key sits in each of them. Total displacement is therefore identical, and so is the mean probe count for a successful search. What shrinks is the spread between the luckiest and unluckiest keys.

The other win is for lookups that miss, which can stop early. If the resident at the current slot has a smaller probe distance than the search key would have at this position, the key cannot be further along: had it been inserted, it would have taken this slot from the resident. The search stops there instead of running to an empty slot.

Rust's standard HashMap used Robin Hood hashing with backward-shift deletion from 2014 until Rust 1.36 (2019), when it was replaced by the Swiss-table-based hashbrown crate^[14]. hashbrown's README reports it as around 2× faster than the implementation it replaced, with 1 byte of overhead per entry instead of 8^[14].

08Swiss tables (flat hash maps)

Even a well-tuned linear-probing table compares keys one slot at a time, and for string keys each comparison can be a pointer chase. Modern CPUs have SIMD instructions that compare a whole register of bytes at once, and Swiss tables are built to use them. Google's Swiss table design^[11] is the one most current high-performance hash maps build on. The core idea: store one metadata byte per slot in a separate array, and use SSE2 instructions (x86's 128-bit SIMD set) to compare 16 metadata bytes in one instruction. A lookup that would take 16 separate comparisons in a conventional table takes one _mm_cmpeq_epi8.

The H1/H2 split

The hash of a key is split into two parts:

• H1 (57 bits in the design notes): picks the probe's starting position^[12].
• H2 (the other 7 bits): stored in the metadata byte for that slot. A compact fingerprint used to filter candidates before comparing the full key.

Which 7 bits become H2 has changed between versions. The design notes and early Abseil take H2 from the low bits (H1 = hash >> 7); current Abseil takes the top 7 bits and uses the whole hash, masked by the capacity, for the starting position^[13].

Each metadata byte is empty (0x80 = 0b10000000), deleted/tombstone (0xFE), or occupied (0b0xxxxxxx, where the 7 low bits are H2); a fourth value, the sentinel 0xFF, marks the end of the array for iterators. The high bit distinguishes empty/deleted from occupied, and the 7-bit H2 fingerprint filters out roughly 127/128 of non-matching keys before the table compares the full key.

The SIMD probe

A lookup works as follows:

1. Compute H1 and H2 from the key's hash.
2. Use H1 to find the starting group: 16 consecutive metadata bytes on SSE2, 8 on ARM and the portable fallback, starting at whatever index H1 lands on rather than at an aligned boundary.
3. Load the 16 metadata bytes into a 128-bit SSE2 register.
4. Broadcast H2 into all 16 lanes of a second register.
5. Execute _mm_cmpeq_epi8: each lane that matches produces 0xFF; non-matches produce 0x00.
6. Extract a 16-bit bitmask with _mm_movemask_epi8. Each set bit is a candidate slot.
7. For each candidate, compare the full key. On a match, return the value.
8. If no match, check if any metadata byte in the group was "empty." If so, the key is absent. If the group was full or contained only tombstones, advance to the next group (quadratic probing on groups) and repeat.

The result: most lookups check one group of 16 slots with a couple of SIMD instructions and zero or one full-key comparison. At Abseil's maximum load factor of 7/8, a 16-slot group has two empty slots on average^[13], so most probes end in the first group.

09Deletion strategies

An entity despawns and its entry leaves the table. In an open-addressing table that's harder than it looks. You cannot simply clear a slot, because that breaks probe chains: a lookup for a key whose probe passed through the now-empty slot would stop too early and falsely report "not found."

Four strategies:

• Tombstones. Mark the deleted slot as "deleted" instead of "empty." Lookups treat tombstones as occupied (skip over them); inserts treat them as empty (reuse them). Simple, but tombstones accumulate and slow down lookups that miss. Swiss tables use this (the 0xFE metadata byte).
• Backward shift deletion. After removing a key, scan forward and shift back any subsequent key whose home slot is at or before the deleted position. Maintains the linear-probing invariant without tombstones. Used by Robin Hood tables (Rust's pre-hashbrown HashMap used this). More expensive per delete, but lookups never encounter stale markers.
• Robin Hood deletion. A variant of backward shift: after removing a key, walk forward; any key with probe distance > 0 shifts back one slot, decrementing its probe distance. Terminates when a key is already at its home slot or an empty slot is found.
• Rehash on delete. After deleting, reinsert every key in the cluster. Correct but expensive. Only viable for tiny tables or when deletions are rare.

Abseil's Swiss table avoids some of those tombstones. Its erase writes kEmpty instead of kDeleted whenever it can prove no probe sequence could have run past the slot. It reads the control group starting at the slot and the group one width earlier, and if the run of non-empty control bytes spanning the slot is shorter than one probe window, the slot goes straight back to empty^[26]. That shrinks the tombstone population without eliminating it, which is why tombstones still count against the growth budget: "Tombstones (kDeleted slots) are not included in the growth capacity, because we'd like to rehash when the table is filled with tombstones and/or full slots."^[26]

Tombstone accumulation is a common performance bug in hand-rolled tables. A table with many inserts and deletes fills with tombstones, and lookups that miss scan more and more of them. The fix is periodic compaction (rehash everything into a fresh table, dropping tombstones) or use backward-shift deletion.

10Load factor and resizing

A table that never grows gets slower with every insert, as §5's formulas showed. A table that grows has to move every entry when it does, and on a game server that one big move can cost a frame. Both the threshold and the way the move happens matter. When the load factor exceeds a threshold, the table allocates a larger array and reinserts every key. The threshold depends on the probing strategy:

• Linear probing: resize at α = 0.5 to 0.7. Higher than 0.7 and clustering dominates.
• Robin Hood: can run near α = 0.9 (Rust's pre-2019 HashMap used 10/11) because probe lengths stay tightly grouped, though inserts and misses still slow down.
• Swiss tables (Abseil): resize at α = 7/8 = 0.875. The SIMD probe tolerates high load because most lookups still check only one group.
• Chaining: resize at α = 0.75 (Java's default) or 1.0 (std::unordered_map's). Can exceed 1.0, with cost growing linearly in α.

Growth policies

Power-of-2 growth (double the table size): modulo reduces to a bitmask (h & (m-1)), avoiding integer division. Requires a hash function with good avalanche; a bad hash combined with power-of-2 modulo creates systematic collisions. Most open-addressing tables use this.

Prime growth (a prime near double the old size): better distribution with mediocre hash functions, but the modulo is an integer division, which costs tens of cycles on many x86 cores unless the compiler knows the divisor at compile time and can turn it into a multiply. libstdc++'s and libc++'s std::unordered_map use prime bucket counts.

Incremental rehashing (the Redis approach)

A full rehash of n keys is O(n). For a real-time system (a game server, an in-memory database), a single O(n) stall can be unacceptable. Redis^[19], whose dict is a chained table, avoids it with incremental rehashing: during a resize it keeps two tables, ht[0] and ht[1]. The new table is allocated up front, but entries move over one bucket at a time as regular inserts, deletes and lookups run (plus a little on a timer). New keys go straight into ht[1]. A lookup checks ht[0] unless the key's bucket there has already been migrated, then ht[1]. The field rehashidx tracks progress; when it reaches the end, the old table is freed.

Amortized O(1) and a bounded worst case are different promises, and the widget separates them. Total work over the run is close either way. What the stop-the-world table cannot offer is a ceiling on any single operation, and a frame budget constrains the worst case.

Amortized O(1) proof sketch

Each insert costs O(1) expected. A resize from n to 2n slots costs O(n) but happens only after about n/2 inserts since the previous one (the table grew from n/2 entries to n). Spread that cost over those inserts and each pays O(1) amortized, meaning averaged over the whole run of inserts.

11Cache behavior and memory layout

Two tables can do the same number of probes and still differ several times in speed, because a lookup's cost is set by how many cache lines it touches, and several slots can share one line. Open addressing's advantage on modern hardware comes mostly from cache lines. A typical cache line is 64 bytes. A linear-probing table with 8-byte entries fits 8 entries per cache line. A probe that walks 4 consecutive slots likely hits within the same cache line (one miss for the first, then three hits). A chaining table dereferences a pointer to a heap-allocated node, which is almost certainly on a different cache line, so every hop is a miss.

Swiss tables push this further. The metadata array is separate from the key-value array: 16 metadata bytes fit in a single 16-byte chunk (one quarter of a cache line). Loading and comparing the group metadata is fast because the data is tiny and contiguous. The full-key comparison, which touches the key-value array, usually happens once per successful lookup and rarely on a miss.

Prefetching. Abseil's lookup issues a prefetch for the slots at the probe position before it loads the control bytes, so the slot-array fetch overlaps the SIMD compare instead of starting after a match. It also exposes prefetch(key), which lets code that knows its next key start both fetches early and overlap them with other work^[13].

Alignment. It is tempting to assume the group is 16-byte aligned so the SSE2 load is a single aligned load. Abseil does the opposite on purpose: a group starts at whatever index H1 lands on, and the load is _mm_loadu_si128, deliberately unaligned^[13]. That is also why the implementation mirrors the first Group::kWidth - 1 control bytes past the end of the array: an unaligned window starting near the end must still be able to read a full group's worth of bytes.

Group width depends on the target. Everything above describes the SSE2 path. Abseil's AArch64 group is 8 slots wide and uses vceq_u8, the 64-bit form, not vceqq_u8; the portable fallback is 8 wide too^[13]. Rust's hashbrown makes the same split, taking the SSE2 path because "it allows us to scan 16 buckets at once instead of 8"^[14]. Phones and the Nintendo Switch are ARM (PlayStation 5 and Xbox Series consoles are x86), so when reasoning about probe counts on target hardware, check the group width before assuming 16.

12Game engine case studies

Here's what shipping engines and libraries actually build, and why each made the choice it did. The pattern to watch for: when the keys are small integers the engine hands out itself, the fastest "hash table" is often no hash table at all.

1 · Unreal's TMap

TMap<K,V> is implemented as a TSet<TPair<K,V>> backed by a sparse array^[20]. Collisions are resolved by chaining rather than probing, but the chain is intrusive. In the engine source each TSet element carries a HashNextId, the sparse-array index of the next element in its bucket, so a lookup hashes to a bucket head and then walks element indices rather than heap nodes. Removal unlinks the element from its bucket's chain and leaves a reusable gap in the sparse array, so no tombstone is needed. The hash function is GetTypeHash(), customizable per key type; the set allocator decides how many hash buckets to use^[20]. Epic's documentation calls TMap the most commonly used container in Unreal after TArray^[20].

2 · EASTL hash_map

Electronic Arts' EASTL^[21] provides hash_map and fixed_hash_map (pre-allocated, no heap allocation during gameplay). The layout is textbook separate chaining: mpBucketArray is an array of node pointers, and every element including the first lives in a heap node holding the value, a next pointer, and optionally a cached hash code so a probe can reject a node without touching the key^[22]. Nothing is inlined into the bucket slot. What suits it to fixed memory budgets is fixed_hash_map, which pre-allocates both the bucket array and a fixed node pool, so no allocation happens during gameplay. Note also that EASTL's default rehash policy uses prime bucket counts with a max load factor of 1.0, not the 0.7-to-0.875 range the flat tables in this tutorial use.

3 · Entity-to-component lookup in ECS

In a sparse-set ECS (EnTT and similar), each component type has a dense array of component data and a sparse array mapping entity IDs to indices into the dense array. The sparse array is direct-indexed (not hashed): the entity ID is the array index, giving O(1) lookup with no collision resolution. The archetype engines mostly do not hash entities either. Bevy resolves an entity through a Vec<EntityMeta> indexed directly by the entity's index; Flecs uses a paged sparse-set entity index; Unity DOTS addresses its chunk lookup by entity index. Direct indexing beats hashing here for the same reason the sparse set does: the key space is dense and allocated by you.

When entity IDs do go into a hash table (a map from entity to some sparse per-entity state, say), the hash has to suit the table. Bevy's EntityHasher is a good worked example. For hashbrown's Swiss table it leaves the entity index in the low bits, which pick the slot, so entities spawned together stay together in memory, and it multiplies by a golden-ratio constant to fill the high bits that become H2; an identity hash would leave H2 the same for every small ID, so every occupied slot in a group would match the SIMD filter. Its documentation warns that the scheme suits contiguous indices and that unusual patterns, such as indices that are all multiples of 256, need a general-purpose hash^[27].

4 · String interning (FName)

Unreal's FName system hashes the string once, stores it in a global name table (a hash table of unique strings), and thereafter uses the table index as the name's identity. Comparing two FNames is an integer comparison rather than a string comparison. Creating an FName from a string costs one hash and a short probe of the name table.

5 · Shader permutation caches

A material with 12 boolean features generates up to 4096 shader permutations. The compiled-shader cache maps a permutation key (a bitmask or a small struct of flags) to a compiled pipeline state object. The key is small, so a multiplicative hash of the bitmask is enough, and a flat open-addressing table is a natural fit. The lookup sits on the render thread's per-draw path, so it has to stay cheap.

6 · The flat-map family and its group widths

Three widely used tables share the Swiss-table idea and disagree about the group. Abseil filters 16 slots at a time with SSE2, dropping to 8 where it is unavailable. Boost's unordered_flat_map uses groups of 15 buckets inside a 16-byte metadata word, spending the sixteenth byte on an overflow marker that "removes the need to use tombstones"^[15], and pins the maximum load factor at 0.875 with no way for the user to change it^[15]. Meta's F14 is named "because it filters 14 slots at once", with a one-byte tag per slot, SSE2 or NEON filtering, and a typical maximum load factor of 12/14^[16]. The filtering mechanism is shared; the group width, the load-factor ceiling and the handling of deletions differ.

Implementation: open-addressing hash table

#include <bit>
#include <cstddef>
#include <cstdint>
#include <vector>

// Minimal open-addressing hash table with linear probing.
// Tombstone deletion. Power-of-2 table size. Fibonacci hash.
struct FlatMap {
    enum SlotState : uint8_t { EMPTY, OCCUPIED, DELETED };

    struct Slot {
        SlotState state = EMPTY;
        uint64_t key;
        uint64_t value;
    };

    std::vector<Slot> slots;
    size_t count = 0;                          // live entries
    size_t tombstones = 0;                     // DELETED slots, still probe-blocking
    size_t mask;                                // table_size - 1

    explicit FlatMap(size_t capacity = 16)
        : slots(capacity), mask(capacity - 1) {}

    // Fibonacci hash: multiply by 2^64 / phi, keep the top log2(size) bits.
    size_t hash(uint64_t key) const {
        // Capacity must be a power of two (and at least 2) for `mask` to be
        // all-ones and the shift to stay below 64.
        return (key * 11400714819323198485ULL) >> (64 - std::countr_zero(mask + 1));
    }

    void insert(uint64_t key, uint64_t value) {
        // Tombstones occupy slots but are not counted in `count`, so the load
        // factor must be tested against occupied + deleted. Testing `count`
        // alone lets a table under insert/erase churn fill entirely with
        // tombstones and never grow, at which point find() never terminates.
        if ((count + tombstones) * 10 > (mask + 1) * 7) rehash();
        size_t idx = hash(key);
        // Walk the whole probe run to EMPTY looking for the key, but remember
        // the first tombstone so we can reuse it. Stopping at the first
        // tombstone would insert a duplicate when the key lives further along.
        size_t firstTombstone = SIZE_MAX;
        while (slots[idx].state != EMPTY) {
            if (slots[idx].state == OCCUPIED && slots[idx].key == key) {
                slots[idx].value = value;             // update existing
                return;
            }
            if (slots[idx].state == DELETED && firstTombstone == SIZE_MAX)
                firstTombstone = idx;
            idx = (idx + 1) & mask;                   // linear probe
        }
        if (firstTombstone != SIZE_MAX) {
            idx = firstTombstone;
            tombstones--;                             // reclaimed
        }
        slots[idx] = { OCCUPIED, key, value };
        count++;
    }

    uint64_t* find(uint64_t key) {
        size_t idx = hash(key);
        while (slots[idx].state != EMPTY) {
            if (slots[idx].state == OCCUPIED && slots[idx].key == key)
                return &slots[idx].value;
            idx = (idx + 1) & mask;
        }
        return nullptr;
    }

    void erase(uint64_t key) {
        size_t idx = hash(key);
        while (slots[idx].state != EMPTY) {
            if (slots[idx].state == OCCUPIED && slots[idx].key == key) {
                slots[idx].state = DELETED;           // tombstone
                count--;
                tombstones++;
                return;
            }
            idx = (idx + 1) & mask;
        }
    }

    void rehash() {
        size_t newSize = (mask + 1) * 2;
        std::vector<Slot> old = std::move(slots);
        slots.assign(newSize, Slot{});
        mask = newSize - 1;
        count = 0;
        tombstones = 0;   // rehashing is what actually reclaims them
        for (auto& slot : old)
            if (slot.state == OCCUPIED) insert(slot.key, slot.value);
    }
};

// Minimal open-addressing hash table with linear probing.
// Tombstone deletion. Power-of-2 table size. Fibonacci hash.
const FIB: u64 = 11400714819323198485;

enum Slot {
    Empty,
    Deleted,
    Occupied { key: u64, value: u64 },
}

struct FlatMap {
    slots: Vec<Slot>,
    count: usize,        // live entries
    tombstones: usize,   // Deleted slots, still probe-blocking
    mask: usize,
}

impl FlatMap {
    fn new(capacity: usize) -> Self {
        let slots = (0..capacity).map(|_| Slot::Empty).collect();
        FlatMap { slots, count: 0, tombstones: 0, mask: capacity - 1 }
    }

    fn hash(&self, key: u64) -> usize {
        let shift = 64 - (self.mask + 1).trailing_zeros();
        (key.wrapping_mul(FIB) >> shift) as usize
    }

    fn insert(&mut self, key: u64, value: u64) {
        // Tombstones block probes but are not in `count`, so they must be part
        // of the load test or a churning table never grows and find() spins.
        if (self.count + self.tombstones) * 10 > (self.mask + 1) * 7 {
            self.rehash();                  // resize at alpha = 0.7
        }
        let mut idx = self.hash(key);
        let mut first_tombstone: Option<usize> = None;
        // Run to Empty looking for the key. Stopping at the first tombstone
        // would insert a duplicate whenever the key sits further along.
        loop {
            match &self.slots[idx] {
                Slot::Occupied { key: k, .. } if *k == key => {
                    self.slots[idx] = Slot::Occupied { key, value };
                    return;
                }
                Slot::Empty => break,
                Slot::Deleted => {
                    if first_tombstone.is_none() { first_tombstone = Some(idx); }
                    idx = (idx + 1) & self.mask;
                }
                _ => idx = (idx + 1) & self.mask,   // linear probe
            }
        }
        if let Some(slot) = first_tombstone {
            idx = slot;
            self.tombstones -= 1;          // reclaimed
        }
        self.slots[idx] = Slot::Occupied { key, value };
        self.count += 1;
    }

    fn erase(&mut self, key: u64) {
        let mut idx = self.hash(key);
        loop {
            match &self.slots[idx] {
                Slot::Occupied { key: k, .. } if *k == key => {
                    // Tombstone, not Empty: an Empty here would cut the probe
                    // run and hide every key that probed past this slot.
                    self.slots[idx] = Slot::Deleted;
                    self.count -= 1;
                    self.tombstones += 1;
                    return;
                }
                Slot::Empty => return,
                _ => idx = (idx + 1) & self.mask,
            }
        }
    }

    fn find(&self, key: u64) -> Option<u64> {
        let mut idx = self.hash(key);
        loop {
            match &self.slots[idx] {
                Slot::Occupied { key: k, value } if *k == key => {
                    return Some(*value);
                }
                Slot::Empty => return None,
                _ => idx = (idx + 1) & self.mask,
            }
        }
    }

    fn rehash(&mut self) {
        let new_size = (self.mask + 1) * 2;
        let old = std::mem::replace(
            &mut self.slots,
            (0..new_size).map(|_| Slot::Empty).collect(),
        );
        self.mask = new_size - 1;
        self.count = 0;
        self.tombstones = 0;   // rehashing is what reclaims them
        for slot in old {
            if let Slot::Occupied { key, value } = slot {
                self.insert(key, value);
            }
        }
    }
}

13Pitfalls

Use this as a review checklist. Each item is a hash table bug that passes ordinary tests and shows up later as a slow frame or a server under attack.

• Hash flooding (DoS). An attacker crafts keys that all hash to the same slot. Expected O(1) becomes O(n). Crosby and Wallach demonstrated this against the Bro intrusion-detection system in 2003, driving it to drop "as much as 71% of its traffic" using less bandwidth than a dialup modem^[10]. Defense: use a keyed hash with a random key, such as SipHash. Rust's default HashMap uses SipHash-1-3 with random keys for this reason.
• Identity hashes in Swiss tables. Swiss tables take H2 from the hash bits that don't pick the slot. An identity hash on small integer keys leaves those bits zero, so every occupied control byte in a group matches every lookup and each probe degenerates into full-key comparisons. Mix the high bits in (a multiply is enough) before handing integers to a Swiss table.
• Iterator invalidation. An insert that triggers a rehash invalidates every iterator, and in open-addressing tables it moves every entry, so pointers die too. Erasing the current element inside a range-based for loop over a std::unordered_map is undefined behavior, because the loop then increments an invalidated iterator. Use the iterator that erase() returns to continue.
• Tombstone accumulation. A table with many insert/delete cycles fills with tombstones. Misses and inserts slow down because probes skip tombstones but can't stop at them. Fix: periodic rehash to compact, or use backward-shift deletion.
• Power-of-2 modulo with bad hashes. If h(k) = k and m = 2^p, then h(k) & (m-1) is just the low p bits. If keys share low bits (e.g., pointers aligned to 8 bytes), they all map to the same few slots. Fix: mix the bits before masking (Fibonacci multiply, or h >> 16 ^ h on 32-bit hashes).
• Using mutable fields as hash keys. If you insert a key, then modify the fields the hash depends on, the entry becomes unreachable: the lookup hashes to a different slot than the one the entry occupies. Unreal's documentation calls it undefined behavior for TMap^[20].

14What's next

Next in the series, Sorting Algorithms covers the other half of organizing data: putting it in order, from insertion sort to radix sort, which distributes keys into buckets much like a hash table does. Beyond this page, the hash-table variants worth knowing about:

• Perfect hashing. If the key set is known at compile time (keyword tables, opcode maps), a perfect hash function maps each key to a unique slot with zero collisions. gperf and the CMPH library generate them. O(1) worst case, not just expected.
• Cuckoo hashing. Two tables, two hash functions. Each key has exactly two candidate slots (one per table). Insert displaces the incumbent if both candidates are occupied, kicking it to its alternate slot. Worst-case O(1) lookup (check two slots, done). Resize is rare but O(n) when it happens.
• Concurrent hash maps. Lock-free and lock-striped variants: Java's ConcurrentHashMap, Intel TBB's concurrent_hash_map, folly's AtomicHashMap. The main challenge is resizing without blocking readers.
• GPU hash tables. SlabHash (Ashkiani et al., 2018) and the CUDA hash table in cuCollections. GPU hash tables must tolerate high contention across thousands of threads and avoid warp divergence on probe-chain walks.

For the engine programmer, the most useful next step is to profile your game's hottest hash table. Measure the load factor, the average probe length, and the cache-miss rate. If the table is chained, benchmark a switch to open addressing. If it's open addressing with a weak hash, try a multiplicative (Fibonacci) mix. If it's already a Swiss table, the remaining wins are usually in the hash function and the key layout.

15Sources

1. Hans Peter Luhn. Internal IBM memorandum on hash addressing, January 1953. Not publicly available; described in the IEEE Spectrum article "Hans Peter Luhn and the Birth of the Hashing Algorithm." spectrum.ieee.org. Knuth's history of hashing credits this memo as the origin of hashing and of chaining.
2. W. Wesley Peterson. "Addressing for Random-Access Storage." IBM Journal of Research and Development 1(2):130-146, April 1957. DOI: 10.1147/rd.12.0130. ieeexplore.ieee.org/document/5392733. Per Knuth, the first major paper on searching large files: it defines open addressing, analyzes uniform probing, and gives empirical statistics for linear probing.
3. Donald E. Knuth. The Art of Computer Programming, Volume 3: Sorting and Searching, Section 6.4 "Hashing." Addison-Wesley, 1973 (2nd edition 1998). ISBN 0-201-89685-0. gwern.net (excerpt). The reference analysis of hashing: division/multiplication methods, expected probe lengths for linear probing, double hashing, and chaining under SUHA. The linked excerpt is the section's history, the source for the Luhn, Amdahl and Peterson attributions in §2.
4. Pedro Celis. "Robin Hood Hashing." PhD thesis, University of Waterloo, Technical Report CS-86-14, 1986. cs.uwaterloo.ca (PDF). The primary source for the Robin Hood constants in §7, including the numerically computed variance of about 1.883 and the comparison with binary tree hashing. Its constant search cost at full load relies on a new, mean-centered search algorithm rather than the forward scan production tables use.
5. Patricio V. Poblete, Alfredo Viola. "Robin Hood Hashing really has constant average search cost and variance in full tables." AofA 2016; arXiv:1605.04031. arxiv.org (PDF). Proves, in the random-probing model, that Robin Hood's search-cost variance stays bounded by a small constant as the load factor approaches 1, and that a mean-centered search therefore runs in expected constant time. Source of the quoted "does not change the expected search cost" and "turns out to have a dramatic effect on its variance".
6. Glenn Fowler, Landon Curt Noll, Kiem-Phong Vo. "FNV Hash." IETF Internet-Draft (informational). ietf.org/archive/id/draft-eastlake-fnv-21.html. The FNV-1a hash specification: XOR each byte then multiply by a prime. Public domain. Also the source for the 1991 origin in reviewer comments on POSIX P1003.2.
7. Yann Collet. "xxHash: Extremely fast non-cryptographic hash algorithm." GitHub repository, 2012-present. github.com/Cyan4973/xxHash. Throughput-optimized hash using four accumulators with multiply-rotate rounds. The README's benchmark table (i7-9700K) gives the throughput figures in §3 and flags FNV64 for poor avalanche; XXH3 accepts a seed or a custom secret of at least 136 bytes.
8. Wang Yi. "wyhash: The fastest quality hash function." GitHub repository, 2019. github.com/wangyi-fudan/wyhash. Uses wide multiply (64x64=128) for mixing. The README lists it as the default hash in Zig, V, Nim, and Go (since 1.17, as the runtime's non-AES fallback).
9. Reini Urban et al. SMHasher (rurban fork). github.com/rurban/smhasher. The standard test battery referenced in §3: avalanche, differential and keyset tests, plus bad-seed detection, with throughput reported separately for bulk and small keys.
10. Scott A. Crosby, Dan S. Wallach. "Denial of Service via Algorithmic Complexity Attacks." 12th USENIX Security Symposium, 2003. usenix.org (PDF). The origin of hash flooding as a practical attack: with chosen input a hash table degenerates to a linked list, and their Bro server was driven to drop "as much as 71% of its traffic" using less bandwidth than a dialup modem.
11. Matt Kulukundis. "Designing a Fast, Efficient, Cache-friendly Hash Table, Step by Step." CppCon 2017. youtube.com/watch?v=ncHmEUmJZf4. See also: abseil.io/about/design/swisstables. The Swiss table design: SIMD metadata bytes, H1/H2 split, group probing. Released as absl::flat_hash_map.
12. Abseil. "Swiss Tables Design Notes" and the Abseil containers guide. abseil.io. Documents the H1/H2 split (a 57-bit H1 and "a single control bit and the 7 bit H2 hash") and the 87.5% max load factor.
13. Abseil. absl/container/internal/raw_hash_set.h and hashtable_control_bytes.h. github.com/abseil/abseil-cpp. The source for §8 and §11's implementation details: the group load is _mm_loadu_si128, deliberately unaligned; the SSE2 group is 16 wide while the AArch64 and portable groups are 8; probing advances by triangular numbers over whole groups; current code takes H2 from the top 7 bits of the hash; the 7/8 load factor leaves "an average of two empty slots per group"; and lookups prefetch the slot array, with a public prefetch(key).
14. Amanieu d'Antras et al. "hashbrown: Rust port of Google's SwissTable hash map." GitHub repository. github.com/rust-lang/hashbrown. Adopted as the backing implementation of Rust's standard HashMap since Rust 1.36 (2019), replacing the previous Robin Hood implementation.
15. Joaquín M López Muñoz. "Inside boost::unordered_flat_map." Bannalia, 2022. bannalia.blogspot.com. The contemporary flat map compared against Abseil in §12: groups of 15 buckets in a 16-byte metadata word, a max load factor of 0.875 the user cannot change, and an overflow byte that "removes the need to use tombstones".
16. Nathan Bronson, Xiao Shi. "Open-sourcing F14 for faster, more memory-efficient hash tables." Meta Engineering, 2019. engineering.fb.com. Named "because it filters 14 slots at once", with SSE2 or NEON filtering and a typical max load factor of 12/14. The F14 design doc in the Folly repository describes the one-byte tags. A third group width alongside Abseil's 16-or-8 and Boost's 15.
17. CPython. Objects/dictobject.c. github.com/python/cpython. The perturb recurrence quoted in §6: "perturb >>= PERTURB_SHIFT; j = (5*j) + 1 + perturb", with PERTURB_SHIFT = 5. The shift is what folds the high hash bits into the probe sequence.
18. OpenJDK. java.util.HashMap. github.com/openjdk/jdk. Supports the Java figures in §4 and §10: default load factor 0.75, doubling on resize, and the spreading function h ^ (h >>> 16).
19. Salvatore Sanfilippo et al. "Redis source: dict.c." GitHub repository. github.com/redis/redis/blob/unstable/src/dict.c. Incremental rehashing implementation: two hash tables, one-bucket-at-a-time migration during regular operations, rehashidx progress tracking, and lookups that skip the old table's already-migrated buckets.
20. Epic Games. "TMap." Unreal Engine documentation. dev.epicgames.com/documentation/unreal-engine/map-containers. Documents TMap's TPair elements, its sparse-array base, GetTypeHash customization, set allocators that choose the bucket count, the undefined behavior of modifying a key in place, and TMap's standing as the most used container after TArray.
21. Paul Pedriana et al. "EASTL: Electronic Arts Standard Template Library." N2271, ISO/IEC JTC1/SC22/WG21, 2007. open-std.org/jtc1/sc22/wg21/docs/papers/2007/n2271.html. See also: github.com/electronicarts/EASTL. The design paper and open-source release of EA's game-oriented STL replacement, including hash_map and fixed_hash_map.
22. Electronic Arts. EASTL include/EASTL/internal/hashtable.h. github.com/electronicarts/EASTL. The bucket layout cited in §12: node_type** mpBucketArray over singly-linked hash_node chains, with an optional cached hash code. No entry is inlined into a bucket slot.
23. Peter Norvig. "Teach Yourself Programming in Ten Years," approximate timing table. norvig.com/21-days.html. Memory-hierarchy latency ballparks: L1 ~0.5 ns, L2 ~7 ns, DRAM ~100 ns. Used for the per-miss costs in §1 and §4.
24. Martín Farach-Colton, Andrew Krapivin, William Kuszmaul. "Optimal Bounds for Open Addressing Without Reordering." arXiv:2501.02305, FOCS 2025. arxiv.org. The 2025 result discussed in §14: elastic hashing (non-greedy, O(1) amortized) and funnel hashing (greedy, O(log² δ^-1) worst case), in an insert-only setting measured in probes, with a note that bounds like these are impossible once deletions run over an unbounded horizon.
25. Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein. Introduction to Algorithms, 4th ed. MIT Press, 2022. ISBN 9780262046305. mitpress.mit.edu/9780262046305. Chapter 11 covers hash tables, chaining, open addressing, and the SUHA analysis.
26. Abseil. absl/container/internal/raw_hash_set.h and raw_hash_set.cc. github.com/abseil/abseil-cpp. The implementation behind §9: WasNeverFull in raw_hash_set.cc decides whether an erase writes kEmpty or kDeleted by testing whether the run of non-empty control bytes spanning the slot is shorter than one group width, and the growth-capacity comment in raw_hash_set.h states why tombstones still force a rehash. The control-byte values in §8 (kEmpty = -128, kDeleted = -2, kSentinel = -1) are in hashtable_control_bytes.h.
27. Bevy. bevy_ecs/src/entity/hash.rs. github.com/bevyengine/bevy. EntityHasher: keeps the entity index in the low bits for H1, multiplies by a golden-ratio constant to fill the high bits hashbrown uses for H2, and documents the cases (indices that are multiples of 256, mostly dead generations) where a general-purpose hash does better.