Flat Sets and Linear Probing

In the previous lesson, we saw that the C++ standard library's std::unordered_set and std::unordered_map uses a technique called separate chaining to resolve hash collisions. When two keys hash to the same bucket, it allocates a new linked list node on the heap and chains them together.

This pointer-chasing architecture hurts our CPU's cache locality. Every lookup is a roll of the dice that frequently ends in a pipeline stall while the processor waits to fetch a scattered node from main memory.

To solve this, we have to ditch the linked list. We are going to build a flat set, relying on a data-oriented technique known as open addressing.

The core philosophy of a flat set is simple: no external nodes. Every piece of data we care about must live directly inside a single, tightly packed array.

Instead of an array of pointers, we allocate an array of Slot structs. Each slot will hold the actual Key we are storing, alongside a small state variable to tell us if the slot is currently in use. We'll be adding a third state soon, so we'll use an Enum for this rather than a bool:

1#pragma once
2#include <vector>
3#include <cstdint>
4
5class FlatHashSet {
6  enum class CellState : uint8_t {
7    Empty,
8    Occupied
9  };
10
11  struct Slot {
12    int Key{0};
13    CellState State{CellState::Empty};
14  
15    // If we were making a hash map instead of a set, 
16    // we would put the payload in this struct, too:
17    // PayloadType Payload;
18  };
19
20private:
21  std::vector<Slot> Buffer;
22  size_t Capacity{16};
23  size_t Mask{15};
24  size_t Size{0};
25
Mix64 Function|Show
26  uint64_t Mix64(uint64_t x) const {/*...*/}
35
36public:
37  // Initialize our contiguous block of memory
38  FlatHashSet() : Buffer(Capacity) {}
39};

Because our Slot struct contains a 4-byte integer and a 1-byte enum, alignment padding will round its size up to 8 bytes. When we ask the CPU to look at Buffer[0], it doesn't just fetch one slot; the memory controller pulls in the entire cache line - usually a 64-byte chunk.

This means we also get the next 7 slots loaded into the cache, completely for free. This will be useful for our linear probing.

By forcing everything into a flat array, we still have to handle collisions. If "Apple" hashes to index 5, and "Mango" also hashes to index 5, where do we put "Mango"?

For a flat map, the answer is simple. We check index 5. If it's occupied, we take one step to the right and check index 6. If index 6 is occupied, we check index 7. We continue walking linearly down the array until we find an Empty slot.

This mechanical shift is called linear probing:

1// ...
2class FlatHashSet {
3// ...
4public:
5  FlatHashSet() : Buffer(Capacity) {}
6
7  void Insert(int key) {
8    size_t Index{Mix64(key) & Mask};
9
10    while (true) {
11      Slot& Current{Buffer[Index]};
12
13      // If we find an empty slot, claim it!
14      if (Current.State == CellState::Empty) {
15        Current.Key = key;
16        Current.State = CellState::Occupied;
17        ++Size;
18        return;
19      }
20
21      // Prevent duplicate keys
22      if (
23        Current.State == CellState::Occupied &&
24        Current.Key == key
25      ) {
26        return;
27      }
28
29      // Step one slot to the right.
30      // The mask handles the wrap-around back to 0.
31      Index = (Index + 1) & Mask;
32    }
33  }
34};

At first glance, this while loop might seem slow, but as we've seen many times, iterating through slots of a contiguous array is much faster than dereferencing even a single pointer to the heap. Because of the 64-byte cache line, checking the next 6 slots requires zero trips to main RAM.

Furthermore, if the prefetcher detects us looping linearly through memory, it will proactively start streaming the next cache lines into the L1 cache before our while loop even asks for them.

Fast Lookups

To check if our container has a key, we execute the same walk.

We hash the query to get our starting index, and walk forward until we either find the key or we hit an Empty slot. If we hit an Empty slot, we know that the key does not exist, so we can end our search and return false.

1// ...
2class FlatHashSet {
3// ...
4public:
5  // ...
6  bool Contains(int key) const {
7    size_t Index{Mix64(key) & Mask};
8
9    while (true) {
10      const Slot& Current{Buffer[Index]};
11
12      // We hit a blank space. The chain is broken.
13      if (Current.State == CellState::Empty) {
14        return false;
15      }
16
17      if (
18        Current.State == CellState::Occupied &&
19        Current.Key == key
20      ) {
21        return true;
22      }
23
24      Index = (Index + 1) & Mask;
25    }
26  }
27};

We have one problem remaining: how can we implement deletion? We can't just reset the slot to Empty - that would break our Contains() function. Imagine the following sequence of events:

