Robin Hood Hashing

Why Robin Hood Hashing Matters

A cache index may hold many keys close to their preferred slots while a few unlucky keys travel through long collision clusters. Those outliers make lookup costs uneven. Robin Hood Hashing changes who keeps a contested slot: the incoming key takes it if that key has already traveled farther than the resident.

This lesson uses Robin Hood linear probing. Keys advance one slot at a time, wrapping around the array. Each slot stores the key's distance from its home bucket, allowing insertion to compare displacement and an unsuccessful lookup to stop before reaching an empty slot in some cases. Backward-shift deletion preserves that lookup rule without tombstones.

You will trace a set of collisions, implement an exact integer set in Python, C++, and Java, and verify insertion, early termination, deletion, and growth. The sample also shows what “fairness” means: the displacement distribution improves, while the average successful-search cost in this particular comparison stays the same.

Core Concepts and Terminology

The input is a sequence of set operations on comparable keys. The runnable programs use signed $32$-bit integers. The set stores each member exactly once in an array of capacity $m$, with a separate representation for an empty slot. Zero and negative integers are ordinary keys, not empty markers.

A seeded hash function maps key $x$ to its home bucket $h(x)\in[0,m)$. Its linear probe sequence is

$$h(x),\ (h(x)+1)\bmod m,\ (h(x)+2)\bmod m,\ldots.$$

If $x$ occupies slot $j$, its distance from initial bucket, or DIB, is

$$\operatorname{DIB}(x,j)=(j-h(x)+m)\bmod m.$$

Distance counts moves, not probes: a key at home has DIB $0$ but needs one slot inspection for a successful lookup. The sample displays an occupied slot as key:dib. Empty slots have no meaningful DIB; the implementation resets their metadata to zero for clarity.

Let $n$ be the number of members and $\alpha=n/m$ the load factor. The code grows before a new insertion would exceed $3/4$ load, leaving empty space for a terminating probe sequence. This is a demonstration policy, not a universal optimum.

An important invariant is not that DIBs must be globally nondecreasing inside a cluster. For example, with homes $0,0,2$, a valid three-key layout can have DIBs $[0,1,0]$ in consecutive occupied slots. The drop simply starts a key at its own home.

The useful lookup invariant is more precise: for every stored key $x$ with DIB $d$, each earlier slot on its probe path at offset $t\lt d$ is occupied by a resident whose DIB is at least $t$. A search for $x$ therefore cannot encounter an empty slot or a smaller resident DIB before reaching $x$. This path-based statement supports early termination even when adjacent DIBs decrease.

How Robin Hood Hashing Works, Step by Step

Lookup. Start at the query key's home with query distance $d=0$. At each slot, return absent if it is empty; return present if its full key matches; otherwise return absent if resident DIB is smaller than $d$. If none applies, advance one slot circularly and increment $d$. The loop also has a capacity bound as a defensive guard.

Insertion. First look for the key so that a duplicate cannot be inserted or trigger unnecessary growth. If the new load would exceed $0.75$, build a doubled table and reinsert the old members. Then carry the new key with distance zero from its home:

1. If the current slot is empty, store the carried key and its distance, then finish.
2. If resident DIB is smaller than incoming distance, exchange both the keys and their distances. Count a steal.
3. Advance one slot and increment the distance of whichever key is now being carried.

The distance exchange in step $2$ is essential. An evicted key takes its own old DIB onward, not the larger distance of the key that replaced it. Its distance increases by one when it moves to the next slot.

flowchart TD
    A["Insert key"] --> B{"Already present?"}
    B -->|Yes| C["Return false"]
    B -->|No| D{"New load exceeds 0.75?"}
    D -->|Yes| E["Grow and reinsert all old keys"]
    D -->|No| F["Carry new key from home at distance 0"]
    E --> F
    F --> G{"Current slot empty?"}
    G -->|Yes| H["Store key and distance; increase size"]
    G -->|No| I{"Incoming distance greater than resident DIB?"}
    I -->|Yes| J["Swap keys and distances"]
    I -->|No| K["Advance circularly; increase carried distance"]
    J --> K
    K --> G

