Cuckoo Hashing and Filters

In our previous lessons, our hash containers searched for objects using a loop. The loop continued to probe the container's memory until it either found the key or it found a reason to conclude the key doesn't exist. If we maintain a low load factor, the average length of these probing chains is quite short.

However, some systems care more about the worst case performance than the average case. In systems with strict real-time deadlines, such as network routers or high-frequency trading engines, an unbounded while loop can be unacceptable. An algorithm that may need to check dozens of memory locations to find a specific key can be problematic.

We saw how to reduce the variance of these lookup times using Robin Hood hashing , but low variance is not a strict guarantee.

When we need to guarantee an upper bound to our lookup times, Cuckoo Hashing is often the tool of choice. It trades off some insertion speed and memory efficiency for a guarantee that every key in the container can be found within a strictly limited number of memory locations - usually two.

Cuckoo hashing gets its name from the cuckoo bird, which lays its eggs in the nests of other birds. When the cuckoo egg hatches, the chick pushes the original egg out of the nest to secure the slot for itself. A Cuckoo Hash Table uses this eviction mechanism to resolve collisions.

Instead of hashing a key once and walking sequentially down an array (linear probing), a Cuckoo Hash Table hashes a key multiple times. Most implementations use two hashes per key, which generates exactly two distinct index locations where the key is allowed to live.

Then, when we want to check if a key exists, we no longer need a while loop. We simply check Index1, and we check Index2. If the key is in neither of those two buckets, it is not in the table. We have bounded our lookup to a maximum of exactly two memory fetches.

The Cuckoo Kick

Because a key can only live in one of two specific locations, insertions become much more aggressive.

When we try to insert a new key, we check its Index1 and Index2. If one is empty, we drop the key in. But if both buckets are currently occupied by other keys, we do not start walking down the array looking for a gap.

Instead, we become the cuckoo bird. We forcibly evict one of the sitting keys, stealing its bucket for our new insertion.

The evicted key is now homeless. But remember, every key has two possible locations. The evicted key looks at its alternate bucket. If that bucket is empty, it settles in. If that bucket is also full, it evicts that sitting key, and the cycle continues.

This cascade of evictions keeps the table balanced without ever degrading the bounded lookup guarantee. However, the trade-off is that insertions are now much slower as they resolve a long chain of evictions.

It also introduces a new danger: infinite loops. If the table gets too full, or if we get unlucky with our hash functions, the evictions can form a closed cycle, bouncing keys back and forth endlessly.

Managing these cycles makes full Cuckoo-based containers relatively complex to implement. They're also not particularly common - most real world use cases prefer the more balanced performance profile of Robin Hood hashing from earlier in the chapter, or Swiss Tables which we cover in the next chapter.

Cuckoo hashing is more commonly used in a slightly different context. Rather than using it to construct containers, it is regularly used to create filters.

Optimizing our algorithms for efficient CPU and memory cache only goes so far. In the real world, we often need to interact with a database or similar storage sitting on a slow disk drive, or even worse, a network location.

Let's imagine we're creating a system that caches the contents of internet resources like web pages, images, and videos, and stores them in a database. When a user requests a URL, before making an expensive trip to the internet, the server first asks if our system already has a recent copy of that resource which it can use instead.

Our system will almost always respond with a "no", because there are countless internet resources and we can only possibly cache a tiny fraction of them at any given time.

This means we need to optimize for the rejection path. We need an efficient data structure that sits in front of the database and can confidently tell us: "I do not recognize this URL - do not spend the million cycles it would take to query the database - it's not there."

We briefly introduced Bloom filters as a way to handle scenarios like this. Today, the industry standard is the cuckoo filter, which we'll build in this lesson.

To make our filter small, we cannot store full strings like "https://example.com/api/v1/users". Even if we interned them, storing a 4-byte handle per element across a billion resources would span gigabytes of RAM, reducing our cache efficiency.

Instead, we store a fingerprint. A fingerprint is just a tiny slice of a hash. When a URL comes in, we hash it to a massive 64-bit integer, but we only keep a tiny piece of it - usually just 1 byte:

1uint64_t fullHash = StringHasher("https://example.com/api");
2
3// Extract just the bottom 8 bits to create a tiny fingerprint
4uint8_t fingerprint = fullHash & 0xFF;

By storing only an 8-bit fingerprint, our memory usage plummets. A single 64-byte cache line can hold 64 fingerprints.

