Swiss Table Memory Layout

In the previous lesson, we built SimdFindAll() using xsimd. By loading a contiguous block of int8_t bytes into a wide vector register, we compared 16 or 32 elements in a single clock cycle, extracted a bitmask of matches, and hopped directly to the matching indices using std::countr_zero().

Naturally, we want to point this hardware capability directly at the hash tables we built in the previous chapter. Instead of walking a linear probe chain one slot at a time, we want the CPU to inspect 16 or 32 hash table buckets in parallel.

But before we can vectorize our probing loop, we should rethink how a hash table is laid out in RAM. In this lesson, we will tear apart our open-addressed container and rebuild it using the Swiss Table architecture, which is the design behind Google Abseil's absl::flat_hash_map and the modern industry standard for high-performance hash tables.

This is a relatively complex lesson that reuses techniques we introduced in our previous chapter on hash-based containers. Reviewing those lessons is recommended if the topics covered here do not make sense, particularly the Flat Hash Set and Robin Hood Set implementations as the core algorithms - Insert(), Contains(), and Grow() - are very similar to what we walked through in those lessons.

In the previous chapter, we upgraded our basic FlatHashSet into a Robin Hood hash table

To prevent primary clustering from hurting our worst-case lookup times, we added a 1-byte DIB (Distance from Initial Bucket) counter to every slot.

This helped reduce the primary clustering problem - situations where a probe had to traverse 10 or more hash collisions before finding the requested key, or concluding the key wasn't in the container.

In scalar code, stepping through a probe chain of 10 slots meant executing 10 loop iterations, 10 key comparisons, 10 conditional checks with branch misprediction penalties.

However, as we've seen in previous lessons, the vector registers of modern hardware give us another option. We can load a bunch of slots into a vector register and check them all at once. Checking 16 or 32 values using SIMD isn't much slower than checking a single value using scalar code.

To build our Swiss Table, we will completely abandon the DIB counter, the Robin Hood swaps, and the backward-shift deletions. Instead, we'll lean into SIMD, creating algorithms and a memory layout optimized for these vector operations.

If we try to apply xsimd to our FlatHashSet or RobinHoodSet, we immediately hit a physical wall. Our previous hash tables arranged their memory as an array of structures. We had a Slot struct that stored our key value alongside whatever additional metadata our container required for each value:

1struct Slot {
2  // The values our hash set stores
3  int Key{0};
4    
5  // Metadata
6  CellState State{CellState::Empty};
7  
8  // We'd also need to store distance from initial
9  // bucket if we were using Robin Hood hashing
10  // uint8_t DIB{0};
11};

Our containers like FlatHashSet or RobinHoodSet were then managing an array of these structures:

1class FlatHashSet {
2  // ....
3  std::vector<Slot> Buffer;
4  // ...
5};

Even with a tiny 4-byte int key and a 1-byte CellState enum, the compiler inserts 3 bytes of alignment padding so that every int starts on a clean 4-byte memory boundary. Each Slot consumes 8 bytes of RAM, meaning a 64-byte L1 cache line holds only 8 slots.

Now consider what happens in a production system where our container stores more than just a single 4-byte integer. Imagine a hash set storing 32-byte std::string keys, or a hash map associating an 8-byte key with a 56-byte EnemyData payload struct:

1struct FatSlot {
2  uint64_t Key{0};         // 8 bytes
3  EnemyData Payload{};     // 56 bytes
4  CellState State{Empty};  // 1 byte (+ 7 bytes padding)
5};

Every FatSlot now consumes 72 bytes of memory. A single FatSlot no longer fits inside a 64-byte L1 cache line.

Think about what the CPU actually has to do when a collision occurs and our probing loop walks past 8 occupied slots. For the first 7 slots, the keys do not match our query. We only needed to inspect their metadata state and reject them.

However, because State, Key, and Payload are interleaved inside the same FatSlot struct, the memory controller is forced to haul all 72 bytes of every FatSlot from main RAM into the cache just to read a single metadata byte. Over 98% of our L1 cache capacity is polluted with EnemyData payloads we never even read.

Worse still, as we saw in our lesson on automatic vectorization , SIMD registers prefer contiguous lanes of identical types. We cannot efficiently load 16 CellState bytes into an xsimd::batch<int8_t> register when those bytes are separated by 71 bytes of keys and payloads in between.

To pack our metadata tightly for both the cache and our SIMD registers, we turn once again to data-oriented design and the structure of arrays (SoA) layout.