Deletion. Find the key using the same lookup rule. Treat its slot as a hole, then inspect the next slot. While that successor is occupied and has positive DIB, move it into the hole, reduce its DIB by one, and move the hole forward. Stop at an empty slot or a resident with DIB zero, then clear the final hole and decrease the size.

A resident at distance zero must stay at its home: shifting it backward would move it outside its permitted probe path. An empty slot also ends the repair. These stopping conditions keep searches valid and avoid accumulating tombstones. All operations here are single-threaded; during displacement or shifting, transient states are not suitable for unsynchronized readers.

Worked Example with a Full Trace

Use capacity $m=8$, seed $6$, and insertion order $[0,11,2,13,15]$. The generator supplies salt $100842$. With the code's integer mixer, the home buckets are

$$h(0)=0,\quad h(11)=1,\quad h(2)=2,\quad h(13)=0,\quad h(15)=0.$$

The first three keys go directly into their homes. The next two insertions create the interesting changes. The table records every insertion-slot inspection; duplicate-check lookup probes are separate and are not included in the printed insertion counter.

After all five insertions, slots $0$ through $4$ contain $[0:0,13:1,15:2,11:2,2:2]$ and the other slots are empty. There were $12$ insertion-slot inspections and $4$ steals. The load is $5/8$, so no growth was needed.

Ordinary first-come linear probing with the same homes and insertion order would place the keys as $[0:0,11:0,2:0,13:3,15:4]$. Its DIB values are $[0,0,0,3,4]$, compared with Robin Hood's $[0,1,2,2,2]$. Both sums are $7$, both mean DIBs are $7/5=1.4$, and both mean successful-search probe counts are $2.4$. Population DIB variance drops from $3.04$ to $0.64$, and maximum DIB drops from $4$ to $2$ on this example. Better balance is distinct from a lower mean.

Now insert $13$ again. Lookup finds it, so insertion returns false without changing size, layout, or statistics. Delete $13$ from slot $1$ and repair the hole:

The final layout is $[0:0,15:1,11:1,2:1,\mathrm{empty},\mathrm{empty},\mathrm{empty},\mathrm{empty}]$, with size $4$ and $3$ backward shifts. Keys $0,15,11,2$ remain reachable, and $13$ is absent.

Implementation in Python, C++, and Java

Each panel is a complete set implementation with add, contains, and remove. A new insertion returns true; a duplicate returns false. Removing an absent key returns false. The code maintains explicit occupancy so every signed $32$-bit key, including zero and the minimum negative value, can be represented.

For cross-language replay, a specified generator produces one salt at construction: $s\leftarrow16807s\bmod2147483647$, with seed $1\le s\le2147483646$. The same xor-shift mixer and wrapping multiplications modulo $2^{32}$ are then used in all three languages. Python masks the products, C++ uses uint32_t, and Java uses wrapping int arithmetic with unsigned right shifts and an unsigned conversion before the capacity reduction.

The salt remains fixed during growth; reinsertion recalculates every home modulo the new capacity. There is no per-insertion random choice. This seeded mixer is for transparent replay, not a proof that the hash homes satisfy an ideal random model or resist adversarial input.

Capacity must be at least $4$ and no greater than the configured maximum, which is capped at $1048576$ for this example. A new key that would exceed $3/4$ load requests doubled capacity. If that exceeds the maximum, insertion raises a capacity-limit error before changing the table or counters. Duplicates are checked before that guard, so a duplicate still returns false at the load ceiling.

insert_probes counts slot inspections by placement routines, including reinsertion during growth. It excludes the preliminary duplicate lookup. steals counts key-and-DIB exchanges, shifts counts deletion repair moves, and grows counts successful capacity doublings. Lookup probes are not included in these counters. The lower-level placement helper assumes a genuinely new key and at least one empty slot; public operations maintain those preconditions.