Because a fingerprint is so small, there is a chance that two completely different URLs will generate the same 8-bit fingerprint. This creates a false positive. The filter might tell us it has seen a URL before, even though it hasn't.

For a fast rejection path, false positives are perfectly acceptable. If the filter is wrong, we simply fall through to the slow database, at which point we'll discover the data doesn't exist. A filter's job is not to be perfect; its job is to accurately reject invalid requests instantly.

This is why filters are most commonly used in high-miss-rate contexts - that is, where the overwhelming majority of Contains() requests will return false. A cuckoo filter should never return a false negative, so the higher the miss rate, the more reliable and useful the filter is.

Let's begin building the skeleton of our CuckooFilter. We'll start with the basic class definition, our constructor, and our trusty Mix64 algorithm which we will use for hashing integers later on.

Notice that just like our previous hash tables, we force our capacity to be a power of two so we can use a bitwise Mask for rapid modulo arithmetic.

1#pragma once
2#include <vector>
3#include <string>
4#include <string_view>
5#include <cstdint>
6#include <functional>
7
8class CuckooFilter {
9private:
10  size_t Capacity;
11  size_t Mask;
12
13  std::hash<std::string_view> StringHasher;
14
15public:
16  CuckooFilter(size_t numBuckets = 1024) {
17    Capacity = 1;
18    // Requires capacity to be a power of 2
19    while (Capacity < numBuckets) Capacity *= 2;
20    Mask = Capacity - 1;
21  }
22
23private:
Mix64 Function|Show
24  uint64_t Mix64(uint64_t x) const {/*...*/}
33};

Next, we need a helper method to extract the fingerprint and the primary index (Index1) from an incoming key.

We grab the bottom 8 bits of the string's hash to form the fingerprint. We then shift the hash over to use the next chunk of bits for our Index1. We reserve 0 to mean "Empty Slot", so if our fingerprint happens to calculate to 0, we just bump it to 1.

1// ...
2
3class CuckooFilter {
4// ...
5private:
6  uint64_t Mix64(uint64_t x) const { /*...*/ }
7
8  // Helper to extract the 8-bit fingerprint and Index1
9  void GetHashes(
10    std::string_view key,
11    uint8_t& outFingerprint,
12    size_t& outIndex1
13  ) const {
14    uint64_t hash = StringHasher(key);
15
16    outFingerprint = hash & 0xFF;
17
18    // We reserve 0 to mean "Empty Slot"
19    if (outFingerprint == 0) outFingerprint = 1;
20
21    // Shift by 8 to use different bits for the index
22    outIndex1 = (hash >> 8) & Mask;
23  }
24};

There is a challenge in combining fingerprints with cuckoo hashing. When a key is inserted, it might eventually get evicted by another incoming key. When it gets evicted, it needs to fly to its alternate bucket.

In a standard container, we store the full string key, so rehashing it isn't a problem. But in a filter, we threw the original value away. We only have the 1-byte fingerprint sitting in the bucket. How can we possibly calculate a key's alternate bucket if we don't know what the original key was?

We solve this using Partial-Key Cuckoo Hashing, affectionately known as the XOR Hack.

To calculate Index2, we take Index1 and run a bitwise XOR (^) against a mix of the fingerprint. Because the bitwise XOR operator is perfectly symmetrical and reversible, we can perform this same math in reverse. If we are sitting in Index2 and we get evicted, we can find our way back to Index1 using the same formula:

1size_t Index1 = (Index2 ^ Mix64(Fingerprint)) & Mask;

This mathematical sleight-of-hand allows a fingerprint to endlessly bounce back and forth between its two designated buckets without us ever needing to know what the original value was.

Let's add a helper function for this XOR hack to our class:

1// ...
2
3class CuckooFilter {
4// ...
5private:
6  // ...
7  void GetHashes( /*...*/ ) const { /*...*/ }
8
9  // The XOR Hack
10  size_t GetAlternateIndex(
11    size_t index,
12    uint8_t fingerprint
13  ) const {
14    return (index ^ Mix64(fingerprint)) & Mask;
15  }
16};

If each bucket in our array could only hold a single fingerprint, our filter would constantly experience cycles. Two different strings might map to the same two buckets, instantly locking the table into an infinite eviction loop.

To drastically increase the resilience of the filter, we can upgrade our buckets to hold multiple slots.