1. 42 hashes to index 5. It gets inserted there.
2. 99 hashes to index 5. It collides with 42, so it slides right and gets inserted at index 6.
3. We delete 42 from the set, resetting index 5 to Empty.

If we now call Contains(99), the function will hash to index 5. It will see that index 5 is Empty, and it will immediately return false.

To fix this, we cannot just wipe slots clean. We have to leave a tombstone behind. To do this, we can add a Dead state to our enum. When we delete an item, we simply mark it as Dead:

1// ...
2
3// ...
4class FlatHashSet {
5  enum class CellState : uint8_t {
6    Empty,
7    Occupied,
8    Dead 
9  };
10  // ...
11public:
12  // ...
13  void Erase(int key) {
14    size_t Index{Mix64(key) & Mask};
15
16    while (true) {
17      Slot& Current{Buffer[Index]};
18
19      // The key was never in the set
20      if (Current.State == CellState::Empty) return;
21
22      // We found it! Mark it dead, but leave the
23      // slot physically intact
24      if (
25        Current.State == CellState::Occupied &&
26        Current.Key == key
27      ) {
28        Current.State = CellState::Dead;
29        --Size;
30        return;
31      }
32
33      Index = (Index + 1) & Mask;
34    }
35  }
36};

Our Contains() loop will now skip over Dead slots and continue searching down the chain.

Recycling Dead Slots

If our array starts filling up with Dead slots, our probe chains will grow artificially long, and we'll eventually run out of space. We should actively reuse Dead slots when inserting new keys, so let's update our Insert() method.

If we wanted our container to support duplicate keys, this would be relatively straightforward - we'd just drop the key into the first Dead or Empty slot our linear probe finds.

But if we want to prevent duplicate keys, we cannot use the first Dead slot we find. We have to continue walking the chain until we hit an Empty slot to verify the key isn't already hiding further down the line as a duplicate:

1// ...
2#include <limits>
3
4// ...
5
6class FlatHashSet {
7private:
8  // ...
9  static constexpr size_t InvalidIndex{
10    std::numeric_limits<size_t>::max()
11  };
12  
13public:
14  void Insert(int key) {
15    size_t Index{Mix64(key) & Mask};
16
17    // Remember the first grave we walk over
18    size_t FirstDead{InvalidIndex}; 
19
20    while (true) {
21      Slot& Current{Buffer[Index]};
22
23      if (
24        Current.State == CellState::Occupied &&
25        Current.Key == key
26      ) {
27        return;
28      }
29
30      // Rememberthe first dead slot, but keep walking
31      if (Current.State == CellState::Dead) {
32        if (FirstDead == InvalidIndex) FirstDead = Index;
33      }
34
35      if (Current.State == CellState::Empty) {
36        // Use the dead slot if we found one,
37        // otherwise use this empty slot
38        size_t Target = (FirstDead != InvalidIndex)
39          ? FirstDead
40          : Index;
41
42        Buffer[Target].Key = key;
43        Buffer[Target].State = CellState::Occupied;
44        ++Size;
45        return;
46      }
47
48      Index = (Index + 1) & Mask;
49    }
50  }
51  // ...
52};

Because our flat set does not allocate external heap nodes, our Capacity is a hard physical limit. If we try to insert 16 items into an array of 16 slots, the array will become 100% full.

If the array is 100% full, there are no Empty slots left. Our while(true) loops will spin infinitely, completely locking up the CPU.

Even before we hit 100%, performance drops off a cliff. If the array is 95% full, massive, contiguous blocks of occupied memory will form. We call this primary clustering. An insertion might have to probe past 100 unrelated items just to find a single open space, effectively degrading our $O(1)$ lookup into an $O(N)$ linear scan.

The typical benchmark for open-addressed hash tables is to establish a maximum load factor of around 70%.

When the number of occupied slots (plus the number of Dead tombstones clogging up the pipeline) reaches 70% of our capacity, we should pause execution, allocate an array double the size, and rehash everything into it. Let's create a Grow() function to implement this:

1// ...
2class FlatHashSet {
3private:
4  // ...
5  size_t Tombstones{0}; 
6  
7  // ...
8
9  void Grow() {
10    size_t OldCapacity = Capacity;
11    std::vector<Slot> OldBuffer = std::move(Buffer);
12
13    // Double the capacity and recalculate the mask
14    Capacity *= 2;
15    Mask = Capacity - 1;
16    Buffer.assign(Capacity, Slot{});
17
18    // Reset our counters. Grow() will purge the graveyard
19    Size = 0;
20    Tombstones = 0;
21
22    // Physically re-insert only the Live slots
23    for (size_t i = 0; i < OldCapacity; ++i) {
24      if (OldBuffer[i].State == CellState::Occupied) {
25        Insert(OldBuffer[i].Key);
26      }
27    }
28  }
29  // ...
30};