class RNG:
    def __init__(self, seed):
        if not isinstance(seed, int) or not 1 <= seed < 2147483647:
            raise ValueError("invalid seed")
        self.state, self.draws = seed, 0

    def next(self):
        self.state = (16807 * self.state) % 2147483647
        self.draws += 1
        return self.state


def index(key, salt, capacity):
    z = (key & 0xffffffff) ^ salt
    z ^= z >> 16
    z = (z * 0x7feb352d) & 0xffffffff
    z ^= z >> 15
    z = (z * 0x846ca68b) & 0xffffffff
    z ^= z >> 16
    return z % capacity


class Stats:
    def __init__(self):
        self.insert_probes = self.steals = self.shifts = self.grows = 0


class RobinHoodSet:
    def __init__(self, capacity=8, seed=6, max_capacity=1048576):
        if not 4 <= capacity <= max_capacity <= 1048576:
            raise ValueError("invalid capacity")
        self.rng = RNG(seed)
        self.salt = self.rng.next()
        self.m, self.size, self.max_capacity = capacity, 0, max_capacity
        self.keys, self.dib = [None] * capacity, [0] * capacity
        self.stats = Stats()

    def find(self, key):
        if not isinstance(key, int) or not -2147483648 <= key <= 2147483647:
            raise ValueError("key must be a signed 32-bit integer")
        j = index(key, self.salt, self.m)
        for distance in range(self.m):
            if self.keys[j] is None:
                return None
            if self.keys[j] == key:
                return j
            if self.dib[j] < distance:
                return None
            j = (j + 1) % self.m
        return None

    def contains(self, key):
        return self.find(key) is not None

    def place(self, keys, dib, capacity, key):
        j, distance = index(key, self.salt, capacity), 0
        for _ in range(capacity):
            self.stats.insert_probes += 1
            if keys[j] is None:
                keys[j], dib[j] = key, distance
                return
            if dib[j] < distance:
                keys[j], key = key, keys[j]
                dib[j], distance = distance, dib[j]
                self.stats.steals += 1
            j = (j + 1) % capacity
            distance += 1
        raise RuntimeError("internal placement precondition violated")

    def grow(self):
        capacity = 2 * self.m
        if capacity > self.max_capacity:
            raise RuntimeError("capacity limit reached; set unchanged")
        keys, dib = [None] * capacity, [0] * capacity
        for key in self.keys:
            if key is not None:
                self.place(keys, dib, capacity, key)
        self.keys, self.dib, self.m = keys, dib, capacity
        self.stats.grows += 1

    def add(self, key):
        if self.contains(key):
            return False
        if 4 * (self.size + 1) > 3 * self.m:
            self.grow()
        self.place(self.keys, self.dib, self.m, key)
        self.size += 1
        return True

    def remove(self, key):
        hole = self.find(key)
        if hole is None:
            return False
        nxt = (hole + 1) % self.m
        while self.keys[nxt] is not None and self.dib[nxt] > 0:
            self.keys[hole] = self.keys[nxt]
            self.dib[hole] = self.dib[nxt] - 1
            hole, nxt = nxt, (nxt + 1) % self.m
            self.stats.shifts += 1
        self.keys[hole], self.dib[hole] = None, 0
        self.size -= 1
        return True


def show(s):
    return "[" + ", ".join("_" if key is None else f"{key}:{s.dib[j]}"
                            for j, key in enumerate(s.keys)) + "]"


def main():
    s = RobinHoodSet()
    for key in [0, 11, 2, 13, 15]:
        s.add(key)
    print("before = " + show(s))
    duplicate = not s.add(13)
    erased = s.remove(13)
    print("after erase 13 = " + show(s))
    print(f"size={s.size}, capacity={s.m}")
    t = s.stats
    print(f"insert probes={t.insert_probes}, steals={t.steals}, shifts={t.shifts}, grows={t.grows}")
    print(f"hash draws = {s.rng.draws}")
    ok = duplicate and erased and s.size == 4 and not s.contains(13) and not s.contains(999)
    ok = all(s.contains(key) for key in [0, 11, 2, 15]) and ok
    print("checks = " + ("PASS" if ok else "FAIL"))


