Hash Caching and Heterogeneous Lookups

In the previous lessons, we used open addressing to create data structures that packed our keys into contiguous cache lines. This allowed the CPU to quickly glide over our data without any pointer-chasing disruptions.

However, we used simple 32-bit integers as our keys. In real-world use cases, we often want our keys to be more complex types, particularly strings, but this introduces a massive layer of complexity. Strings vary in length; they allocate their own memory, and they are expensive to hash and compare.

In this lesson, we will learn how to alleviate this using hash caching and heterogeneous lookups.

To understand why strings are so hostile to open-addressed hash tables, we have to look at how they are physically constructed in memory.

A std::string is not just a sequence of characters; it is a class that manages dynamic memory. Conceptually, a string is very similar to a std::vector of individual alphabetic characters. On most modern 64-bit standard library implementations, the std::string class consists of three internal components:

• An 8-byte pointer to the array of characters
• An 8-byte integer tracking the current size - the integer returned by the size() method.
• An 8-byte integer tracking the allocated capacity - the integer returned by the capacity() method.

This gives the std::string a footprint of 24 bytes (often padded to 32 bytes by the compiler).

For comparison, the Slot we've been using so far contained a 4-byte int, a 1-byte DIB, and a 1-byte State. With alignment padding, it took only 8 bytes of RAM. Because a CPU cache line is 64 bytes, a single hardware fetch pulled 8 slots into the L1 cache simultaneously. Our probe sequences were practically free.

If we blindly swap our integer out for a std::string, our new Slot structure will balloon to 32 bytes, plus the DIB and State, padding out to 40 or 48 bytes depending on the compiler's alignment rules.

We can now only fit one Slot per cache line. Every single step we take during a linear probe now requires the CPU to halt and fetch a brand new cache line from main memory.

Worse than the structural bloat is the mechanical cost of hashing and comparing strings. During our Contains() probe sequence, we have to compare the key we are searching for against the key sitting in the array slot. With integers, Current.Key == key is a single-cycle ALU instruction.

With strings, the == operator triggers a functional cascade:

1. It checks if the string sizes match.
2. If they do, the CPU must follow the string's internal pointer out into the global heap to read the actual characters.
3. It performs a byte-by-byte memory comparison until it finds a difference or verifies a match.

If a collision cluster forces us to probe past 5 elements, we aren't just walking past 5 slots in our array. We are dereferencing 5 completely separate pointers, fetching 5 disjointed character arrays from arbitrary locations on the heap, and running expensive memory comparison operations on them.

We have accidentally rebuilt the exact pointer-chasing nightmare that we've been trying to avoid.

Small String Optimization (SSO)

Modern implementations of std::string use a trick called Small String Optimization (SSO). If our string is very short (typically 15 characters or less), the class repurposes the 8-byte capacity integer and the 8-byte pointer to store the characters directly inside the class instance itself.

This avoids a heap allocation. However, the strings we need to store routinely exceed 15 characters, meaning we cannot rely on SSO to save us. In most real-world scenarios, a string relies on a pointer to the global heap.

Let's begin refactoring our Robin Hood set to accept strings so we can see the damage. We will swap our integer key for a std::string, and we will replace our custom Mix64() integer hasher with the standard library's std::hash<std::string>.

1#pragma once
2#include <vector>
3#include <string>
4#include <cstdint>
5#include <algorithm>
6#include <functional>
7
8class StringRobinHoodSet {
9  enum class CellState : uint8_t {
10    Empty,
11    Occupied
12  };
13
14  struct Slot {
15    std::string Key; 
16    uint8_t DIB{0};
17    CellState State{CellState::Empty};
18  };
19
20private:
21  size_t Capacity{16};
22  size_t Mask{15};
23  size_t Size{0};
24  std::vector<Slot> Buffer;
25
26  // Use the standard library string hasher
27  std::hash<std::string> StringHasher; 
28
29  void Grow() {
30    size_t OldCapacity{Capacity};
31    std::vector<Slot> OldBuffer{std::move(Buffer)};
32
33    Capacity *= 2;
34    Mask = Capacity - 1;
35    Buffer.assign(Capacity, Slot{});
36    Size = 0;
37
38    for (size_t i = 0; i < OldCapacity; ++i) {
39      if (OldBuffer[i].State == CellState::Occupied) {
40        // Because std::string manages dynamic memory, we use
41        // std::move to steal the heap pointer, rather than
42        // performing an expensive deep copy.
43        Insert(std::move(OldBuffer[i].Key)); 
44      }
45    }
46  }
47
48public:
49  StringRobinHoodSet() : Buffer(Capacity) {}
50
51  // ...
52};