Remember that we're using the bitwise mask trick, which requires our capacity to always be a power of 2. By doubling 16 to 32, 64, and so on, we guarantee the bitwise logic never breaks.

We now simply inject a load-factor check at the very beginning of our Insert() method:

1// ...
2class FlatHashSet {
3// ...
4public:
5  // ...
6  void Insert(int key) {
7    // If Live Data + Dead Data > 70% of Capacity, reallocate
8    if ((Size + Tombstones) >= (Capacity * 0.7f)) {
9      Grow();
10    }
11
12    // ...
13  }
14  // ...
15};

The Erase() method creates a new tombstone, so it should increment the Tombstones counter:

1// ...
2class FlatHashSet {
3// ...
4public:
5  void Erase(int key) {
6    // ...
7    if (
8      Current.State == CellState::Occupied &&
9      Current.Key == key
10    ) {
11      Current.State = CellState::Dead;
12      --Size;
13      ++Tombstones; 
14      return;
15    }
16    // ...
17  }
18};

Finally, Insert() should decrement the Tombstones counter if it's recycling a tombstone slot:

1// ...
2class FlatHashSet {
3// ...
4public:
5  void Insert(int key) {
6    // ...
7
8    while (true) {
9      // ...
10
11      if (Current.State == CellState::Empty) {
12        // ...
13        ++Size;
14        
15        // If we are replacing a tombstone, decrement the counter
16        if (Target == FirstDead) --Tombstones;
17        
18        return;
19      }
20
21      // ...
22    }
23  }
24};

We have written a lot of raw mechanical logic. Let's prove that the hardware prefers this over the standard library's pointer chains.

We will run a benchmark comparing std::unordered_set against our custom FlatHashSet. We'll populate both with 2,000,000 items, and blast them with batches of 1,000,000 randomized Contains() queries.

The lookup performance of a hash container can have different performance characteristics depending on "miss rate" - that is, what percentage of our Contains() calls are for a key that is not in the collection.

The following tests measure our performance at three different miss rates - 1%, 50%, and 99%:

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

1---------------------------------------
2Benchmark                           CPU
3---------------------------------------
4BM_StdSet/MissRatePct:1         65.3 ms
5BM_StdSet/MissRatePct:50        76.4 ms
6BM_StdSet/MissRatePct:99        69.4 ms
7
8BM_FlatHashSet/MissRatePct:1    21.9 ms
9BM_FlatHashSet/MissRatePct:50   32.0 ms
10BM_FlatHashSet/MissRatePct:99   37.0 ms

Both containers use algorithms that would be classified as $O(1)$, but the physical constant factor of our simple FlatHashMap is already much faster than a highly optimized implementation of separate chaining.

We'll continue evolving our open addressing implementation in the next lesson, upgrading it to use Robin Hood hashing.

Pointer Stability

Remember, one of the key advantages of the secondary chaining approach is that it maintains pointer stability.

When we obtain a pointer or reference to a value inside a std::unordered_map, that pointer remains valid through insertions, removals, and even complete rehashes of the container.

Our FlatHashSet does not have this safety net. If we hand out a reference to FlatHashSet[5], and then someone calls Insert(), it might trigger a Grow(). The underlying vector will reallocate, the old memory block will be destroyed, and our system is now holding a dangling pointer.

In the next lesson, we'll switch out our linear probing for a Robin Hood strategy that trades away even more pointer stability for additional speed.

In these systems, we should generally pass values by copy, or develop a habit of always getting a fresh reference or pointer from the container rather than trying to save and reuse ones that can become stale.

Here is our complete FlatHashSet, using open addressing and linear probing:

In this lesson, we moved away from heap-allocated nodes and built a pure array-driven implementation.

By storing our data contiguously, we allowed the CPU's hardware prefetcher to do the heavy lifting, pulling entire sequences of probing slots into the L1 cache simultaneously. We handled deletions using Dead tombstones, and protected our query performance by enforcing a 70% load factor capacity.

Linear probing is fast, but it is highly susceptible to variance. If our array starts to cluster, one unlucky query might have to probe past 20 items before finding its target. In the next lesson, we will implement a clever swapping heuristic known as Robin Hood Hashing to forcibly smooth out this variance and keep our probe lengths short and efficient.