if __name__ == "__main__":
    main()

#include <cstdint>
#include <iostream>
#include <stdexcept>
#include <utility>
#include <vector>

struct RNG {
    std::int64_t state, draws = 0;
    explicit RNG(std::int64_t seed) : state(seed) {
        if (seed < 1 || seed >= 2147483647) throw std::invalid_argument("invalid seed");
    }
    std::uint32_t next() {
        state = (16807 * state) % 2147483647; ++draws;
        return static_cast<std::uint32_t>(state);
    }
};
int index(int key, std::uint32_t salt, int capacity) {
    std::uint32_t z = static_cast<std::uint32_t>(key) ^ salt;
    z ^= z >> 16; z *= 0x7feb352dU;
    z ^= z >> 15; z *= 0x846ca68bU;
    z ^= z >> 16;
    return static_cast<int>(z % static_cast<std::uint32_t>(capacity));
}
struct Slot { bool used = false; int key = 0, dib = 0; };
struct Stats { std::int64_t insert_probes = 0, steals = 0, shifts = 0, grows = 0; };
class RobinHoodSet {
public:
    RNG rng;
    std::uint32_t salt;
    int m, size = 0, max_capacity;
    std::vector<Slot> slots;
    Stats stats;
    explicit RobinHoodSet(int capacity = 8, std::int64_t seed = 6, int maximum = 1048576)
        : rng(seed), m(capacity), max_capacity(maximum) {
        if (capacity < 4 || capacity > maximum || maximum > 1048576)
            throw std::invalid_argument("invalid capacity");
        salt = rng.next(); slots.resize(capacity);
    }
    int find(int key) const {
        int j = index(key, salt, m);
        for (int distance = 0; distance < m; ++distance) {
            if (!slots[j].used) return -1;
            if (slots[j].key == key) return j;
            if (slots[j].dib < distance) return -1;
            j = (j + 1) % m;
        }
        return -1;
    }
    bool contains(int key) const { return find(key) != -1; }
    void place(std::vector<Slot>& target, int capacity, int key) {
        int j = index(key, salt, capacity), distance = 0;
        for (int step = 0; step < capacity; ++step) {
            ++stats.insert_probes;
            if (!target[j].used) {
                target[j].used = true; target[j].key = key; target[j].dib = distance; return;
            }
            if (target[j].dib < distance) {
                std::swap(target[j].key, key); std::swap(target[j].dib, distance); ++stats.steals;
            }
            j = (j + 1) % capacity; ++distance;
        }
        throw std::logic_error("internal placement precondition violated");
    }
    void grow() {
        int capacity = 2 * m;
        if (capacity > max_capacity) throw std::runtime_error("capacity limit reached; set unchanged");
        std::vector<Slot> trial(capacity);
        for (const auto& slot : slots) if (slot.used) place(trial, capacity, slot.key);
        slots = std::move(trial); m = capacity; ++stats.grows;
    }
    bool add(int key) {
        if (contains(key)) return false;
        if (4LL * (size + 1) > 3LL * m) grow();
        place(slots, m, key); ++size; return true;
    }
    bool remove(int key) {
        int hole = find(key); if (hole == -1) return false;
        int next = (hole + 1) % m;
        while (slots[next].used && slots[next].dib > 0) {
            slots[hole] = slots[next]; --slots[hole].dib;
            hole = next; next = (next + 1) % m; ++stats.shifts;
        }
        slots[hole].used = false; slots[hole].dib = 0; --size; return true;
    }
};
void show(const RobinHoodSet& s) {
    std::cout << '[';
    for (int j = 0; j < s.m; ++j) {
        if (j) std::cout << ", ";
        if (s.slots[j].used) std::cout << s.slots[j].key << ':' << s.slots[j].dib;
        else std::cout << '_';
    }
    std::cout << "]\n";
}
int main() {
    RobinHoodSet s;
    for (int key : {0, 11, 2, 13, 15}) s.add(key);
    std::cout << "before = "; show(s);
    bool duplicate = !s.add(13), erased = s.remove(13);
    std::cout << "after erase 13 = "; show(s);
    std::cout << "size=" << s.size << ", capacity=" << s.m << '\n';
    const Stats& t = s.stats;
    std::cout << "insert probes=" << t.insert_probes << ", steals=" << t.steals << ", shifts=" << t.shifts << ", grows=" << t.grows << '\n';
    std::cout << "hash draws = " << s.rng.draws << '\n';
    bool ok = duplicate && erased && s.size == 4 && !s.contains(13) && !s.contains(999);
    for (int key : {0, 11, 2, 15}) ok = s.contains(key) && ok;
    std::cout << "checks = " << (ok ? "PASS" : "FAIL") << '\n';
    return 0;
}