Moving a std::string using std::move() simply copies the 24-byte footprint and nullifies the original, preventing a deep-copy of the heap-allocated character array.

Let's implement the Insert() and Contains() methods exactly as we did for integers, but using our new StringHasher:

1// ...
2class StringRobinHoodSet {
3// ...
4public:
5  // ...
6  void Insert(std::string key) {
7    if (Size >= (Capacity * 0.7f)) Grow();
8
9    // Hash the entire string to a 64-bit integer
10    size_t Index{StringHasher(key) & Mask}; 
11    Slot Incoming{std::move(key), 0, CellState::Occupied};
12
13    while (true) {
14      Slot& Current{Buffer[Index]};
15
16      if (Current.State == CellState::Empty) {
17        Current = std::move(Incoming);
18        ++Size;
19        return;
20      }
21
22      // This is an expensive memcmp!
23      if (Current.Key == Incoming.Key) return; 
24
25      if (Incoming.DIB > Current.DIB) {
26        std::swap(Incoming.Key, Current.Key);
27        std::swap(Incoming.DIB, Current.DIB);
28      }
29
30      Index = (Index + 1) & Mask;
31      Incoming.DIB++;
32    }
33  }
34
35  bool Contains(const std::string& key) const {
36    size_t Index{StringHasher(key) & Mask};
37    uint8_t SearchDIB{0};
38
39    while (true) {
40      const Slot& Current{Buffer[Index]};
41
42      if (Current.State == CellState::Empty) return false;
43
44      // Expensive memory comparison
45      if (Current.Key == key) return true; 
46
47      if (SearchDIB > Current.DIB) return false;
48
49      Index = (Index + 1) & Mask;
50      SearchDIB++;
51    }
52  }
53};

We now have a functional string-based Robin Hood set. But when a collision occurs, that Current.Key == key instruction inside the while loop forces the CPU to abandon its contiguous array, jump to the heap, and run a byte-by-byte comparison on two character arrays.

If we have to step past 4 occupied slots to find our target, we perform 4 completely useless string comparisons, thrashing the cache every single time.

To solve this, we can defer the string comparison until we are certain it is worth the cost. We can do this using a technique called hash caching.

When we hash a string, we generate a massive, random 64-bit integer. Right now, we immediately crush that 64-bit integer using our bitwise Mask to find our starting array index, and then we throw the full hash away.

Instead of throwing it away, we could store the full 64-bit hash directly inside the Slot alongside the string:

1// ...
2class StringRobinHoodSet {
3  // ...
4  struct Slot {
5    std::string Key;
6    size_t Hash{0}; 
7    uint8_t DIB{0};
8    CellState State{CellState::Empty};
9  };
10  // ...
11};

Storing an 8-byte size_t increases the physical size of our Slot, but not across any meaningful breakpoint. We could only store one Slot per cache line before, and an 8-byte increase doesn't change that.

However, it does allow us to almost entirely bypass the pointer chasing.

When we are probing for a key, we first compare the full 64-bit hash of the string we are searching for against the Hash stored inside the slot. Because a hash is just an integer, Current.Hash == Incoming.Hash executes in a single CPU cycle.

In almost all practical scenarios, if two 64-bit hashes match, it is almost certain that the underlying data also matches. Even if we were storing 100 million strings, there is only around a 0.027% chance that two of them would share the same 64-bit hash. Because of this, in many high-performance systems, a hash match is considered a "good enough" guarantee that the underlying data matches.

However, if we want to be certain, we can still take the expensive leap to main memory to perform the full std::string comparison to verify that the hash match wasn't just an incredible coincidence.