Instead of a single std::vector<Slot>, we split our hash table into two separate, parallel arrays of the same Capacity.

The first array is Metadata, a tightly packed buffer of 1-byte control values where Metadata[i] tracks the state of slot i. The second array is Keys, a parallel buffer where Keys[i] stores the key values our container is storing. It's also where we'd store the payload, if we were building a hash map rather than a set.

Because every element in Metadata is a single 1-byte int8_t, an entire 64-slot neighborhood of our hash table fits inside a single 64-byte cache line. Furthermore, because every element in Metadata is a 1-byte integer, the compiler inserts zero alignment padding between elements.

Let's create a new header file, SwissSet.h, and set up this dual-array skeleton alongside the usual Mix64() hash function we'll need later:

1#pragma once
2#include <vector>
3#include <cstdint>
4#include <cstddef>
5
6class SwissSet {
7private:
8  size_t Capacity{16};
9  size_t Mask{15};
10  size_t Size{0};
11  size_t Tombstones{0};
12
13  // SoA Split: 1-byte metadata separated from keys
14  std::vector<int8_t> Metadata;
15  std::vector<int> Keys;
16
17  uint64_t Mix64(uint64_t x) const {
18    x ^= x >> 30;
19    x *= 0xbf58476d1ce4e5b9ULL;
20    x ^= x >> 27;
21    x *= 0x94d049bb133111ebULL;
22    x ^= x >> 31;
23    return x;
24  }
25
26public:
27  SwissSet() : Metadata(Capacity), Keys(Capacity) {}
28};

Separating Metadata from Keys gives us a dense 1-byte array, but there is a catch. If Metadata[i] only told us whether slot i was Empty, Occupied, or Deleted, what would happen during a lookup when we hit an Occupied slot?

We would still have to jump over to Keys[i] in the second array to check if Keys[i] == key. If we have to fetch Keys[i] for every occupied slot in a cluster, touching two separate memory arrays on every probe step.

To avoid reading Keys[i] unless we are almost certain our target key is sitting there, we combine the hash caching technique and the 1-byte fingerprints from our Cuckoo Filter directly inside the Metadata byte.

In Swiss Table terminology, each int8_t in the Metadata array is called a control byte.

Designing the Control Byte

An int8_t has 8 bits. We need a single byte to represent both the lifecycle state of the slot (Empty, Deleted, or Occupied) and a hash fingerprint at the same time.

We accomplish this by dividing the 8 bits using the leftmost bit. This is the most significant bit in standard binary representations and, for signed integers like int8_t, represents the sign of the integer. When that bit is 1, the int8_t value is negative (-128 to -1).

We assign two specific negative values to represent our empty and tombstone states:

• kEmpty is -128 (binary 10000000), meaning the slot has never been used, and any probe chain that hits it can immediately terminate
• kDeleted is -2 (binary 11111110), representing a tombstone that probe chains must step over

When the leftmost bit is 0, the int8_t value is non-negative (0 to 127), which indicates that the slot is occupied.

In this state, the lower 7 bits (0xxxxxxx) store a 7-bit hash signature of the key sitting in Keys[i].

This bit-level layout gives the CPU three major mechanical advantages. First, there are zero wasted bits, because we pack both the state enum and a 7-bit hash fingerprint into the same byte.

Second, we get a single-instruction occupancy check. Because kEmpty (-128) and kDeleted (-2) are negative, and all valid 7-bit fingerprints (0 to 127) are non-negative; checking if any slot holds a live element is a simple Metadata[i] >= 0 comparison.

Third, we get direct signature matching. When searching for a key whose 7-bit signature is 42, we do not need to check if Metadata[i] is occupied first. We simply check if (Metadata[i] == 42).

Since 42 cannot equal -128 (kEmpty) or -2 (kDeleted), a single byte equality check tests both occupancy and the 7-bit hash fingerprint simultaneously.

H1/H2 Hash Splitting

To populate our control byte, we split our 64-bit hash from Mix64() into two independent values, typically called H1 and H2.

H1 uses the top 57 bits of the hash, which we can extract by shifting the 64-bit hash right by 7 bits: hash >> 7. The H1 value determines which bucket our probe should start when we're trying to add or read a value from our set.

Like with our previous containers, we can get this preferred bucket by applying our mask: H1(hash) & Mask.

