Variance Reduction: Robin Hood Hashing (PSL) & Cuckoo Hashing

Robin Hood Hashing: PSL Monotonicity & Tombstone-Free Deletion

For any key $k$ currently stored at index $i$ in a linear-probed table of size $m$, define its Probe Sequence Length (PSL) (also called Displacement Ideal Distance, DIB) as its modular distance from its home bucket:

$$\text{PSL}(k, i) = (i - h(k)) \bmod m$$

During insert(k), we track curr_psl = 0 starting at idx = h(k). At each occupied slot idx, we compare curr_psl against occupant_psl. Whenever curr_psl > occupant_psl, we swap the incoming key with the occupant and continue probing with the displaced occupant. This maintains two powerful invariants:

• Early-Exit Lookup Bound: Because keys along any contiguous cluster are ordered monotonically by their home buckets, if a lookup for target reaches a slot where search_psl > occupant_psl, target cannot exist anywhere further in the table—if it did, it would have stolen occupant's slot during insertion! Thus unsuccessful searches terminate early without scanning to an EMPTY slot.
• Tombstone-Free Backward-Shift Deletion: Instead of leaving a TOMBSTONE when deleting slot idx, Robin Hood inspects next = (idx + 1) % m. While table[next] is occupied and has PSL > 0, it shifts table[next] backward into table[idx] (decrementing its PSL by 1) and advances idx = next. Once it encounters an EMPTY slot or a key sitting at its home bucket (PSL == 0), it marks table[idx] = EMPTY, keeping the table 100% free of tombstones forever.

Cuckoo Hashing: Bipartite Eviction Graphs

In Cuckoo Hashing, two tables $T_1, T_2$ of size $m$ (or one table of size $2m$) use independent hash functions $h_1, h_2$. Every key $x$ resides exclusively at $T_1[h_1(x)]$ or $T_2[h_2(x)]$. Lookups and deletions check only those two slots in parallel—requiring at most 2 cache line reads in the worst case.

To insert $x$, if $T_1[h_1(x)]$ is occupied by $y$, we place $x$ at $T_1[h_1(x)]$ and evict $y$ to its alternate home $T_2[h_2(y)]$, chaining evictions up to $\text{MaxLoop} = lceil 6 \log_{1/(2\alpha)} n \rceil$ steps before triggering a rehash with fresh hash seeds.

Visualizing Robin Hood PSL Swapping & Cuckoo Eviction Cycles

Production C++20 Implementation: Cuckoo Hash Table with Unicyclic Eviction Loop

// C++20: 2-Table Cuckoo Hash Map with Worst-Case 2-Probe Lookup & Cycle Detection
#include <vector>
#include <cstdint>
#include <optional>
#include <utility>

template <typename V>
class CuckooHashMap {
    struct Entry {
        uint64_t key = 0;
        V val{};
        bool occupied = false;
    };

    std::vector<Entry> t1_, t2_;
    size_t count_ = 0;
    uint64_t seed1_ = 0x9e3779b97f4a7c15ULL;
    uint64_t seed2_ = 0xbf58476d1ce4e5b9ULL;
    static constexpr size_t MAX_KICKS = 64;

    size_t h1(uint64_t k) const noexcept {
        k ^= seed1_; k *= 0xff51afd7ed558ccdULL;
        return (k ^ (k >> 33)) & (t1_.size() - 1);
    }
    size_t h2(uint64_t k) const noexcept {
        k ^= seed2_; k *= 0xc4ceb9fe1a85ec53ULL;
        return (k ^ (k >> 33)) & (t2_.size() - 1);
    }

    void rehash(size_t newHalfCap) {
        auto old1 = std::move(t1_);
        auto old2 = std::move(t2_);
        t1_.assign(newHalfCap, Entry{});
        t2_.assign(newHalfCap, Entry{});
        seed1_ = seed1_ * 6364136223846793005ULL + 1442695040888963407ULL;
        seed2_ = seed2_ * 2862933555777941757ULL + 3037000493ULL;
        count_ = 0;
        for (auto& e : old1) if (e.occupied) insert(e.key, std::move(e.val));
        for (auto& e : old2) if (e.occupied) insert(e.key, std::move(e.val));
    }

public:
    explicit CuckooHashMap(size_t pow2HalfCap = 16) : t1_(pow2HalfCap), t2_(pow2HalfCap) {}

    // Strict O(1) Worst-Case Lookup: Exactly 2 independent array reads
    std::optional<V> find(uint64_t key) const noexcept {
        const Entry& e1 = t1_[h1(key)];
        const Entry& e2 = t2_[h2(key)];
        if (e1.occupied && e1.key == key) return e1.val;
        if (e2.occupied && e2.key == key) return e2.val;
        return std::nullopt;
    }

    void insert(uint64_t key, V val) {
        if (Entry& e1 = t1_[h1(key)]; e1.occupied && e1.key == key) { e1.val = std::move(val); return; }
        if (Entry& e2 = t2_[h2(key)]; e2.occupied && e2.key == key) { e2.val = std::move(val); return; }

        if ((count_ + 1) * 5 >= (t1_.size() + t2_.size()) * 2) { // Keep load factor < 0.40
            rehash(t1_.size() * 2);
        }

        Entry cur{key, std::move(val), true};
        for (size_t kick = 0; kick < MAX_KICKS; ++kick) {
            Entry& slot1 = t1_[h1(cur.key)];
            if (!slot1.occupied) { slot1 = std::move(cur); ++count_; return; }
            std::swap(cur, slot1);

            Entry& slot2 = t2_[h2(cur.key)];
            if (!slot2.occupied) { slot2 = std::move(cur); ++count_; return; }
            std::swap(cur, slot2);
        }
        // Bicyclic component detected: rehash with new seeds and re-insert displaced cur
        rehash(t1_.size() * 2);
        insert(cur.key, std::move(cur.val));
    }
};