Robin Hood Hashing

In our previous lesson, we built a FlatHashSet using simple linear probing. By ditching the linked lists, the CPU's hardware prefetcher happily sucked our contiguous array into the L1 cache, granting us a massive performance boost.

However, linear probing has a major flaw: variance. In real-time systems, audio processing, or high-frequency trading, average performance doesn't matter if our worst-case performance causes a dropped frame or a missed trade. Our basic linear probe works when the array is mostly empty, but as it fills up, it becomes unpredictable.

In this lesson, we will introduce a heuristic called Robin Hood Hashing. We are going to reorder the data as it lands in memory, smoothing out the variance and guaranteeing more predictable, bounded search times.

To understand why we need a new algorithm, we should observe how linear probing degrades.

Imagine an array that is 80% full. Hash functions distribute data randomly, which isn't quite the same as distributing it evenly. In a random distribution, some areas of our array will be relatively empty, whilst some areas will have large clusters of contiguous keys.

We call this primary clustering, and it can snowball out of control.

If a new key hashes to an index that happens to land in the middle of a 15-slot cluster, it has to walk all the way to the end of that cluster to find an Empty slot.

Finding a free slot at the end of a large cluster is slow and, even worse, it then makes the cluster even larger by claiming that slot. Future hashes are now more likely to land somewhere in that cluster, our insertion algorithm will take even longer to find its way to the end of it, and will then make the cluster larger once again.

If a query requires 15 probes, it is no longer an $O(1)$ lookup. It has degraded into an $O(N)$ linear scan. Probing past 15 elements also means we have stepped outside of our initial 64-byte L1 cache line, forcing the CPU to stall while it fetches another cache line from main memory.

We need a way to keep our clusters small, or at least ensure that no single element is pushed unreasonably far from its starting point.

To fix this, we need to track exactly how far an element has wandered from where it wanted to be. We call this the Distance from Initial Bucket, or DIB.

If a key hashes to index 5, and it gets inserted into index 5, its DIB is 0. A DIB of 0 is perfect - it means the element is exactly where it wants to be.

If index 5 was occupied, and the key had to slot into index 6 instead, its DIB is 1. If 6 was also taken, it would move into slot 7 and it's DIB would become 2.

Let's update our Slot struct to store this new metric. Because a DIB of 255 is practically impossible in any properly sized hash table, a single 1-byte integer is more than enough:

1#pragma once
2#include <vector>
3#include <cstdint>
4#include <algorithm>
5
6class RobinHoodSet {
7  enum class CellState : uint8_t {
8    Empty,
9    Occupied
10  };
11
12  struct Slot {
13    int Key{0};
14    uint8_t DIB{0}; 
15    CellState State{CellState::Empty};
16  };
17};

Let's construct our new RobinHoodSet using the same fundamental array architecture as our previous FlatHashSet, carrying over our Mix64() hash function.

1// ...
2
3class RobinHoodSet {
4// ...
5private:
6  size_t Capacity{16};
7  size_t Mask{15};
8  size_t Size{0};
9  std::vector<Slot> Buffer;
10
Mix64 Function|Show
11  uint64_t Mix64(uint64_t x) const {/*...*/}
20
21public:
22  RobinHoodSet() : Buffer(Capacity) {}
23};

With our DIB metric in place, we can implement the core mechanic of Robin Hood hashing: stealing from the rich to give to the poor. In this context:

• A "rich" element is sitting very close to its optimal bucket (a low DIB).
• A "poor" element has been forced to walk a long distance (a high DIB).

The goal of Robin Hood hashing is not necessarily to reduce the average DIB - it is to reduce the variance in the DIB. This makes our probing lengths more consistent:

When we insert a new key, we track its current DIB as we walk down the probe chain. If our incoming key ever encounters a sitting element that has a lower DIB than our incoming key's current DIB, we steal its slot and give it to the new key.

We then pick up the evicted element and continue walking through the array to find a new slot for it.

In the following example, we want to add 92 to our container, but we get unlucky as this hashes to the start of a cluster of occupied slots.

In a simple linear probing strategy, our 92 would get inserted into the end of this cluster and have a relatively painful DIB of 4. But with Robin Hood hashing, we share some pain to drop its DIB to 2:

This continuous juggling acts as a smoothing function. It prevents any single key from suffering a 15-slot probe sequence. Instead of one key walking 15 slots, the algorithm distributes the pain, trying to make every object's distance from its initial bucket approximately equal.

Let's write the Insert() method. We will use std::swap() to juggle the Key and the DIB simultaneously.

1// ...
2class RobinHoodSet {
3// ...
4public:
5  void Insert(int key) {
6    // Basic load factor protection
7    if (Size >= (Capacity * 0.7f)) {
8      Grow(); // We'll implement this later
9    }
10
11    size_t Index{Mix64(key) & Mask};
12
13    // We package our incoming data into a temporary Slot
14    Slot Incoming{key, 0, CellState::Occupied};
15
16    while (true) {
17      Slot& Current{Buffer[Index]};
18
19      // We found a completely empty space, drop it in
20      if (Current.State == CellState::Empty) {
21        Current = Incoming;
22        ++Size;
23        return;
24      }
25
26      if (Current.Key == Incoming.Key) {
27        return; // Duplicate check
28      }
29
30      // Robin Hood Swap: Steal from the rich
31      if (Incoming.DIB > Current.DIB) {
32        std::swap(Incoming.Key, Current.Key);
33        std::swap(Incoming.DIB, Current.DIB);
34      }
35
36      // We didn't swap, or we just became the evicted element.
37      // Either way, we must keep walking.
38      Index = (Index + 1) & Mask;
39      Incoming.DIB++;
40    }
41  }
42  // ...
43};

By packaging our key and DIB into a temporary Incoming slot, the std::swap() logic becomes simple. The CPU simply exchanges the contents of its local registers with the main memory array, and the loop continues as if nothing happened, blindly carrying the newly evicted victim forward.

Distributing the variance is great for cache predictability, but the DIB heuristic gives us an even bigger performance superpower: the early exit.

In standard linear probing, a search query must walk the array until it finds the key or hits an Empty slot. If the array is heavily clustered, a search for a key that doesn't exist (a miss) might have to walk through 15 occupied slots before finally hitting an empty space and returning false.

Misses are incredibly expensive in standard open addressing.

With Robin Hood hashing, our array is ordered by DIB variance. If we are searching for a key, and our current search distance is 3, but we look at the array and see an element with a DIB of 1, we can instantly stop searching.

Why? Because if our target key was actually in the container, it would stolen this slot. Its DIB of 3 would have caused the element with a DIB of 1 to be evicted.

The physical mechanics of our Insert() method guarantee that a key can never sit behind an element that is richer than it.

1// ...
2class RobinHoodSet {
3// ...
4public:
5  // ...
6  bool Contains(int key) const {
7    size_t Index{Mix64(key) & Mask};
8    uint8_t SearchDIB{0};
9
10    while (true) {
11      const Slot& Current{Buffer[Index]};
12
13      // Miss: We hit an empty space
14      if (Current.State == CellState::Empty) return false;
15
16      // Hit: We found the key!
17      if (Current.Key == key) return true;
18
19      // Early Exit Miss: We are poorer than the sitting element!
20      if (SearchDIB > Current.DIB) {
21        return false;
22      }
23
24      Index = (Index + 1) & Mask;
25      SearchDIB++;
26    }
27  }
28  // ...
29};

This simple if statement fundamentally changes the performance profile of the container. Negative queries (misses) no longer have to traverse the entire cluster. They terminate almost instantly, often within the very first L1 cache line fetch.

In the previous lesson, we solved deletions by leaving a Dead tombstone in the array. This was necessary because a standard Empty slot would prematurely terminate the Contains() probe chain for any elements that collided and shifted past it.

Tombstones artificially inflate our load factor, forcing our Insert() loop to walk further, and triggering expensive Grow() reallocations long before our container is physically full.

Because Robin Hood hashing tracks the exact DIB of every element, we can perform a highly optimized Backward Shift deletion, eradicating tombstones from our architecture.

When we want to delete an element, we don't mark it Dead. We wipe it to Empty.

Then, we look at the element immediately to its right. If that element has a DIB above 0, meaning it is shifted away from its ideal bucket, we drag it backward into our newly vacated slot and decrement its DIB. We then look at the next element and repeat the process.