H2 uses the bottom 7 bits of the hash, which we extract by performing hash & 0b01111111 (or hash & 0x7F). This isolates the lowest 7 bits and forces the 8th bit to 0, giving us our int8_t control byte signature in the range 0 to 127.

Because H2 is 7 bits wide, there are $2^7 = 128$ distinct signatures. When our probe loop walks past an occupied slot containing an unrelated key, there is a $127/128$ chance that its H2 byte will not match our target's H2 byte.

That means 99.22% of collisions are rejected directly inside the 1-byte Metadata array. The CPU rarely has to fetch from the Keys array until it lands on the exact slot containing our target key.

Let's add our Ctrl constants and the H1() and H2() helper methods to SwissSet, and initialize every slot in Metadata to Ctrl::kEmpty:

1#pragma once
2#include <vector>
3#include <cstdint>
4#include <cstddef>
5
6class SwissSet {
7  // Special negative control byte states (Bit 7 is 1)
8  struct Ctrl {
9    static constexpr int8_t kEmpty = -128;  // 0b10000000
10    static constexpr int8_t kDeleted = -2;  // 0b11111110
11  };
12
13private:
14  size_t Capacity{16};
15  size_t Mask{15};
16  size_t Size{0};
17  size_t Tombstones{0};
18
19  std::vector<int8_t> Metadata;
20  std::vector<int> Keys;
21
Mix64 Function|Show
22  uint64_t Mix64(uint64_t x) const {/*...*/}
31
32  // Top 57 bits: determines the starting bucket index
33  static size_t H1(uint64_t hash) {
34    return static_cast<size_t>(hash >> 7);
35  }
36
37  // Bottom 7 bits: stored in Metadata (always 0..127)
38  static int8_t H2(uint64_t hash) {
39    return static_cast<int8_t>(hash & 0x7F);
40  }
41
42public:
43  // Initialize all control bytes to kEmpty (-128)
44  SwissSet()
45    : Metadata(Capacity, Ctrl::kEmpty),
46      Keys(Capacity) {}
47};

Before we vectorize the probe loop in the next lesson, let's build the core lookup and insertion operations over our new SoA layout.

Implementing this scalar metadata probe first establishes the exact state transitions between Ctrl::kEmpty, Ctrl::kDeleted, and H2 signatures that our SIMD batch probing will operate on next.

It also allows us to benchmark and isolate how much performance comes purely from the SoA metadata split and 7-bit H2 filtering before SIMD instructions even enter the picture.

Implementing Contains()

When Contains(int key) is called, we hash the key once with Mix64(key), extract the starting bucket index using H1(hash) & Mask, and extract the 7-bit fingerprint using H2(hash).

We then walk the Metadata array starting at Index. At each slot, we load the 1-byte control value at Metadata[Index].

If ctrl == h2, the slot is occupied, and its 7-bit signature matches our query's H2. Only in this case do we reach into the Keys array to verify Keys[Index] == key. If the full keys match, we return true. If it was a 1-in-128 false positive, we continue probing.

If ctrl == kEmpty, we have reached an empty slot (-128). The probe chain is broken, so we immediately return false without ever touching the Keys array.

Otherwise, the slot is either a kDeleted tombstone or holds a different H2 signature, so we advance Index = (Index + 1) & Mask to inspect the next adjacent byte in Metadata:

1// ...
2class SwissSet {
3// ...
4public:
5  SwissSet()
6    : Metadata(Capacity, Ctrl::kEmpty),
7      Keys(Capacity) {}
8
9  bool Contains(int key) const {
10    uint64_t hash{Mix64(key)};
11    size_t Index{H1(hash) & Mask};
12    int8_t h2{H2(hash)};
13
14    while (true) {
15      int8_t ctrl{Metadata[Index]};
16
17      // Fast Path: 7-bit signature matches
18      // Only touch the Keys array on a signature hit
19      if (ctrl == h2) {
20        if (Keys[Index] == key) return true;
21      }
22
23      // Chain broken: key is not in the set
24      if (ctrl == Ctrl::kEmpty) {
25        return false;
26      }
27
28      Index = (Index + 1) & Mask;
29    }
30  }
31};

Implementing Insert() and Tombstone Recycling

Our Insert() logic follows the same tombstone-recycling strategy we built in the linear probing lesson, subtly adapted to operate on our split Metadata and Keys arrays.

As we walk the probe chain checking whether the key already exists in the set, we track the index of the first kDeleted tombstone we encounter using FirstDeleted. Just like in Contains(), we guard the duplicate key check behind if (ctrl == h2) so we never waste memory bandwidth reading Keys[Index] on unrelated slots.

