Hash-Based Containers

So far, we've focused on arranging our data in a way that makes it fast to traverse and process. However, many systems are not designed to process large chunks of data at once. Sometimes, the primary thing we care about is looking for a single item. This generally takes one of two forms:

1. We want to check if something exists in our collection. For example, someone wants to register an account on our application, and we need to check if the username or email address they entered has already been registered.
2. We want to retrieve the value associated with a key. For example, we have a specific identifier like the reference number for a transaction, and we want to get the details of that transaction.

At an algorithmic level, these are essentially the same problem. Both scenarios involve finding a key in a collection. In the second scenario, the key just happens to be bundled together with some additional data, too.

The standard library containers optimized for these tasks are std::unordered_set and std::unordered_map. We cover the standard library sets and maps in more detail in the previous course. In this lesson, we'll just give a quick overview before going under the hood to see how they work.

The standard library's std::unordered_set is a container that stores unique elements in no particular order. It is perfectly suited for our first scenario: a container that lets us quickly check if a specific item already exists.

The two primary actions are inserting an item into the set using the insert() method, and checking if an item exists in the set using the contains() method:

1#include <iostream>
2#include <unordered_set>
3#include <string>
4
5int main() {
6  std::unordered_set<std::string> RegisteredUsers;
7
8  // Add users to the set
9  RegisteredUsers.insert("Alice");
10  RegisteredUsers.insert("Bob");
11
12  // Check if a user exists
13  if (RegisteredUsers.contains("Alice")) {
14    std::cout << "Alice is already registered\n";
15  }
16
17  if (!RegisteredUsers.contains("Charlie")) {
18    std::cout << "Charlie is available\n";
19  }
20}

1Alice is already registered
2Charlie is available

The standard library's std::unordered_map builds on this same concept. There is one main difference:

• In a set, each element is a single object - usually called a key
• In a map, each element is two objects - usually called a key-value pair

In standard library maps, key-value pairs are stored as a std::pair whose first member is the key, and second is the value associated with that key.

To insert objects, we provide both the key and the associated value. To query the container, we use only the key:

1#include <iostream>
2#include <unordered_map>
3#include <string>
4
5int main() {
6  // First template parameter is the key type;
7  // second is the value type. Our keys be strings
8  // in this example, and our value will be ints
9  std::unordered_map<std::string, int> PlayerScores;
10
11  // Create and insert key-value pairs
12  std::pair Alice{"Alice", 1500};
13  PlayerScores.insert(Alice);
14  
15  std::pair Bob{"Bob", 800};
16  PlayerScores.insert(Bob);
17
18  if (PlayerScores.contains("Alice")) {
19    std::cout << "Alice has a score\n";
20  }
21
22  if (!PlayerScores.contains("Charlie")) {
23    std::cout << "Charlie doesn't have a score";
24  }
25}

1Alice has a score
2Charlie doesn't have a score

The ability to store a value alongside the key makes it perfect for the second scenario we described in the introduction. That is, we have a key and want to retrieve the value associated with that key.

The std::unordered_map container overloads the [] operator to make this usage pattern much easier:

1#include <iostream>
2#include <unordered_map>
3#include <string>
4
5int main() {
6  std::unordered_map<std::string, int> PlayerScores;
7  
8  std::pair Alice{"Alice", 1500}; 
9  PlayerScores.insert(Alice); 
10  PlayerScores["Alice"] = 1500; 
11  
12  std::pair Bob{"Bob", 800};
13  PlayerScores.insert(Bob);
14  PlayerScores["Bob"] = 800;
15
16  std::cout << "Alice's score: " << PlayerScores["Alice"];
17
18  if (PlayerScores.contains("Charlie")) {
19    std::cout << "Alice's score: " << PlayerScores["Charlie"];
20  }
21}

1Alice's score: 1500

Behind the scenes, hash sets and hash maps work in fundamentally the same way. The challenge they need to solve is finding a key within the container as quickly as possible. Whether or not that key is bundled alongside an additional value is relatively unimportant to the design of the data structure or the algorithms that use it.