Let's update our Insert() and Contains() methods to use hash caching as the initial test, and then a follow-up check of the underlying string just to be 100% sure:

1// ...
2class StringRobinHoodSet {
3// ...
4public:
5  void Insert(std::string key) {
6    if (Size >= (Capacity * 0.7f)) Grow();
7
8    // Calculate the hash once and store it
9    size_t Hash{StringHasher(key)}; 
10    size_t Index{Hash & Mask};
11
12    // Package the hash into the incoming slot
13    Slot Incoming{std::move(key), Hash, 0, CellState::Occupied}; 
14
15    while (true) {
16      Slot& Current{Buffer[Index]};
17
18      if (Current.State == CellState::Empty) {
19        Current = std::move(Incoming);
20        ++Size;
21        return;
22      }
23
24      // Fast Path: Check the cached integer hash first
25      if (Current.Hash == Incoming.Hash) { 
26        // Slow Path: Only compare strings if hashes match
27        if (Current.Key == Incoming.Key) return; 
28      }
29
30      if (Incoming.DIB > Current.DIB) {
31        std::swap(Incoming.Key, Current.Key);
32        std::swap(Incoming.Hash, Current.Hash); 
33        std::swap(Incoming.DIB, Current.DIB);
34      }
35
36      Index = (Index + 1) & Mask;
37      Incoming.DIB++;
38    }
39  }
40
41  bool Contains(const std::string& key) const {
42    size_t Hash{StringHasher(key)}; 
43    size_t Index{Hash & Mask};
44    uint8_t SearchDIB{0};
45
46    while (true) {
47      const Slot& Current{Buffer[Index]};
48
49      if (Current.State == CellState::Empty) return false;
50
51      // Fast Path: Compare integer hashes
52      if (Current.Hash == Hash) { 
53        // Slow Path: Chase the pointer to the heap
54        if (Current.Key == key) return true; 
55      }
56
57      if (SearchDIB > Current.DIB) return false;
58
59      Index = (Index + 1) & Mask;
60      SearchDIB++;
61    }
62  }
63};

Our search sequence is fast again, but we have a silent performance leak hidden in our API. Our Contains() method expects a std::string& as its parameter.

Often, if someone wants to check if "PlayerOne" is in the set, they will pass a char* literal rather than a std::string:

1// This is not a std::string - it's a char*
2Set.Contains("PlayerOne");

Because our function demands a std::string reference, the compiler might silently construct a temporary std::string on the caller's behalf. It allocates memory on the heap, copies the "PlayerOne" characters into it, passes the reference to our function, and then destroys the allocation when the function returns.

We might be triggering a hidden heap allocation simply to ask a yes/no question.

The std::string_view Solution

To fix this, we should decouple our container's internal storage (std::string) from its query interface. C++17 added <string_view> , which helps us establish a non-owning, zero-allocation window into whatever character data the user provides. We cover string views in detail in the previous course.

By updating our query methods to accept std::string_view, users can pass string literals, raw const char* buffers, or actual std::string objects. In all cases, the compiler constructs a lightweight view containing just a pointer and a length, completely bypassing the heap allocator.

Permitting a container of one type, such as std::string, to be queried using a key of a different type, such as std::string_view, is known as Heterogeneous Lookup:

1// ...
2#include <string_view> 
3// ...
4
5class StringRobinHoodSet {
6// ...
7public:
8  // Accept a string_view to prevent hidden allocations
9  bool Contains(std::string_view key) const { 
10
11    // Wait, how do we hash a string_view?
12    // size_t Hash{StringHasher(key)};
13  }
14};

We hit a minor snag. Our container is built around std::hash<std::string>. We cannot pass a std::string_view into it.

We could create a separate std::hash<std::string_view>, but we must guarantee that hashing a std::string("Apple") and hashing a std::string_view("Apple") produce the same output. If they produce different hashes, our Current.Hash == Hash check will fail, and we will never find our data.

Fortunately, this requirement was predicted when std::string_view was designed. The standard requires it to have a transparent hashing solution that guarantees identical outputs for identical character sequences, regardless of the wrapper type.