public class Main {
    static class RNG {
        long state, draws;
        RNG(long seed) {
            if (seed < 1 || seed >= 2147483647L) throw new IllegalArgumentException("invalid seed");
            state = seed;
        }
        int next() { state = (16807L * state) % 2147483647L; ++draws; return (int)state; }
    }
    static int index(int key, int salt, int capacity) {
        int z = key ^ salt;
        z ^= z >>> 16; z *= 0x7feb352d;
        z ^= z >>> 15; z *= 0x846ca68b;
        z ^= z >>> 16;
        return (int)(Integer.toUnsignedLong(z) % capacity);
    }
    static class Stats { long insertProbes, steals, shifts, grows; }
    static class RobinHoodSet {
        final RNG rng;
        final int salt;
        int m, size, maxCapacity;
        Integer[] keys;
        int[] dib;
        final Stats stats = new Stats();
        RobinHoodSet(int capacity, long seed, int maximum) {
            if (capacity < 4 || capacity > maximum || maximum > 1048576)
                throw new IllegalArgumentException("invalid capacity");
            rng = new RNG(seed); salt = rng.next(); m = capacity; maxCapacity = maximum;
            keys = new Integer[capacity]; dib = new int[capacity];
        }
        int find(int key) {
            int j = index(key, salt, m);
            for (int distance = 0; distance < m; ++distance) {
                if (keys[j] == null) return -1;
                if (keys[j] == key) return j;
                if (dib[j] < distance) return -1;
                j = (j + 1) % m;
            }
            return -1;
        }
        boolean contains(int key) { return find(key) != -1; }
        void place(Integer[] target, int[] distances, int capacity, int key) {
            int j = index(key, salt, capacity), distance = 0;
            for (int step = 0; step < capacity; ++step) {
                ++stats.insertProbes;
                if (target[j] == null) { target[j] = key; distances[j] = distance; return; }
                if (distances[j] < distance) {
                    int oldKey = target[j], oldDistance = distances[j];
                    target[j] = key; distances[j] = distance; key = oldKey; distance = oldDistance; ++stats.steals;
                }
                j = (j + 1) % capacity; ++distance;
            }
            throw new IllegalStateException("internal placement precondition violated");
        }
        void grow() {
            int capacity = 2 * m;
            if (capacity > maxCapacity) throw new IllegalStateException("capacity limit reached; set unchanged");
            Integer[] trial = new Integer[capacity]; int[] trialDib = new int[capacity];
            for (Integer key : keys) if (key != null) place(trial, trialDib, capacity, key);
            keys = trial; dib = trialDib; m = capacity; ++stats.grows;
        }
        boolean add(int key) {
            if (contains(key)) return false;
            if (4L * (size + 1) > 3L * m) grow();
            place(keys, dib, m, key); ++size; return true;
        }
        boolean remove(int key) {
            int hole = find(key); if (hole == -1) return false;
            int next = (hole + 1) % m;
            while (keys[next] != null && dib[next] > 0) {
                keys[hole] = keys[next]; dib[hole] = dib[next] - 1;
                hole = next; next = (next + 1) % m; ++stats.shifts;
            }
            keys[hole] = null; dib[hole] = 0; --size; return true;
        }
    }
    static String show(RobinHoodSet s) {
        StringBuilder out = new StringBuilder("[");
        for (int j = 0; j < s.m; ++j) {
            if (j != 0) out.append(", ");
            if (s.keys[j] == null) out.append('_'); else out.append(s.keys[j]).append(':').append(s.dib[j]);
        }
        return out.append(']').toString();
    }
    public static void main(String[] args) {
        RobinHoodSet s = new RobinHoodSet(8, 6, 1048576);
        int[] input = {0, 11, 2, 13, 15}; for (int key : input) s.add(key);
        System.out.println("before = " + show(s));
        boolean duplicate = !s.add(13), erased = s.remove(13);
        System.out.println("after erase 13 = " + show(s));
        System.out.println("size=" + s.size + ", capacity=" + s.m);
        Stats t = s.stats;
        System.out.println("insert probes=" + t.insertProbes + ", steals=" + t.steals + ", shifts=" + t.shifts + ", grows=" + t.grows);
        System.out.println("hash draws = " + s.rng.draws);
        boolean ok = duplicate && erased && s.size == 4 && !s.contains(13) && !s.contains(999);
        int[] remaining = {0, 11, 2, 15}; for (int key : remaining) ok = s.contains(key) && ok;
        System.out.println("checks = " + (ok ? "PASS" : "FAIL"));
    }
}