The C++ standard library also includes std::unordered_multiset and std::unordered_multimap, which work in much the same way. The only difference is that the multi variations allow multiple objects with the same key to be stored. To support that use case, they also include a slightly expanded API, such as count() methods to return how many copies of a given key are in the container.

But again, whether we allow or disallow duplicate keys is relatively unimportant. The data structures are the same, and the algorithms that interact with them change in only small, obvious ways.

We'll focus on sets rather than maps in this chapter, and our containers won't support duplicates. We'll highlight the rare scenarios where the additional payloads of a map or the desire to support duplicate keys makes a meaningful difference.

Preview: Trees

The standard library also includes similar-sounding containers such as std::set, std::multiset, std::map, std::multimap, std::flat_set, and std::flat_map. These work differently: they are implemented as trees rather than hash-based containers. We cover trees in the next chapter.

The insertion and lookup functions of both std::unordered_set and std::unordered_map are both $O(1)$ algorithms on average. It doesn't matter how big our collection gets - adding or finding things within it maintains an approximately constant cost.

How is that possible? Our previous best efforts were the $O(\text{log} N)$ lookups of binary search algorithms, and those required the data to be sorted. The standard library's unordered sets and maps have no such requirement.

The secret is that they aren't searching at all - they use a strategy where they can translate our query directly into a physical memory address. We'll rebuild this strategy in this lesson and then explore alternative options in subsequent lessons.

Let's start with an easy case. If our keys are small, tightly packed integers like 0 through 99, the strategy is simple. We just allocate an array of 100 elements, and then position elements within that array based on their value. If we wanted to store 42, we'd put it in Array[42].

A container that implements this insertion strategy might look something like this:

1#pragma once
2#include <vector>
3
4class HashSet {
5private:
6  std::vector<bool> Array;
7
8public:
9  // Allocate an array of 100 booleans, initialized to false
10  HashSet() : Array(100, false) {}
11
12  void Insert(int key) {
13    // Use the key itself directly as the physical index
14    if (key >= 0 && key < 100) {
15      Array[key] = true;
16    }
17  }
18};

Then, if we later need to ask "does this set contain 42?", we jump directly to Array[42] and check if it is there. No searching or loops required - just an $O(1)$ lookup:

1// ...
2
3class HashSet {
4// ...
5public:
6  bool Contains(int key) const {
7    if (key >= 0 && key < 100) {
8      return Array[key];
9    }
10    return false;
11  }
12};

But what if our keys are strings, like "PlayerOne"? Or what if our keys are 64-bit integers that can take any value in that range? We cannot allocate an array with 18 quintillion slots just to track a collection of 50 integers. To bridge this gap, we use a hash function.

A hash function is a mathematical meat grinder. It accepts an input of potentially any size or type (a string, a struct, a float) and scrambles the bits, outputting a fixed-size integer.

One of the key properties is that a hash function must be deterministic - the same input must always generate the same output. If we feed "PlayerOne" into a hash function, it might spit out 14,930,122. Then, every time we feed it "PlayerOne", it will always spit out that same value.

This scrambler allows us to map chaotic, sparse, or non-integer data to a single numerical value. In C++, the standard library provides std::hash<T>() for this purpose:

1#include <iostream>
2#include <string>
3#include <functional>
4
5int main() {
6  std::hash<std::string> StringHasher;
7
8  size_t hashA = StringHasher("PlayerOne");
9  size_t hashB = StringHasher("PlayerTwo");
10
11  // These will be different 64-bit integers
12  std::cout << hashA << "\n" << hashB;
13}

112433818514973321678
213461229425461713598

We could use these integers as the indices of our array, but they're huge. Using them directly would require an array with a very large memory footprint. We'll shrink these down to a more manageable range soon, but before we do that, let's briefly talk about an important effect we want our hash functions to have.

The Avalanche Effect

In most real-world use cases, the objects we want to store in our container are quite similar. The integers we store tend to be in a similar range; the strings we store tend to be of a similar length and in the same language; objects derived from a custom struct have a similar bit layout.