Because our fingerprints are only 1 byte, we can pack 4 fingerprints into a single 4-byte bucket. This means each Index actually points to a small neighborhood of 4 slots. If a string maps to Index1 and Index2, it actually has 8 possible slots where its fingerprint can reside.

Let's add this Bucket struct and our underlying storage Table to the filter, and initialize it in the constructor.

1// ...
2
3class CuckooFilter {
4private:
5  // A 4-byte bucket containing 4 slots
6  struct Bucket {
7    uint8_t Slots[4]{0, 0, 0, 0};
8  };
9
10  size_t Capacity;
11  size_t Mask;
12  std::vector<Bucket> Table;
13
14  std::hash<std::string_view> StringHasher;
15
16public:
17  CuckooFilter(size_t numBuckets = 1024) {
18    Capacity = 1;
19    while (Capacity < numBuckets) Capacity *= 2;
20    Mask = Capacity - 1;
21
22    Table.resize(Capacity);
23  }
24
25  // ...
26};

With our buckets in place, we can implement our Contains() query.

When a query arrives, we extract the fingerprint and calculate Index1. We then check the 4 slots inside Index1. If we find the fingerprint, we return true. If it's not there, we use the XOR hack to calculate Index2, and check the 4 slots there.

There are no while loops, no linear probing, and no pointer chasing. It is a strictly bounded operation:

1// ...
2
3class CuckooFilter {
4// ...
5public:
6  // ...
7
8  bool Contains(std::string_view key) const {
9    uint8_t fingerprint;
10    size_t index1;
11    GetHashes(key, fingerprint, index1);
12
13    // Check the 4 slots in Bucket 1
14    const Bucket& b1 = Table[index1];
15    for (int i = 0; i < 4; ++i) {
16      if (b1.Slots[i] == fingerprint) return true;
17    }
18
19    // Use the XOR hack to find the alternate bucket
20    size_t index2 = GetAlternateIndex(index1, fingerprint);
21
22    // Check the 4 slots in Bucket 2
23    const Bucket& b2 = Table[index2];
24    for (int i = 0; i < 4; ++i) {
25      if (b2.Slots[i] == fingerprint) return true;
26    }
27
28    // Maximum 2 cache misses. We are done.
29    return false;
30  }
31};

Insertion is where the cuckoo evictions happen, and it requires a bit more logic. We will build this in three pieces.

First, let's write a small private helper method. This method takes a bucket index, checks its 4 slots, and if it finds an empty slot (a 0), it drops the fingerprint in and returns true.

1// ...
2
3class CuckooFilter {
4private:
5  // ...
6
7  // Helper to attempt dropping a fingerprint into a bucket
8  bool TryInsertInBucket(size_t index, uint8_t fingerprint) {
9    Bucket& b = Table[index];
10    for (int i = 0; i < 4; ++i) {
11      if (b.Slots[i] == 0) { // 0 means empty
12        b.Slots[i] = fingerprint;
13        return true;
14      }
15    }
16    return false;
17  }
18
19public:
20  // ...
21};

Next, we can begin our Insert() method. We start by calculating our hashes and attempting the peaceful path. We simply ask our new helper method to try placing the fingerprint in Index1, and if that fails, we try Index2.

1// ...
2
3class CuckooFilter {
4// ...
5public:
6  // ...
7
8  bool Insert(std::string_view key) {
9    uint8_t fingerprint;
10    size_t index1;
11    GetHashes(key, fingerprint, index1);
12
13    // Attempt the fast, peaceful path
14    if (TryInsertInBucket(index1, fingerprint)) return true;
15
16    size_t index2 = GetAlternateIndex(index1, fingerprint);
17    if (TryInsertInBucket(index2, fingerprint)) return true;
18
19    // TODO: Both buckets are full. Prepare for eviction.
20
21    return false;
22  }
23};

The Cuckoo Eviction Loop

If both buckets are full (all 8 slots are occupied), we must initiate a cuckoo kick.

We randomly select either Index1 or Index2. We randomly select one of the 4 slots inside that bucket. We overwrite that slot with our incoming fingerprint, and we take the evicted fingerprint into our temporary registers.

We then calculate the alternate bucket for the evicted fingerprint using the XOR hack, and repeat the process.

To prevent an infinite loop where fingerprints endlessly bounce back and forth, we institute a hard limit: MaxKicks. If we kick fingerprints 500 times in a row, the table is either too full or caught in a cycle, and the insertion fails.

Let's add the MaxKicks limit and replace our TODO with the eviction logic:

1// ...
2#include <random>
3
4class CuckooFilter {
5private:
6  // ...
7  const int MaxKicks{500};
8
9public:
10  // ...
11
12  bool Insert(std::string_view key) {
13    uint8_t fingerprint;
14    size_t index1;
15    GetHashes(key, fingerprint, index1);
16
17    if (TryInsertInBucket(index1, fingerprint)) return true;
18
19    size_t index2 = GetAlternateIndex(index1, fingerprint);
20    if (TryInsertInBucket(index2, fingerprint)) return true;
21
22    // Both buckets are full.
23    // Randomly select one of the two buckets to attack
24    size_t activeIndex = (rand() % 2 == 0) ? index1 : index2;
25
26    for (int kick = 0; kick < MaxKicks; ++kick) {
27      Bucket& b = Table[activeIndex];
28
29      // Randomly select a victim slot (0 to 3)
30      int victimSlot = rand() % 4;
31
32      // Swap our fingerprint with the victim
33      uint8_t evicted = b.Slots[victimSlot];
34      b.Slots[victimSlot] = fingerprint;
35
36      // We are now holding the homeless victim.
37      // Calculate its alternate destination via XOR
38      fingerprint = evicted;
39      activeIndex = GetAlternateIndex(activeIndex, fingerprint);
40
41      // Try to peacefully settle the victim in its new home
42      if (TryInsertInBucket(activeIndex, fingerprint)) {
43        return true;
44      }
45    }
46
47    // We hit the kick limit. The filter is too full
48    return false;
49  }
50};

Why not Grow the Filter?

In a conventional container, a failure to insert due to the container being almost full would prompt us to grow it. We'd allocate a larger array, and rehash everything to that new bucket count. However, this isn't an option for filters. We can't rehash the values, because we don't remember them - they were discarded after we generated their fingerprint.

More complex architectures are possible where we orchestrate multiple filters, and we can "grow" by adding additional filters to that cluster. But, in most scenarios, we generally know how big our filter needs to be, and can set its capacity accordingly.

Fast Randomness

In our insertion method, we used the C-style rand() function to select our victims. In a true production environment, rand() is often too slow and relies on hidden global state.

High-performance systems typically use a lightweight, bitwise pseudo-random number generator like Xorshift embedded directly inside the class to maintain cache locality and avoid locking overhead.

One of the flaws of a traditional Bloom filter is that we cannot delete data from it. Because multiple keys might flip the same bit, clearing a bit might accidentally erase a completely unrelated key.

Our cuckoo filter fixes this. Because our buckets hold discrete 8-bit fingerprints, we can safely delete an item by simply finding its fingerprint and wiping it back to 0.

However, we must be careful. If two different strings hash to the same 8-bit fingerprint, and they both map to the same bucket, removing one string should only delete one instance of the fingerprint. So, once we find and erase a single matching fingerprint, we immediately return true.

1// ...
2
3class CuckooFilter {
4// ...
5public:
6  // ...
7
8  bool Erase(std::string_view key) {
9    uint8_t fingerprint;
10    size_t index1;
11    GetHashes(key, fingerprint, index1);
12
13    // Check Bucket 1
14    Bucket& b1 = Table[index1];
15    for (int i = 0; i < 4; ++i) {
16      if (b1.Slots[i] == fingerprint) {
17        b1.Slots[i] = 0; // Erase it by setting to 0
18        return true;
19      }
20    }
21
22    size_t index2 = GetAlternateIndex(index1, fingerprint);
23
24    // Check Bucket 2
25    Bucket& b2 = Table[index2];
26    for (int i = 0; i < 4; ++i) {
27      if (b2.Slots[i] == fingerprint) {
28        b2.Slots[i] = 0; // Erase it by setting to 0
29        return true;
30      }
31    }
32
33    // The key was never in the filter
34    return false;
35  }
36};

Let's put our cuckoo filter to the test. Filters are generally used in scenarios with high miss rates. We'll use a 99% miss rate here.

We will pre-allocate 500,000 strings into a std::unordered_set and our CuckooFilter, and then blast both with 1,000,000 queries where almost every single query is for a key that does not exist:

1#include <benchmark/benchmark.h>
2#include <unordered_set>
3#include <vector>
4#include <string>
5#include <random>
6#include <algorithm>
7#include <dsa/CuckooFilter.h>
8
9const int kNumElements = 500'000;
10const int kNumQueries = 1'000'000;
11
12std::string GenerateString(std::mt19937& rng) {
13  const char charset[] = "ABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789";
14  std::uniform_int_distribution<int> dist(0, sizeof(charset) - 2);
15  std::string s;
16  s.reserve(16);
17  for (int i = 0; i < 16; ++i) s += charset[dist(rng)];
18  return s;
19}
20
21std::vector<std::string> GenerateData() {
22  std::vector<std::string> data(kNumElements);
23  std::mt19937 rng(42);
24  for (int i = 0; i < kNumElements; ++i) data[i] = GenerateString(rng);
25  return data;
26}
27
28const std::vector<std::string> Data = GenerateData();
29
30std::vector<std::string> GenerateQueries() {
31  std::vector<std::string> queries;
32  queries.reserve(kNumQueries);
33
34  // 1% Hits, 99% Misses
35  int hits = kNumQueries * 0.01;
36  int misses = kNumQueries - hits;
37
38  for (int i = 0; i < hits; ++i) queries.push_back(Data[i]);
39
40  std::mt19937 rng(1337);
41  for (int i = 0; i < misses; ++i) {
42    queries.push_back(GenerateString(rng));
43  }
44  return queries;
45}
46
47static void BM_StdUnorderedSet_Rejection(benchmark::State& state) {
48  std::vector<std::string> queries = GenerateQueries();
49  std::unordered_set<std::string> set(Data.begin(), Data.end());
50
51  for (auto _ : state) {
52    for (const auto& query : queries) {
53      benchmark::DoNotOptimize(set.contains(query));
54    }
55  }
56}
57
58static void BM_CuckooFilter_Rejection(benchmark::State& state) {
59  std::vector<std::string> queries = GenerateQueries();
60  
61  // CuckooFilter requires power of 2 capacity
62  // 131,072 buckets * 4 slots = 524,288 total capacity
63  CuckooFilter filter(131072);
64  
65  for (const auto& val : Data) filter.Insert(val);
66
67  for (auto _ : state) {
68    for (const auto& query : queries) {
69      benchmark::DoNotOptimize(filter.Contains(query));
70    }
71  }
72}
73
74BENCHMARK(BM_StdUnorderedSet_Rejection)
75  ->Unit(benchmark::kMillisecond);
76BENCHMARK(BM_CuckooFilter_Rejection)
77  ->Unit(benchmark::kMillisecond);

1--------------------------------------
2Benchmark                         Time
3--------------------------------------
4BM_StdUnorderedSet_Rejection    210 ms
5BM_CuckooFilter_Rejection      41.7 ms

When the std::unordered_set receives a missed query, it calculates a 64-bit hash, bounds it to an array index, and fetches the memory address. That address is an empty linked list. It takes a full trip to main memory just to realize nothing is there, stalling the pipeline.

The CuckooFilter calculates the hash, extracts the 8-bit fingerprint, and checks the 4 bytes at Index1. The 4-byte bucket is likely already sitting hot in the cache because the entire filter fits in less than 600 Kilobytes of RAM. If the fingerprint isn't there, it executes the single-cycle XOR hack and checks Index2. It confirms a true negative in nanoseconds.

But remember, the filter occasionally returns false positives - that is, Contains() returns true even though the object isn't there. This occurs when two different objects have the same fingerprint and have been allocated to the same bucket. We can trade some memory efficiency for a much lower false positive rate by increasing the signature size from 8 to 16 bits.

Here is the complete implementation of our CuckooFilter:

In this lesson, we stepped away from software heuristics to build a data structure bound by strict physical limits. We learned that:

1. Cuckoo Hashing: By relying on two independent hashes, we can bound our worst-case search time to a maximum of exactly two bucket checks, discarding the unpredictable variance of linear probing while loops.
2. The Fast Rejection Path: Instead of checking slow systems for every query, we can place a tiny filter at the boundary to instantly reject invalid requests.
3. Fingerprints: Storing a 1-byte fingerprint instead of an entire string shrinks our memory footprint drastically, allowing millions of records to fit entirely within the CPU's cache.
4. The XOR Hack: By using the symmetric nature of bitwise XOR, we can endlessly bounce orphaned fingerprints between their two designated buckets without ever needing to know what the original key was.

We have pushed sequential, scalar code as far as it can go. In the next chapter, we will begin exploring vectorization (SIMD) and the construction of the industry-standard Swiss Table, letting the hardware check dozens of buckets simultaneously in a single clock cycle.