We stop shifting backward the moment we encounter an Empty slot, or an element with a DIB == 0, meaning it is sitting exactly where it wants to be.

1// ...
2class RobinHoodSet {
3// ...
4public:
5  // ...
6  void Erase(int key) {
7    size_t Index{Mix64(key) & Mask};
8    uint8_t SearchDIB{0};
9
10    while (true) {
11      Slot& Current{Buffer[Index]};
12
13      // Misses
14      if (Current.State == CellState::Empty) return;
15      if (SearchDIB > Current.DIB) return;
16
17      // We found the target to delete!
18      if (Current.Key == key) {
19        ShiftBackward(Index); 
20        --Size;
21        return;
22      }
23
24      Index = (Index + 1) & Mask;
25      SearchDIB++;
26    }
27  }
28  // ...
29};

The ShiftBackward() helper function handles the mechanical cleanup. It acts like a vacuum, sucking the cluster backward to perfectly seal the gap, maintaining perfect cache locality.

1// ...
2class RobinHoodSet {
3private:
4  // ...
5  void ShiftBackward(size_t Index) {
6    while (true) {
7      size_t NextIndex{(Index + 1) & Mask};
8      Slot& NextSlot{Buffer[NextIndex]};
9
10      // If the next slot is empty, or sitting exactly
11      // where it wants to be (DIB == 0), we stop shifting.
12      if (NextSlot.State == CellState::Empty || NextSlot.DIB == 0) {
13        Buffer[Index].State = State::Empty;
14        return;
15      }
16
17      // Drag the next element backward into our current gap
18      Buffer[Index] = NextSlot;
19      Buffer[Index].DIB--;
20
21      // Move our gap pointer forward
22      Index = NextIndex;
23    }
24  }
25  // ...
26};

By eliminating tombstones, we guarantee that our array only contains pristine, live data. This ensures our probe lengths stay as short as physically possible and delays expensive heap reallocations as long as possible.

The Grow() Method

Finally, because we no longer have a Tombstone counter or Dead state to worry about, our reallocation logic is simplified. We iterate through the old array and feed any Occupied slots directly into our Insert() logic.

1// ...
2class RobinHoodSet {
3private:
4  // ...
5  void Grow() {
6    size_t OldCapacity{Capacity};
7    std::vector<Slot> OldBuffer{std::move(Buffer)};
8
9    Capacity *= 2;
10    Mask = Capacity - 1;
11    Buffer.assign(Capacity, Slot{});
12    Size = 0;
13
14    // Physically re-insert data into the new, larger memory block
15    for (size_t i = 0; i < OldCapacity; ++i) {
16      if (OldBuffer[i].State == CellState::Occupied) {
17        Insert(OldBuffer[i].Key);
18      }
19    }
20  }
21  // ...
22};

The main strength of Robin Hood Hashing is not that it makes the average lookup speed faster. In fact, the average is sometimes slower as checking and updating the DIB values adds complexity that doesn't exist in a basic linear probing implementation.

The benefit of Robin Hood Hashing is that it reduces the variance of our lookup speeds. By robbing from the rich to give to the poor, our elements' distance from their preferred bucket is much more consistent.

Robin Hood hashing is particularly effective in miss-heavy scenarios - that is, where Contains() will usually return false. This is thanks to the DIB tracking unlocking the early exit strategy we implemented above.

Let's add our RobinHoodSet to the benchmarks we created in the previous lesson, which test our containers at 1%, 50%, and 99% miss rates. They insert 2,000,000 randomized elements into each set and run 1,000,000 randomized queries on each test iteration:

1#include <benchmark/benchmark.h>
2#include <unordered_set>
3#include <vector>
4#include <random>
5#include <algorithm>
6#include <dsa/FlatHashSet.h>
7#include <dsa/RobinHoodSet.h>
8
9const int kNumElements = 2'000'000;
10const int kNumQueries = 1'000'000;
11
12std::vector<int> GenerateData() {
13  std::vector<int> data(kNumElements);
14  std::mt19937 rng(42);
15
16  std::uniform_int_distribution<int> dist(1, 50'000'000); 
17  for (int i = 0; i < kNumElements; ++i) data[i] = dist(rng);
18  return data;
19}
20
21const std::vector<int> Data = GenerateData();
22
23std::vector<int> GenerateQueries(double miss_rate) {
24  std::vector<int> queries;
25  queries.reserve(kNumQueries);
26
27  int misses = kNumQueries * miss_rate;
28  int hits = kNumQueries - misses;
29  
30  for (int i = 0; i < hits; ++i) {
31    queries.push_back(Data[i]);
32  }
33  
34  // Misses (completely out of the insertion bounds)
35  for (int i = 0; i < misses; ++i) {
36    queries.push_back(i + 100'000'000); 
37  }
38  
39  std::mt19937 rng(42);
40  std::shuffle(queries.begin(), queries.end(), rng);
41  
42  return queries;
43}
44
45static void BM_StdSet(benchmark::State& state) {
46  double miss_rate = state.range(0) / 100.0;
47  
48  std::vector<int> queries = GenerateQueries(miss_rate);
49  std::unordered_set<int> set(Data.begin(), Data.end());
50  
51  for (auto _ : state) {
52    for (int query : queries) {
53      benchmark::DoNotOptimize(set.contains(query)); 
54    }
55  }
56}
57
58static void BM_FlatHashSet(benchmark::State& state) {
59  double miss_rate = state.range(0) / 100.0;
60  std::vector<int> queries = GenerateQueries(miss_rate);
61  
62  FlatHashSet set;
63  for (int val : Data) set.Insert(val);
64  
65  for (auto _ : state) {
66    for (int query : queries) {
67      benchmark::DoNotOptimize(set.Contains(query));
68    }
69  }
70}
71
72static void BM_RobinHood(benchmark::State& state) {
73  double miss_rate = state.range(0) / 100.0;
74  std::vector<int> queries = GenerateQueries(miss_rate);
75  
76  RobinHoodSet set;
77  for (int val : Data) set.Insert(val);
78  
79  for (auto _ : state) {
80    for (int query : queries) {
81      benchmark::DoNotOptimize(set.Contains(query));
82    }
83  }
84}
85
86#define REGISTER_BENCHMARK(func) BENCHMARK(func) \
87  ->Unit(benchmark::kMillisecond) \
88  ->ArgName("MissRatePct") \
89  ->Arg(1) \
90  ->Arg(50) \
91  ->Arg(99)
92
93REGISTER_BENCHMARK(BM_StdSet);
94REGISTER_BENCHMARK(BM_FlatHashSet);
95REGISTER_BENCHMARK(BM_RobinHood);

1---------------------------------------
2Benchmark                           CPU
3---------------------------------------
4BM_StdSet/MissRatePct:1         61.1 ms
5BM_StdSet/MissRatePct:50        74.7 ms
6BM_StdSet/MissRatePct:99        67.0 ms
7
8BM_FlatHashSet/MissRatePct:1    20.1 ms
9BM_FlatHashSet/MissRatePct:50   28.2 ms
10BM_FlatHashSet/MissRatePct:99   31.7 ms
11
12BM_RobinHood/MissRatePct:1      23.0 ms
13BM_RobinHood/MissRatePct:50     29.2 ms
14BM_RobinHood/MissRatePct:99     28.5 ms

Open addressing's primary clustering problem has other solutions too, most notably quadratic probing and double hashing. Rather than placing a colliding element in the next adjacent slot, both techniques probe more distant slots when the preferred bucket is taken. This reduces clustering, but at the cost of cache locality and prefetcher-friendliness.

Robin Hood hashing dominated high-performance implementations throughout the last decade and remains popular today, but recent hardware advancements have changed the balance of power. Modern CPUs offer wide vector registers capable of comparing 16 elements in parallel within a single instruction, which unlocks some new possibilities.

In the next chapter, we'll use these new hardware capabilities to introduce the new king of hash table design: the Swiss Table.

Here is our complete RobinHoodSet example:

In this lesson, we tackled the variance of linear probing by tracking the Distance from Initial Bucket (DIB) and swapping elements on the fly.

This architecture eliminated Dead tombstones via backward shifting, kept our cache lines packed with relevant data, and unlocked the early exit mechanic to quickly reject invalid queries.

So far, we've been using basic integers as our keys, but in real use cases, we often need our keys to be strings. In the next lesson, we'll introduce the problems this creates and how we can solve them.