Once the probe loop reaches a kEmpty slot, we know the key is not a duplicate. If FirstDeleted recorded a tombstone earlier in the chain, we recycle that slot and decrement Tombstones; otherwise, we claim the kEmpty slot at Index. We then write the 1-byte h2 signature into Metadata[Target] and the full key into Keys[Target]:

1// ...
2#include <limits> 
3
4class SwissSet {
5// ...
6private:
7  // ...
8  static constexpr size_t InvalidIndex{
9    std::numeric_limits<size_t>::max()
10  };
11
12public:
13  // ...
14  void Insert(int key) {
15    if ((Size + Tombstones) >= (Capacity * 0.7f)) {
16      Grow(); // We will implement Grow() shortly
17    }
18
19    uint64_t hash{Mix64(key)};
20    size_t Index{H1(hash) & Mask};
21    int8_t h2{H2(hash)};
22    size_t FirstDeleted{InvalidIndex};
23
24    while (true) {
25      int8_t ctrl{Metadata[Index]};
26
27      // Check for duplicates only when H2 matches
28      if (ctrl == h2 && Keys[Index] == key) {
29        return;
30      }
31
32      // Record the first tombstone we walk over
33      if (ctrl == Ctrl::kDeleted) {
34        if (FirstDeleted == InvalidIndex) {
35          FirstDeleted = Index;
36        }
37      }
38
39      if (ctrl == Ctrl::kEmpty) {
40        size_t Target = (FirstDeleted != InvalidIndex)
41          ? FirstDeleted
42          : Index;
43
44        Metadata[Target] = h2;
45        Keys[Target] = key;
46        ++Size;
47        if (Target == FirstDeleted) --Tombstones;
48        return;
49      }
50
51      Index = (Index + 1) & Mask;
52    }
53  }
54};

Because we dropped Robin Hood hashing's DIB tracking and backward-shift deletion, we cannot reset a deleted slot directly to Ctrl::kEmpty. Doing so would sever the probe chain for any elements that collided and shifted past that slot during earlier insertions.

Instead, Erase() uses our kDeleted (-2) tombstone state. We hash the target key, compute Index from H1(hash) and h2 from H2(hash), and walk the Metadata array.

If we encounter kEmpty, the key was never in the container, and we return immediately. If we find a slot where ctrl == h2 and Keys[Index] == key, we overwrite Metadata[Index] with kDeleted, decrement Size, and increment Tombstones.

Notice that for trivial key types like int, Erase() does not even need to modify Keys[Index] when deleting an element. Overwriting the 1-byte control value in Metadata[Index] with -2 immediately hides the stale key from future Contains() queries and marks the slot as available for reuse during future Insert() calls:

1// ...
2class SwissSet {
3// ...
4public:
5  // ...
6  void Erase(int key) {
7    uint64_t hash{Mix64(key)};
8    size_t Index{H1(hash) & Mask};
9    int8_t h2{H2(hash)};
10
11    while (true) {
12      int8_t ctrl{Metadata[Index]};
13
14      if (ctrl == Ctrl::kEmpty) return;
15
16      if (ctrl == h2 && Keys[Index] == key) {
17        Metadata[Index] = Ctrl::kDeleted;
18        --Size;
19        ++Tombstones;
20        return;
21      }
22
23      Index = (Index + 1) & Mask;
24    }
25  }
26};

As elements are inserted and erased, Size + Tombstones gradually approaches our load factor threshold. Even though Insert() recycles tombstones whenever it walks past them, tombstones still lengthen probe chains for negative queries because Contains() cannot stop until it hits a true kEmpty byte.

When Size + Tombstones reaches 70% of Capacity, we call Grow() to double the capacity of both parallel arrays, wipe away all accumulated tombstones, and rehash the live elements into fresh buckets.

Here, our signed int8_t control byte encoding simplifies the reallocation pass. How does Grow() know whether slot i in OldMetadata holds a live element versus kEmpty or kDeleted?

Because both special states have Bit 7 set to 1 (making them negative) and every valid 7-bit H2 signature has Bit 7 set to 0 (making it 0 to 127), Grow() simply checks if (OldMetadata[i] >= 0). Every live key is re-inserted into the newly resized arrays, while empty slots and dead tombstones are ignored:

1// ...
2class SwissSet {
3private:
4  // ...
5  void Grow() {
6    size_t OldCapacity{Capacity};
7    std::vector<int8_t> OldMetadata{std::move(Metadata)};
8    std::vector<int> OldKeys{std::move(Keys)};
9
10    Capacity *= 2;
11    Mask = Capacity - 1;
12
13    Metadata.assign(Capacity, Ctrl::kEmpty);
14    Keys.assign(Capacity, 0);
15
16    Size = 0;
17    Tombstones = 0;
18
19    for (size_t i{0}; i < OldCapacity; ++i) {
20      // Any non-negative control byte (0..127) is occupied
21      if (OldMetadata[i] >= 0) {
22        Insert(OldKeys[i]);
23      }
24    }
25  }
26
27public:
28  // ...
29};

Let's test our completed SwissSet in dsa_app/main.cpp to verify that insertions, lookups, and tombstone deletions work together properly:

1#include <iostream>
2#include <dsa/SwissSet.h>
3
4int main() {
5  SwissSet Set;
6
7  Set.Insert(42);
8  Set.Insert(99);
9  Set.Insert(150);
10
11  std::cout << "Contains 42? "
12    << (Set.Contains(42) ? "Yes" : "No") << "\n";
13
14  Set.Erase(42);
15
16  std::cout << "Contains 42 after erase? "
17    << (Set.Contains(42) ? "Yes" : "No") << "\n";
18
19  std::cout << "Contains 99 after erase? "
20    << (Set.Contains(99) ? "Yes" : "No");
21}

1Contains 42? Yes
2Contains 42 after erase? No
3Contains 99 after erase? Yes

We have not written a single line of SIMD code inside SwissSet yet. Our while loops are still stepping through Metadata one byte at a time using scalar instructions.

Even so, let's see what happens when we benchmark our SoA SwissSet against std::unordered_set, FlatHashSet, and RobinHoodSet.