Use Python 3, C++14 or later, or Java 17 or later. Compile C++ with g++ -std=c++14 -O2 main.cpp -o robin; compile and run Java with javac Main.java and java Main. All three programs print these six lines:

• before = [0:0, 13:1, 15:2, 11:2, 2:2, _, _, _]
• after erase 13 = [0:0, 15:1, 11:1, 2:1, _, _, _, _]
• size=4, capacity=8
• insert probes=12, steals=4, shifts=3, grows=0
• hash draws = 1
• checks = PASS

The output before deletion makes the insertion statistics independently checkable, and the final check confirms duplicate detection, deletion, remaining members, and an absent key. A stronger test should scan every stored key and DIB, compare operations with an independent reference set, and include wrapped clusters and growth.

Complexity, Correctness, and Invariants

For fixed-size keys and constant-cost hashing, successful or unsuccessful lookup can take constant time in the best case. At a fixed load bounded below $1$, sufficiently well-distributed hash homes give constant expected probe costs; the constants depend on load. The same expectation supports amortized constant insertion with geometric growth. These are distributional claims, not worst-case guarantees for the fixed public mixer.

At fixed capacity, a search or insertion may traverse a cluster containing all $n$ members, and deletion may shift almost all of it. Their worst-case time is $O(n+1)$, with matching linear examples for nontrivial $n$. Each ordinary operation uses $O(1)$ auxiliary state. The table and its metadata use $\Theta(m)$ storage and are not automatically shrunk after deletion.

Growth allocates a new array, scans the old capacity, and reinserts the old keys. Its expected cost is $O(m+n)$ under suitable hashing, but the actual reinsertion routine can take $O(n^2)$ time on an adversarial collision pattern. A growth operation therefore has deterministic upper bound $O(m+n^2)$ in this code, with $O(m)$ additional table storage during doubling. When growth is triggered by the load ceiling, $m$ and $n$ are proportional. Calling every resize worst-case linear would ignore the reinsertion cost.

Correctness has three parts. First, the metadata of every resident must equal its circular distance from home. Second, the resident keys must be exactly the set's members, with no duplicates. Third, the lookup-path invariant must hold: before a stored key at distance $d$, each earlier offset $t$ encounters a resident with DIB at least $t$.

Insertion preserves these properties because a pending key passes a resident only when resident DIB is at least its own current distance. Otherwise it takes that slot, and the displaced key carries its own distance forward. Raising a resident DIB by a steal cannot make an existing search terminate earlier at that slot. When an empty slot is reached, all members are resident again and the size increases once.

Backward shifting moves a successor one step closer to its own home, so its DIB must decrease by exactly one. To see why it remains safe for other searches, consider a query that would have passed the hole before reaching a later member. At the successor slot its old query distance was one greater; the lookup invariant required the successor's DIB to be at least that distance. Moving the successor backward and subtracting one preserves the required inequality at the hole.