If our hash function returned similar hashes for similar objects, this would be a problem. It would mean our data would get hashed to a similar range of integers, meaning they'd be assigned to a similar range of indices in our array. This increases the number of collisions we have to deal with - situations where two different values get assigned to the same index.

We'll learn how to deal with collisions soon, but our first line of defence is to reduce the frequency with which they occur. To help with this, we want our hash outputs to be scattered across the whole integer spectrum rather than clustered in a similar area.

A well-designed hash function provides this through the avalanche effect. Changing even a single bit of the input should cause large changes in the output. This means that similar inputs (like "PlayerOne" and "PlayerTwo" in our previous example) do not produce similar hashes.

An important caveat of std::hash() is that it often does not avalanche when our inputs are integers. On major compiler implementations, std::hash() for integral types is implemented as the identity function.

The identity function does absolutely nothing - it just returns the number we give it:

1#include <iostream>
2#include <functional>
3
4int main() {
5  std::hash<int> IntHasher;
6
7  std::cout << "Hash of 42: "  << IntHasher(42);
8  std::cout << "\nHash of 43: "  << IntHasher(43);
9  std::cout << "\nHash of 100: " << IntHasher(100);
10}

1Hash of 42: 42
2Hash of 43: 43
3Hash of 100: 100

To fix this, high-performance systems bypass std::hash() for integers and write their own hash functions. A common approach is a variant of the SplitMix64 algorithm.

This algorithm cascades changes from the higher bits down to the lower bits using a sequence of bitwise right-shifts (>>) and XORs (^). Additionally, by multiplying the result by large, carefully chosen prime numbers, it effectively randomizes the bits. This ensures that even consecutive numbers produce wildly different, highly entropic outputs.

More information on SplitMix64 is available here. An implementation in code looks something like this:

1#include <iostream>
2#include <cstdint>
3
4// A high-entropy integer mixer
5uint64_t Mix64(uint64_t x) {
6  x ^= x >> 30;
7  x *= 0xbf58476d1ce4e5b9ULL;
8  x ^= x >> 27;
9  x *= 0x94d049bb133111ebULL;
10  x ^= x >> 31;
11  return x;
12}
13
14int main() {
15  std::cout << "Mix64 of 42: " << Mix64(42);
16  std::cout << "\nMix64 of 43: " << Mix64(43);
17}

1Mix64 of 42: 12058926934050108962
2Mix64 of 43: 5695472266747893962

We now have two sequential inputs producing wildly different 64-bit hashes.

Whether we hash a string using std::hash() or an integer using Mix64(), we are left with a massive 64-bit integer. We must map that 64-bit space down to the physical bounds of a smaller array.

We'll cover sizing strategies for these arrays soon, but let's imagine for now that we've decided to use a 16-slot array. Then, we will need to crush our 64-bit hash into the range of 0 to 15. We can do this using the same bitwise masking trick we used to wrap our ring buffer earlier in the course.

By enforcing that our array's capacity is a power of 2, we can subtract 1 from the capacity to create a bitmask, and use the fast bitwise AND (&) instruction to snap the hash into bounds:

1size_t Capacity = 16;
2size_t Mask = Capacity - 1; // 15 (Binary: 00001111)
3
4size_t Hash = Mix64(42);
5
6// Snap the massive hash into the 0-15 range
7size_t Index = Hash & Mask; 
8
9// Place our payload in that index
10Buffer[Index] = Payload;

We can now take a string like "PlayerOne", or an integer like 42, hash it to a 64-bit value whilst maintaining the avalanche effect, mask it down to a small array boundary, and instantly drop the payload into the resulting index:

1#pragma once
2#include <vector>
3#include <cstdint>
4
5class HashSet {
6private:
7  size_t Capacity = 16;       // Binary: 00010000
8  size_t Mask = Capacity - 1; // Binary: 00001111
9  std::vector<int> Buffer;
10
Mix64 Function|Show
11  uint64_t Mix64(uint64_t x) const {/*...*/}
20
21public:
22  // Initialize buffer with -1 to represent empty slots
23  HashSet() : Buffer(Capacity, -1) {}
24
25  void Insert(int key) {
26    size_t Hash = Mix64(key);
27    size_t Index = Hash & Mask;
28
29    // Drop the payload into the resulting index
30    Buffer[Index] = key;
31  }
32};