We'll use the same test suite from the previous chapter, inserting 3,000,000 random integers and running 1,000,000 queries across 1%, 50%, and 99% miss rates:

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#include <dsa/SwissSet.h>
9
10const int kNumElements = 3'000'000;
11const int kNumQueries = 1'000'000;
12
13std::vector<int> GenerateData() {
14  std::vector<int> data(kNumElements);
15  std::mt19937 rng(42);
16
17  std::uniform_int_distribution<int> dist(1, 50'000'000);
18  for (int i = 0; i < kNumElements; ++i) data[i] = dist(rng);
19  return data;
20}
21
22const std::vector<int> Data = GenerateData();
23
24std::vector<int> GenerateQueries(double miss_rate) {
25  std::vector<int> queries;
26  queries.reserve(kNumQueries);
27
28  int misses = kNumQueries * miss_rate;
29  int hits = kNumQueries - misses;
30
31  for (int i = 0; i < hits; ++i) {
32    queries.push_back(Data[i]);
33  }
34
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  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
71static void BM_RobinHood(benchmark::State& state) {
72  double miss_rate = state.range(0) / 100.0;
73  std::vector<int> queries = GenerateQueries(miss_rate);
74
75  RobinHoodSet set;
76  for (int val : Data) set.Insert(val);
77
78  for (auto _ : state) {
79    for (int query : queries) {
80      benchmark::DoNotOptimize(set.Contains(query));
81    }
82  }
83}
84
85static void BM_SwissSet(benchmark::State& state) {
86  double miss_rate = state.range(0) / 100.0;
87  std::vector<int> queries = GenerateQueries(miss_rate);
88
89  SwissSet set;
90  for (int val : Data) set.Insert(val);
91
92  for (auto _ : state) {
93    for (int query : queries) {
94      benchmark::DoNotOptimize(set.Contains(query));
95    }
96  }
97}
98
99#define REGISTER_BENCHMARK(func) BENCHMARK(func) \
100  ->Unit(benchmark::kMillisecond) \
101  ->ArgName("MissRatePct") \
102  ->Arg(1) \
103  ->Arg(50) \
104  ->Arg(99)
105
106REGISTER_BENCHMARK(BM_StdSet);
107REGISTER_BENCHMARK(BM_FlatHashSet);
108REGISTER_BENCHMARK(BM_RobinHood);
109REGISTER_BENCHMARK(BM_SwissSet);

1---------------------------------------
2Benchmark                           CPU
3---------------------------------------
4BM_StdSet/MissRatePct:1         72.9 ms
5BM_StdSet/MissRatePct:50        78.8 ms
6BM_StdSet/MissRatePct:99        62.2 ms
7
8BM_FlatHashSet/MissRatePct:1    26.5 ms
9BM_FlatHashSet/MissRatePct:50   50.8 ms
10BM_FlatHashSet/MissRatePct:99   78.0 ms
11
12BM_RobinHood/MissRatePct:1      35.9 ms
13BM_RobinHood/MissRatePct:50     50.0 ms
14BM_RobinHood/MissRatePct:99     47.4 ms
15
16BM_SwissSet/MissRatePct:1       26.2 ms
17BM_SwissSet/MissRatePct:50      51.4 ms
18BM_SwissSet/MissRatePct:99      26.3 ms

Even with a scalar probing loop, SwissSet outperforms both FlatHashSet and RobinHoodSet. This is particularly true in use cases involving high miss rates, where the SwissSet is cutting query time in half.

There are three reasons why SwissSet is more efficient, particularly as the miss rate increases.

Reason 1: Working Set Compression

To hold 3,000,000 elements under a 70% load factor, our Capacity scales to over 8 million slots using the power-of-two allocation strategy: $2^{23} = 8,388,608$.

In FlatHashSet and RobinHoodSet, the Slot array then occupies around 64MB of RAM, which exceeds the L3 cache capacity of many processors.

In SwissSet, the Metadata array occupies only 8 MB of RAM. Because the entire metadata table fits inside the L3 cache, probing Metadata avoids main memory stalls on a massive fraction of queries.

Reason 2: Overall Memory Efficiency

In FlatHashSet, bundling a 4-byte int key with a 1-byte CellState enum forces the compiler to add 3 bytes of alignment padding per slot, consuming 8 bytes per slot.

By separating Metadata (1 byte per slot) and Keys (4 bytes per slot) into homogeneous arrays, all alignment padding disappears. Our total memory footprint drops from 8 bytes per slot down to 5 bytes per slot, representing a 37.5% reduction in cache pressure and total RAM usage.

Reason 3: Filtering Collisions Before Touching Keys

When a query misses, SwissSet walks a few 1-byte entries in Metadata until it encounters kEmpty. Because 99.22% of colliding occupied slots have a different H2 byte, the CPU rarely fetches from the 16 MB Keys array during a missed query.

By storing H2 inside the control byte, we have effectively embedded a 1-byte fingerprint filter directly into the front door of our hash table.

Let's look one more time at the inner while loop of SwissSet::Contains():

1while (true) {
2  int8_t ctrl{Metadata[Index]};
3
4  if (ctrl == h2) {
5    if (Keys[Index] == key) return true;
6  }
7
8  if (ctrl == Ctrl::kEmpty) {
9    return false;
10  }
11
12  Index = (Index + 1) & Mask;
13}

Our Metadata buffer is a contiguous array of int8_t bytes, and our loop is simply scanning that int8_t array for two target values: h2 and kEmpty.

That is the exact problem we solved with xsimd::batch, mask(), and std::countr_zero() in the previous lesson .

In the next lesson, we will replace this byte-by-byte walk with vectorized group probing. Instead of inspecting Metadata[Index] one slot at a time, we will load a 16-byte or 32-byte xsimd::batch directly from Metadata and compare the entire group against h2 and kEmpty in parallel.

Here is the complete code for the initial SwissSet we constructed in this lesson:

In this lesson, we redesigned our open-addressed hash table from the ground up to prepare it for hardware vectorization:

1. Ditching Robin Hood: When probing metadata is cheap, tracking DIB values and swapping elements during Insert() costs more CPU cycles and cache write traffic than it saves.
2. Structure of Arrays (SoA) Split: Interleaving State, Key, and Payload inside an array of structures wastes alignment padding, pollutes cache lines with uninspected payloads, and prevents contiguous SIMD loads. Separating 1-byte Metadata from Keys packs 64 slot states into a single 64-byte cache line.
3. Control Bytes: We split our 64-bit hash into a 57-bit H1() bucket index and a 7-bit H2() signature. Storing negative states (kEmpty = -128, kDeleted = -2) alongside non-negative H2 signatures inside each control byte filters out 99.22% of hash collisions without touching the Keys array.

With our Metadata packed into a contiguous std::vector<int8_t>, our container is now primed for xsimd.

In the next lesson, we will vectorize SwissSet to probe 16, 32, or 64 buckets per clock cycle, handle group wrap-around at array boundaries, and push our maximum load factor all the way to 87.5%.