Build Lab: Open-Addressed Robin Hood Hash Table with Tombstone-Free Backward Shift Deletion

Architecture & Invariant Specifications

Our implementation guarantees four structural invariants across every insert, find, erase, and rehash operation:

1. Power-of-Two Capacity ($m = 2^r$) with SplitMix64 Finalizer: Every key is mixed through a 64-bit SplitMix64 avalanche permutation so both high and low bits have full entropy, and bucket indexing uses a single bitwise AND idx = hash & (m - 1).
2. 1-Based Distance-from-Initial-Bucket (dib = psl + 1): Instead of storing both a bool occupied flag and a uint32_t psl counter, we store a single integer dib (Distance from Initial Bucket): dib == 0 denotes an EMPTY slot, while dib >= 1 denotes an occupied slot with $\text{PSL} = \text{dib} - 1$.
3. Robin Hood Swap Invariant (curr_dib > slot.dib): During insert, if an occupied slot has the same key, we update its value in-place; otherwise if curr_dib > slot.dib, the incoming entry steals the slot via std::swap and continues probing with the displaced entry.
4. Backward-Shift Deletion (erase): When deleting at idx, we inspect next = (idx + 1) & mask. While table[next].dib > 1 (meaning the occupant at next is occupied AND displaced from its home bucket, i.e., $\text{PSL} > 0$), we shift table[next] backward to table[idx] with dib - 1 and advance idx = next. Finally, we clear table[idx].dib = 0.

Visualizing End-to-End Insert, Early-Exit Find & Backward-Shift Erase

Complete Reference Implementation: RobinHoodMap<K, V> in C++20

// C++20: Complete Open-Addressed Robin Hood Hash Table with Tombstone-Free Backward Shift
#include <vector>
#include <cstdint>
#include <optional>
#include <utility>
#include <algorithm>

template <typename K, typename V>
class RobinHoodMap {
    struct Slot {
        K key{};
        V val{};
        uint32_t dib = 0; // 0 = EMPTY, >= 1 means PSL = dib - 1
    };

    std::vector<Slot> table_;
    size_t size_ = 0;

    static uint64_t hashKey(const K& k) noexcept {
        uint64_t x = static_cast<uint64_t>(std::hash<K>{}(k));
        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{});
        size_ = 0;
        for (auto& s : old) {
            if (s.dib > 0) insert(std::move(s.key), std::move(s.val));
        }
    }

public:
    explicit RobinHoodMap(size_t initialPow2Cap = 16) : table_(initialPow2Cap) {}

    size_t size() const noexcept { return size_; }

    bool insert(K key, V val) {
        // Resize at 85% load factor (17/20)
        if ((size_ + 1) * 20 >= table_.size() * 17) {
            rehash(table_.size() * 2);
        }
        const size_t mask = table_.size() - 1;
        size_t idx = hashKey(key) & mask;
        uint32_t curDib = 1;

        while (true) {
            Slot& s = table_[idx];
            if (s.dib == 0) {
                s.key = std::move(key);
                s.val = std::move(val);
                s.dib = curDib;
                ++size_;
                return true;
            }
            if (s.dib == curDib && s.key == key) {
                s.val = std::move(val); // Update existing key in-place
                return false;
            }
            // Robin Hood Rule: steal slot if incoming key has larger DIB than occupant
            if (curDib > s.dib) {
                std::swap(key, s.key);
                std::swap(val, s.val);
                std::swap(curDib, s.dib);
            }
            idx = (idx + 1) & mask;
            ++curDib;
        }
    }

    std::optional<V> find(const K& key) const {
        const size_t mask = table_.size() - 1;
        size_t idx = hashKey(key) & mask;
        uint32_t curDib = 1;

        while (true) {
            const Slot& s = table_[idx];
            // Early-exit invariant: if slot is empty OR occupant is richer, key cannot exist
            if (s.dib < curDib) return std::nullopt;
            if (s.dib == curDib && s.key == key) return s.val;
            idx = (idx + 1) & mask;
            ++curDib;
        }
    }

    bool erase(const K& key) {
        const size_t mask = table_.size() - 1;
        size_t idx = hashKey(key) & mask;
        uint32_t curDib = 1;

        while (true) {
            Slot& s = table_[idx];
            if (s.dib < curDib) return false; // Key not found
            if (s.dib == curDib && s.key == key) break; // Located target at idx
            idx = (idx + 1) & mask;
            ++curDib;
        }

        // Tombstone-free backward shift deletion
        size_t next = (idx + 1) & mask;
        while (table_[next].dib > 1) {
            table_[idx] = std::move(table_[next]);
            --table_[idx].dib;
            idx = next;
            next = (next + 1) & mask;
        }
        table_[idx] = Slot{};
        --size_;
        return true;
    }

    uint32_t maxPsl() const noexcept {
        uint32_t maxD = 1;
        for (const auto& s : table_) maxD = std::max(maxD, s.dib);
        return maxD - 1;
    }
};