Hash tables: open addressing

std::unordered_map is a chained hash table: an array of buckets, each pointing to a linked list of heap-allocated nodes. That design gives stable references, but it costs an allocation per insert and a pointer chase per lookup. Most high-performance hash tables (Abseil's flat_hash_map, Boost's unordered_flat_map, Rust's HashMap) use open addressing instead: the entries live in one flat array, and a collision is resolved by trying other slots of the same array.

This lesson builds one, and the interesting parts aren't the happy path. They are the three things that quietly turn O(1) into O(n): a hash whose low bits don't vary, a load factor that's allowed to creep towards 1, and deletion.

1. Slots, home slots, and the mask

Keep the slot count a power of two, cap = 2^b. Then a hash value picks a slot with one AND: hash & (cap - 1) keeps the low b bits. That slot is the key's home.

std::hash<int> in libstdc++ is the identity function, so the home slot of an integer is just its low bits. That's fine for keys 0, 1, 2, … and terrible for keys that share low bits — addresses, IDs that are multiples of a page size, timestamps rounded to milliseconds:

#include <cstdint>
#include <print>
#include <set>

// splitmix64's finalizer: every input bit affects every output bit.
std::uint64_t mix(std::uint64_t x) {
    x ^= x >> 30;
    x *= 0xbf58476d1ce4e5b9ULL;
    x ^= x >> 27;
    x *= 0x94d049bb133111ebULL;
    x ^= x >> 31;
    return x;
}

int main() {
    const std::uint64_t mask = 1024 - 1;      // 1024 slots
    std::set<std::uint64_t> raw, mixed;
    for (std::uint64_t i = 0; i < 1000; ++i) {
        std::uint64_t key = i * 4096;         // e.g. page-aligned addresses
        raw.insert(key & mask);
        mixed.insert(mix(key) & mask);
    }
    std::println("distinct home slots, raw hash:   {}", raw.size());
    std::println("distinct home slots, mixed hash: {}", mixed.size());
}

With the raw hash, a thousand keys share one home slot. A table can't fix a hash that throws information away, but it can refuse to trust the low bits: mix the hash, then mask. A finalizer like the one above costs a few cycles and makes the table robust to lazy hash functions.

2. Linear probing

On a collision, try the next slot, then the next (wrapping around), until you find the key or an empty slot. That's linear probing. Its great virtue is locality: a probe sequence walks consecutive memory, usually within a cache line or two.

Worked example — a minimal set of ints:

#include <cstddef>
#include <optional>
#include <print>
#include <vector>

class IntSet {
public:
    explicit IntSet(std::size_t cap) : slots_(cap) {}   // cap: a power of two

    bool insert(int key) {
        std::size_t i = home(key);
        while (slots_[i]) {                     // walk the cluster
            if (*slots_[i] == key) return false;
            i = (i + 1) & mask();               // wrap around
        }
        slots_[i] = key;                        // first empty slot
        return true;
    }

    bool contains(int key) const {
        for (std::size_t i = home(key); slots_[i]; i = (i + 1) & mask())
            if (*slots_[i] == key) return true;
        return false;                           // empty slot: not here
    }

private:
    std::vector<std::optional<int>> slots_;
    std::size_t mask() const { return slots_.size() - 1; }
    std::size_t home(int key) const { return static_cast<std::size_t>(key) & mask(); }
};

int main() {
    IntSet s(8);
    for (int k : {13, 21, 6, 29}) s.insert(k);   // 13, 21, 29 all have home 5
    std::println("{} {} {}", s.contains(21), s.contains(29), s.contains(37));
}

contains stops at the first empty slot. That's only correct because of an invariant worth stating precisely:

Every entry is reachable from its home slot without crossing an empty slot.

Insert maintains it trivially (it fills the first empty slot on the path). Deletion is where it gets broken — §4.

(This toy set has no growth; it would loop forever once full. A real table never lets that happen: §3.)

3. Load factor and growth

The load factor α = size / capacity. With linear probing and a good hash, the expected number of probes (Knuth) is about:

So keep α bounded — ¾ is a common choice for linear probing; SIMD-probed tables go to ⅞. When an insert would cross the limit, double the capacity and re-insert every entry at its new home (the mask changed, so homes changed). Doubling makes growth amortized O(1) per insert, for exactly the same reason as std::vector: the total rehashing work is a geometric series.

Growing by a constant (+64 slots) instead means rehashing every 48 or so inserts — O(n²) for n inserts.

4. Deletion without breaking chains

The obvious erase — find the slot, empty it — is wrong:

#include <cstddef>
#include <optional>
#include <print>
#include <vector>

int main() {
    // Homes: 13 → 5, 21 → 5, 29 → 5. Linear probing put them in slots 5, 6, 7.
    std::vector<std::optional<int>> slots(8);
    slots[5] = 13;
    slots[6] = 21;
    slots[7] = 29;

    slots[6].reset();   // naive erase of 21

    // Look up 29: start at its home (5), stop at the first empty slot.
    bool found = false;
    for (std::size_t i = 5; slots[i]; i = (i + 1) & 7)
        if (*slots[i] == 29) found = true;
    std::println("29 found after erasing 21? {}", found);
}

The hole at slot 6 cut 29 off from its home. Two standard fixes:

Tombstones. Mark the slot deleted instead of empty. Lookups skip tombstones; inserts may reuse them. Simple, but tombstones occupy slots: they lengthen probe sequences until a rehash removes them, so they must count towards the load factor (or be cleaned up some other way).

Backward-shift deletion. Empty the slot, then repair the cluster: walk forward from the hole; any entry whose probe path passes through the hole moves back into it, and its old slot becomes the new hole. Stop at the first empty slot. No tombstones, ever.

When does the entry at j (home k) pass through the hole at i? When i lies cyclically in [k, j) — equivalently, when the distance from k to j is at least the distance from i to j.

Faded example — your turn

Fill in the condition, using & mask() for cyclic distances:

slots_[i].reset();
for (std::size_t j = (i + 1) & mask(); slots_[j]; j = (j + 1) & mask()) {
    std::size_t k = home(slots_[j]->first);
    if (/* the hole i lies on the probe path from k to j */) {
        slots_[i] = std::move(slots_[j]);
        slots_[j].reset();
        i = j;
    }
}

5. Other probe sequences

Quadratic probing visits home + 1, home + 3, home + 6, … (triangular numbers). With a power-of-two capacity this still visits every slot exactly once, and it breaks up the long runs ("primary clustering") that linear probing forms — at the price of cache locality:

#include <cstddef>
#include <print>
#include <vector>

int main() {
    const std::size_t cap = 16, mask = cap - 1;
    std::vector<bool> seen(cap);
    std::size_t i = 3, visited = 0;
    for (std::size_t step = 0; step < cap; ++step) {
        if (!seen[i]) ++visited;
        seen[i] = true;
        i = (i + step + 1) & mask;    // offsets 1, 2, 3, … from the previous slot
    }
    std::println("distinct slots visited: {} of {}", visited, cap);
}

Robin Hood hashing (a preview — not needed here) is linear probing where an inserting entry that is further from its home than the occupant takes the slot and continues inserting the displaced one. It equalises probe lengths, lets misses stop early, and pairs naturally with backward-shift deletion.

6. Chaining, for contrast

std::unordered_map must give stable references: a pointer to an element stays valid across rehashes. That pretty much forces one heap node per entry:

#include <print>
#include <unordered_map>

int main() {
    std::unordered_map<int, int> m;
    m[1] = 10;
    int* p = &m[1];
    for (int i = 2; i < 1000; ++i) m[i] = i;   // many rehashes
    std::println("still {} via a pointer taken before {} rehashes",
                 *p, m.bucket_count() > 8 ? "several" : "no");
    std::println("max_load_factor: {}", m.max_load_factor());
}

The default max_load_factor is 1.0: chains let α exceed what open addressing could tolerate. Iterators are invalidated by a rehash, but pointers and references to elements are not.

A flat table gives that guarantee up — find's pointer is invalidated by the next insert that grows the table, or by an erase that shifts entries — in exchange for no per-entry allocation, better locality, and typically 2–4× faster lookups.

7. Adversarial inputs

Average O(1) assumes keys behave randomly with respect to the hash. An attacker who knows your hash can choose keys that all collide and turn every operation into O(n) ("hash flooding"). Defences: mix with a per-process random seed, or a keyed hash such as SipHash for untrusted input. Mixing with a fixed function, as here, defends against accidental patterns, not adversaries.

Summary

• Flat array of slots, power-of-two capacity, home = mix(hash) & (cap - 1).
• Linear probing: walk forward from home until the key or an empty slot.
• Invariant: every entry reachable from its home without crossing an empty slot.
• Keep α ≤ ¾ (or ⅞) and grow by doubling; rehash re-inserts everything.
• Delete with backward shift (or tombstones that count towards the load).
• Flat tables trade pointer stability for speed; std::unordered_map chains.