If the successor is at home, its DIB is zero. No remaining member can require a search path to cross the hole and that zero-DIB successor: such a path would already violate the lookup invariant at the successor. Repair may therefore stop there. An empty successor similarly marks the end of any continuing probe path. These arguments also apply when the hole advances from slot $m-1$ to slot $0$.

All scans are bounded. The public load policy guarantees an empty slot before ordinary placement; linear probing advances the slot on every iteration, so placement reaches an empty slot within one circuit. Lookup additionally stops on an early certificate, and deletion advances its hole until the next empty slot or zero-DIB resident.

Variants, Pitfalls, and Optimizations

Simply clearing a deleted slot is unsafe. In the sample, clearing slot $1$ after deleting $13$ would make a search for $15$ stop there as absent, even though $15$ remained at slot $2$. The three backward shifts move the surviving keys closer to home and leave the final hole at a safe stopping boundary.

Other implementation decisions have distinct consequences:

• Move metadata with the key. A steal exchanges the pending and resident DIBs as well as their keys. Increment only the distance of the key being carried to the next slot. A deletion shift decrements the moved key's DIB, and a resize recomputes it from scratch.
• Use the correct early-stop inequality. Stop when resident DIB is strictly smaller than query distance. Equality is not an absence certificate: a later colliding key can still be found after passing a tied resident. Keep the full-key equality check as well.
• Handle wraparound in every operation. Advance by $(j+1)\bmod m$, and interpret DIB circularly. A cluster beginning near the end of the array can continue at its beginning; deletion must repair across the same boundary.
• Do not assume sorted DIBs. The valid sequence $[0,1,0]$ is a counterexample. Test the lookup-path invariant and exact metadata instead of rejecting every decrease.
• Do not transplant tombstones casually. A tombstone design needs its own search and insertion rules. Treating a tombstone as empty loses keys, while reusing its stale DIB with the early-stop rule can also be wrong. This implementation uses backward shifting throughout.
• Control load and displacement ranges. Higher utilization increases cluster lengths even with a good hash. A compact DIB field can overflow on a long cluster; grow, widen it, or provide an explicit fallback rather than wrapping metadata silently. The sample uses ordinary integer distances at a bounded capacity.
• Generalize records carefully. A map must move keys and values together. Insertion, deletion, and growth can relocate elements, so pointers and iterators into a flat table may be invalidated. Concurrent operations require an appropriate relocation protocol.

Robin Hood placement does not prevent primary clustering, and fairness is not a promise that every operation performs less work than ordinary linear probing. Track mean, variance, maximum distance, lookup probes, insertion moves, and deletion shifts separately. The original Robin Hood literature also studies probing and search models beyond this simple linear scan; guarantees for those models should not be imported without checking their assumptions.

For long strings, hashing and key comparison have costs depending on length. For hostile input, the example's fixed deterministic mixer is not an adversarial performance defense. Its purpose is to make layout and counters exactly reproducible while the dictionary invariants remain directly testable.

Practice Problems and Real-World Use

Compare every public operation with an independent reference set. After each operation, verify multiplicities and size, recompute each resident's DIB from its home and slot, and check every earlier offset on its lookup path. Query absent keys as well as members so that an incorrect early-stop rule cannot hide behind successful lookups alone.

Include empty tables, duplicate insertion, absent deletion, repeated insert/delete cycles, zero and extreme integers, long shared-home clusters, a zero-DIB stopping boundary, wrapping at the last slot, growth, and a capacity-limit failure that leaves the prior state unchanged. For small tables, enumerate many assigned home patterns and insertion orders; this tests the displacement policy independently of one chosen hash function.

For further study, Pedro Celis's Robin Hood Hashing thesis develops the original idea and analysis. Stanford's hash-table assignment provides exercises on Robin Hood insertion, early lookup termination, and backward-shift deletion. Use those discussions alongside an explicit probing model and the concrete invariants above.