Collision Resolution: Separate Chaining vs Linear/Quadratic/Double Probing

Separate Chaining vs Open Addressing Probe Sequences

Define the load factor $\alpha = n / m$, where $n$ is the number of stored elements and $m$ is the number of bucket slots:

• Separate Chaining ($alpha$ can exceed $1$): Each slot stores a pointer to a linked list (or small inline vector) of colliding entries. Under uniform hashing, an unsuccessful search inspects $\alpha$ nodes and a successful search inspects $1 + \alpha/2$ nodes on average. However, every node allocation incurs malloc overhead (16 bytes) + an 8-byte next pointer, and traversing a chain dereferences non-contiguous heap addresses (L3/DRAM cache misses).
• Linear Probing ($h(k, i) = (h(k) + i) \bmod m$): Probes adjacent slots sequentially. Maximizes spatial locality and hardware stream prefetching, but suffers from primary clustering: any key hashing anywhere inside a contiguous cluster of length $L$ extends that cluster to $L + 1$ with probability $(L + 1)/m$.
• Quadratic Probing ($h(k, i) = (h(k) + c_1 i + c_2 i^2) \bmod m$): Eliminates primary clustering by jumping quadratically, leaving only milder secondary clustering (keys with the exact same initial $h(k)$ follow the same trajectory). When $m = 2^r$ and $c_1 = c_2 = 1/2$, the triangular numbers $h(k, i) = (h(k) + i(i+1)/2) \bmod 2^r$ are guaranteed to visit every slot in $\{0, \dots, 2^r - 1\}$ exactly once!
• Double Hashing ($h(k, i) = (h_1(k) + i \cdot h_2(k)) \bmod m$): Uses a second independent hash $h_2(k)$ coprime to $m$ (e.g., $h_2(k)$ odd when $m = 2^r$, or $h_2(k) \in [1, m-1]$ when $m$ is prime). Generates $m^2$ distinct probe sequences, eliminating both primary and secondary clustering at the cost of a new cache miss on nearly every probe step.

Visualizing Primary Clustering & Tombstone Accumulation

The SVG diagram below illustrates how a contiguous cluster of 4 elements in Linear Probing captures any hash landing in slots $[2..6]$ (probability $5/m$), and how replacing slot $3$ with a TOMBSTONE preserves the search bridge to keys shifted to slots $4$ and $5$.

Production C++20 Implementation: Power-of-Two Triangular Quadratic Probing

// C++20: Open-Addressed Hash Table with Triangular Quadratic Probing & Tombstone Rehash
#include <vector>
#include <cstdint>
#include <optional>

template <typename K, typename V>
class TriangularProbeMap {
    enum class State : uint8_t { EMPTY = 0, OCCUPIED = 1, TOMBSTONE = 2 };
    struct Slot {
        K key{};
        V val{};
        State state = State::EMPTY;
    };

    std::vector<Slot> table_;
    size_t live_ = 0;
    size_t tombs_ = 0;

    static uint64_t hash64(uint64_t x) noexcept {
        x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9ULL;
        x = (x ^ (x >> 27)) * 0x94d049bb133111ebULL;
        return x ^ (x >> 31);
    }

    void rehash(size_t newCap) {
        std::vector<Slot> old = std::move(table_);
        table_.assign(newCap, Slot{});
        live_ = 0;
        tombs_ = 0;
        for (auto& s : old) {
            if (s.state == State::OCCUPIED) insert(std::move(s.key), std::move(s.val));
        }
    }

public:
    explicit TriangularProbeMap(size_t pow2Cap = 16) : table_(pow2Cap) {}

    bool insert(K key, V val) {
        // Trigger resize or same-size tombstone cleanup when occupied + tombstones >= 75%
        if ((live_ + tombs_) * 4 >= table_.size() * 3) {
            size_t nextCap = (live_ * 2 >= table_.size()) ? table_.size() * 2 : table_.size();
            rehash(nextCap);
        }
        const size_t mask = table_.size() - 1;
        size_t idx = hash64(static_cast<uint64_t>(key)) & mask;
        size_t firstTomb = static_cast<size_t>(-1);

        for (size_t step = 1; ; ++step) {
            Slot& s = table_[idx];
            if (s.state == State::EMPTY) {
                Slot& target = (firstTomb != static_cast<size_t>(-1))
                               ? (--tombs_, table_[firstTomb]) : s;
                target.key = std::move(key);
                target.val = std::move(val);
                target.state = State::OCCUPIED;
                ++live_;
                return true;
            }
            if (s.state == State::TOMBSTONE) {
                if (firstTomb == static_cast<size_t>(-1)) firstTomb = idx;
            } else if (s.key == key) {
                s.val = std::move(val);
                return false;
            }
            // Triangular step: idx_{i} = (idx_{i-1} + step) mod 2^r visits all 2^r slots!
            idx = (idx + step) & mask;
        }
    }

    std::optional<V> find(const K& key) const {
        const size_t mask = table_.size() - 1;
        size_t idx = hash64(static_cast<uint64_t>(key)) & mask;
        for (size_t step = 1; ; ++step) {
            const Slot& s = table_[idx];
            if (s.state == State::EMPTY) return std::nullopt;
            if (s.state == State::OCCUPIED && s.key == key) return s.val;
            idx = (idx + step) & mask;
        }
    }
};