We can simply replace std::hash<std::string> with a generic std::hash<std::string_view>, and we use it to hash both our incoming std::string objects during insertion, and our std::string_view keys during lookups:

1// ...
2class StringRobinHoodSet {
3// ...
4private:
5  // ...
6  // Change our hasher to natively accept string_views
7  std::hash<std::string_view> Hasher; 
8
9public:
10  void Insert(std::string key) {
11    // ...
12    // key implicitly converts to string_view, producing
13    // a universal, comparable 64-bit hash
14    size_t Hash{Hasher(key)}; 
15    // ...
16  }
17
18  bool Contains(std::string_view key) const { 
19    // Produce the exact same hash without allocating memory
20    size_t Hash{Hasher(key)}; 
21    size_t Index{Hash & Mask};
22    uint8_t SearchDIB{0};
23
24    while (true) {
25      const Slot& Current{Buffer[Index]};
26
27      if (Current.State == CellState::Empty) return false;
28
29      if (Current.Hash == Hash) {
30        // Current.Key (std::string) implicitly compares
31        // cleanly against key (std::string_view)
32        if (Current.Key == key) return true; 
33      }
34
35      if (SearchDIB > Current.DIB) return false;
36
37      Index = (Index + 1) & Mask;
38      SearchDIB++;
39    }
40  }
41  // ...
42};

With hash caching and heterogeneous lookups implemented, our Contains() query is now a completely allocation-free, cache-friendly operation.

Let's test our optimizations. We will benchmark three containers:

1. std::unordered_set<std::string>: The standard library baseline.
2. NaiveStringRobinHoodSet: Our Robin Hood implementation without hash caching, passing const std::string&. This is our implementation from the previous lesson, updated to use std::string keys hashed using std::hash() rather than int keys hashed with Mix64(). It is available in the Complete Code section below for reference.
3. OptimizedStringRobinHoodSet: Our implementation from this lesson, including hash caching and std::string_view.

To ensure we are bypassing small string optimization, we will generate large, 32-character strings.

As with our previous benchmarks, we will insert 2,000,000 of them, and then perform batches of 1,000,000 random queries at 1%, 50%, and 99% miss rates:

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

1---------------------------------------------
2Benchmark                                 CPU
3---------------------------------------------
4BM_StdUnorderedSet/MissRatePct:1       414 ms
5BM_StdUnorderedSet/MissRatePct:50      422 ms
6BM_StdUnorderedSet/MissRatePct:99      406 ms
7
8BM_NaiveRobinHood/MissRatePct:1        320 ms
9BM_NaiveRobinHood/MissRatePct:50       305 ms
10BM_NaiveRobinHood/MissRatePct:99       312 ms
11
12BM_OptimizedRobinHood/MissRatePct:1    160 ms
13BM_OptimizedRobinHood/MissRatePct:50   160 ms
14BM_OptimizedRobinHood/MissRatePct:99   164 ms

Here is the complete implementation of our StringRobinHoodSet using hash caching and transparent heterogeneous lookups with the help of std::string_view:

In this lesson, we discovered that dropping a complex data type like a std::string into a tightly optimized memory layout can instantly destroy its performance. We learned that:

1. Strings are fat: A std::string consumes 32+ bytes, drastically reducing the number of slots we can fit into a cache line.
2. Strings chase pointers: Standard comparisons force the CPU to follow pointers into the heap, causing pipeline stalls.
3. Hash Caching: By spending 8 bytes of structural padding to store the pre-calculated integer hash, we can bypass complex data comparisons entirely.
4. Heterogeneous Lookups: By separating our internal storage (std::string) from our API (std::string_view), we eliminated hidden, temporary heap allocations.

However, even with these optimizations, we're still losing quite a lot of performance compared to when we were using simple integer keys. String objects still live out on the heap, and in a complex program, storing the same strings multiple times adds up to a lot of wasted memory.

In the next lesson, we will explore string interning, a pattern that allows us to deduplicate strings and storing them in a dedicated, global vault. This lets us represent the strings using cheap, 4-byte integer handles that the CPU loves so much.