When we later need to check if something exists in our collection, we repeat that same process and check the corresponding slot:

1// ...
2
3class HashSet {
4// ...
5public:
6  bool Contains(int key) const {
7    size_t Hash = Mix64(key);
8    size_t Index = Hash & Mask;
9
10    // Jump directly to the calculated index and check
11    return Buffer[Index] == key;
12  }
13};

There is one glaring problem here. Two different values can be allocated to the same slot, and we're not handling that correctly:

1#include <iostream>
2#include <dsa/HashSet.h>
3
4int main() {
5  HashSet Set;
6
7  // Insert our first key and verify it works
8  Set.Insert(42);
9  std::cout << "Contains 42 initially: "
10    << (Set.Contains(42) ? "True" : "False") << "\n";
11
12  // Insert 20 more keys. Because our array capacity is only 16,
13  // we are mathematically guaranteed to overwrite existing slots.
14  for (int i = 100; i < 120; ++i) {
15    Set.Insert(i);
16  }
17
18  // 42 was likely overwritten by another key that masked to
19  // the same index
20  std::cout << "Contains 42 after more inserts: "
21    << (Set.Contains(42) ? "True" : "False");
22}

1Contains 42 initially: True
2Contains 42 after more inserts: False

The Pigeonhole Principle is a fundamental mathematical concept: if we have $N$ boxes and $N + 1$ pigeons, at least one box must contain more than one pigeon.

In the context of our hash containers, our "boxes" are the physical slots in our array (e.g., 16 slots), and our "pigeons" are the potentially infinite number of keys we might want to store. Even if we use a flawless hash function with perfect distribution, once we insert a 17th element into a 16-slot array, a collision is mathematically unavoidable.

1#include <iostream>
2#include <string>
3#include <functional>
4
5int main() {
6  std::hash<std::string> StringHasher;
7  size_t Capacity = 8;
8  size_t Mask = Capacity - 1;
9
10  size_t HashA = StringHasher("Apple") & Mask;
11  size_t HashB = StringHasher("Grape") & Mask;
12  size_t HashC = StringHasher("Banana") & Mask;
13  size_t HashD = StringHasher("Mango") & Mask;
14
15  
16  // Because the Mask bounds the index from
17  // 0 to 7, it's only a matter of time before
18  // two distinct strings output the same index.
19  std::cout << "Apple Index: " << HashA;
20  std::cout << "\nOrange Index: " << HashB;
21  std::cout << "\nBanana Index: " << HashC;
22  std::cout << "\nMango Index: " << HashD;
23}

1Apple Index: 5
2Orange Index: 3
3Banana Index: 4
4Mango Index: 5

To build a functioning hash-based container, the data structure must physically store both "Apple" and "Mango" even though the math says they belong in the same slot. Efficiently handling collisions is the key challenge in hash table design.

We'll see several ways of solving this problem throughout the chapter, but implementations of the standard library's std::unordered_set and std::unordered_map tackle it using separate chaining.

When we solve collisions using a separate chaining strategy, the underlying structure typically does not store our payload directly inside the array. Instead, each slot in the array is a linked list, storing all of the elements in our collection that hashed and masked to that slot:

When we insert "Apple", it might hash and mask to index 5. The map asks the global heap allocator for memory, creates a new linked list node containing "Apple", and adds it to Array[5].

When we insert "Mango", it might also mask to index 5. The map asks the heap for another node. It traverses the linked list at Array[5], verifies that "Mango" isn't already there, and wires the new node into the chain:

Our Insert() function could implement separate chaining like the following example. Note that std::ranges::contains() requires C++23 and can be replaced with std::ranges::find() or std::find() on older standards:

1#pragma once
2#include <vector>
3#include <list>
4#include <cstdint>
5#include <algorithm>
6
7class HashSet {
8private:
9  size_t Capacity = 16;
10  size_t Mask = Capacity - 1;
11  
12  // Each slot is now a linked list (std::list) of integers
13  std::vector<std::list<int>> Buckets;
14  
Mix64 Function|Show
15  uint64_t Mix64(uint64_t x) const {/*...*/}
24
25public:
26  HashSet() : Buckets(Capacity) {}
27
28  void Insert(int key) {
29    size_t Hash = Mix64(key);
30    size_t Index = Hash & Mask;
31
32    // Grab the linked list at the resulting index
33    auto& Chain = Buckets[Index];
34
35    // Only append a new node if the key isn't already in the list
36    if (!std::ranges::contains(Chain, key)) {
37      Chain.push_back(key);
38    }
39  }
40};

Traversal and Lookup

When we want to read data from the separately-chained set, we repeat the process. We hash our query, apply the mask to find the array index, and then we walk the linked list at that index.

Because multiple keys might share the same linked list, we cannot just blindly grab the first node. We must physically compare the key stored inside the node against the key we are searching for:

1#pragma once
2#include <vector>
3#include <list>
4#include <cstdint>
5#include <algorithm>
6
7class HashSet {
8// ...
9public:
10  // ...
11  bool Contains(int key) const {
12    size_t Hash = Mix64(key);
13    size_t Index = Hash & Mask;
14
15    // Traverse the linked list at this specific array index
16    const auto& Chain = Buckets[Index];
17    return std::ranges::contains(Chain, key);
18};

Even though we're now iterating through a list, this is still classified as an $O(1)$ operation.

Assuming our array is reasonably sized for the number of entries we need to store, and our hash function distributes keys relatively evenly across the array, each linked list will be short - often just 1 or 2 nodes. The mathematical "cost" of traversing a 2-node list is a constant factor, so the academic Big O notation remains $O(1)$.

But we can probably tell from this logic that we're dealing with quite an expensive constant factor here. It is chasing pointers and missing the cache. We'll measure the cost of this in the next lesson.

When designing hash-based containers, there are two things in contention. We want our array to be small to make efficient use of memory and reduce gaps in our cache. However, the smaller and more tightly packed our array is, the more likely we are to encounter collisions. When we're solving collisions using a separate chaining strategy, that means our Insert() and Contains() algorithms need to traverse longer linked lists.

The physical array slots are referred to as buckets, and the ratio of the total number of elements in the container compared to the number of buckets is called the load factor. The larger our load factor, the longer our secondary linked lists are.

The standard library containers like std::unordered_set automatically intervene to prevent excessive degradation caused by a high load factor. When we add enough items to our set such that the load factor exceeds a certain threshold (usually 1.0, meaning an average of one element per bucket), the container undergoes a rehash. Rehashing involves allocating a new, larger array (typically double the size), recalculating the mask, and re-routing every single node from the old buckets into the new buckets.

Just like reallocating a std::vector, this rehasing process is an expensive operation that we want to avoid as much as possible. If we know how big our collection is likely to get, we can proactively reserve the space (the bucket count) we know we'll need to maintain an acceptable load factor.

If we want to intervene in the default behavior of a std::unordered_set or std::unordered_map, or just monitor what's going on, here are the main tools:

• size() returns the number of elements in the set
• bucket_count() returns size of the array that is being used
• load_factor() returns the average number of elements per bucket (that is, the average length of the linked lists)
• max_load_factor(n) sets the load factor limit - once load_factor() gets above n, the container will automatically rehash to use a larger array. This can be called without an argument if we just want to find out what the current limit is set to - usually 1.0 unless we changed it.
• rehash(n) manually triggers a rehash to an array with at least n buckets
• reserve(n) manually trigger a rehash to the number of buckets that could accommodate n elements, given the currently configured maximum load factor. This is approximately equivalent to rehash(n/max_load_factor()).

The following example incrementally pushes elements to a std::unordered_set, and when that increases the load factor above 1.0, we see it automatically rehashing to a larger array:

1#include <iostream>
2#include <unordered_set>
3
4int main() {
5  std::unordered_set<int> Set;
6  
7  std::cout << "Max Load Factor: "
8    << Set.max_load_factor();
9
10  for (int i = 1; i <= 15; ++i) {
11    Set.insert(i);
12    std::cout << "\nSize: " << Set.size()
13      << " | Buckets: " << Set.bucket_count()
14      << " | Load Factor: " << Set.load_factor();
15  }
16  
17  // Rehashing is expensive.  If we know approximately how large
18  // our container will grow, we can proactively configure the
19  // bucket count using either the rehash() or reserve() methods:
20  std::cout << "\nRehashing to at least 100 buckets...";
21  Set.rehash(100);
22  
23  std::cout << "\nSize: " << Set.size()
24      << " | Buckets: " << Set.bucket_count()
25      << " | Load Factor: " << Set.load_factor();
26}

1Max Load Factor: 1
2...
3Size: 11 | Buckets: 13 | Load Factor: 0.846154
4Size: 12 | Buckets: 13 | Load Factor: 0.923077
5Size: 13 | Buckets: 13 | Load Factor: 1
6Size: 14 | Buckets: 29 | Load Factor: 0.482759
7Size: 15 | Buckets: 29 | Load Factor: 0.517241
8Rehashing to at least 100 buckets...
9Size: 15 | Buckets: 103 | Load Factor: 0.145631

Separate chaining uses techniques like heap allocation and pointer-chasing that we've seen is physically hostile to the CPU. So why is it used here?

The C++ standard heavily prioritizes pointer stability and, as we covered in the previous chapter, this is the key advantage of linked lists. Massive logical restructuring is possible without any physical movements of the nodes - we just change how they're linked together.

The biggest restructuring that a hash-based container needs to perform is a full rehash, which std::unordered_set andstd::unordered_map can complete without physically moving a single node:

1#include <iostream>
2#include <unordered_set>
3
4int main() {
5  std::unordered_set<int> Set;
6  Set.insert(42);
7
8  // Grab a raw pointer to the value stored physically
9  // inside the set
10  const int* Before = &(*Set.find(42));
11
12  std::cout << "Initial Buckets: "
13    << Set.bucket_count() << "\n";
14  std::cout << "Pointer before rehash: "
15    << Before << " (Value: " << *Before << ")\n";
16
17
18  // Force a massive logical restructure
19  Set.rehash(1000);
20  
21  // Find the node containing 42 again
22  const int* After = &(*Set.find(42));
23  
24  std::cout << "Buckets after rehash:  "
25    << Set.bucket_count() << "\n";
26  std::cout << "Pointer after rehash:  "
27    << After << " (Value: " << *After << ")";
28}

1Initial Buckets: 8
2Pointer before rehash: 000001F157374680 (Value: 42)
3Buckets after rehash:  1024
4Pointer after rehash:  000001F157374680 (Value: 42)

As usual, the standard library implementations are general, safe containers designed to prioritize broad guarantees across a wide spectrum of use cases. We'll implement and compare alternative strategies throughout the chapter.

Here is the complete implementation of the HashSet example we created in this lesson:

To wrap up our exploration of the standard library's hash containers and their underlying mechanics:

1. The Hash and the Mask: We learned how to mathematically bypass searching by scrambling a key into a 64-bit hash, and using a bitwise & to mask it down to a physical array index.
2. The Integer Trap: We discovered that std::hash<int> is often an identity function, requiring custom bit-mixers (like Mix64) to safely avalanche sequential keys.
3. Separate Chaining: To handle collisions, std::unordered_set attaches a scattered heap-allocated linked list to every array index.
4. The Hardware Reality: We proved via benchmarking that for small datasets, the cache-thrashing pointer chasing of std::unordered_set is significantly slower than a brute-force $O(N)$ linear scan over contiguous memory.

When std::unordered_set is too slow for what we're building, we need some alternatives. We'd like to maintain the $O(1)$ mathematical routing of a hash map, but we should eradicate the linked list and the heap allocations.

In the next lesson, we will do exactly that. We will fold the payloads directly into the array to build a cache-friendly, data-oriented structure: the flat set.