Why this matters
Hash tables are one of the most common ways a program looks up data by key. std::unordered_map and std::unordered_set in C++ are hash tables. The course module on maps and sets covers them as tools. This lesson explains what happens inside, because the speed of a hash table depends on one thing: how often two different keys end up in the same place.
When two keys end up in the same place, that is a collision. Collisions are normal. Every hash table has them. What matters is how many there are and how much work each one causes. A table with few collisions answers a lookup in about the same time no matter how many keys it holds. A table with many collisions answers a lookup by scanning a long list, and the time grows with the number of keys. The rest of this lesson shows both cases with code you can compile and run.
Ordered sets and maps (std::set and std::map) do not have collisions in this sense. They keep keys in sorted order in a tree, so they never hash keys at all. The next lesson in this module, custom keys, covers what a hash table needs from a key type. This lesson stays with the inside of the table.
The idea: an array of buckets
A hash table is an array. Each slot of the array is called a bucket. A bucket holds one or more entries, where each entry is a key and its value.
To store a key, the table needs to know which bucket to use. It gets that answer from a hash function. A hash function takes a key and returns a number. The table then turns that number into a bucket index. The usual way is the remainder after dividing by the number of buckets, written in C++ as hash % bucketCount.
A plain example shows the steps. Suppose the table has 10 buckets, numbered 0 to 9. Suppose the hash function for a string adds up the codes of its letters. The letter c has code 99, a has 97, and t has 116. Here is the work for the key "cat":
- Add the codes: 99 + 97 + 116 = 312.
- Take the remainder after dividing by 10: 312 % 10 = 2.
- Store the entry in bucket 2.
Looking up "cat" later repeats the same steps. The table computes 312, goes straight to bucket 2, and checks what is there. It never looks at the other 9 buckets. That is why a lookup is fast when the buckets are short.
The code below builds this table with a small class. Read the put and get functions first. They show the steps above in code.
#include <cstddef>
#include <functional>
#include <iostream>
#include <string>
#include <utility>
#include <vector>
struct Entry {
std::string key;
int value;
};
class ToyTable {
public:
using Hasher = std::function<std::size_t(const std::string&)>;
ToyTable(std::size_t bucketCount, Hasher hasher)
: buckets_(bucketCount), hasher_(std::move(hasher)) {}
std::size_t bucketFor(const std::string& key) const {
return hasher_(key) % buckets_.size();
}
void put(const std::string& key, int value) {
auto& bucket = buckets_[bucketFor(key)];
for (auto& entry : bucket) {
if (entry.key == key) {
entry.value = value;
return;
}
}
bucket.push_back({key, value});
}
// Returns -1 when the key is not present.
int get(const std::string& key) {
const auto& bucket = buckets_[bucketFor(key)];
for (const auto& entry : bucket) {
++comparisons_;
if (entry.key == key) {
return entry.value;
}
}
return -1;
}
void printBuckets() const {
for (std::size_t i = 0; i < buckets_.size(); ++i) {
if (buckets_[i].empty()) continue;
std::cout << "bucket " << i << ":";
for (const auto& entry : buckets_[i]) {
std::cout << " " << entry.key << "=" << entry.value;
}
std::cout << "\n";
}
}
std::size_t comparisons() const { return comparisons_; }
void resetComparisons() { comparisons_ = 0; }
private:
std::vector<std::vector<Entry>> buckets_;
Hasher hasher_;
std::size_t comparisons_ = 0;
};
// Adds the letter codes of the key. Anagrams always get the same sum.
std::size_t sumOfLetters(const std::string& key) {
std::size_t sum = 0;
for (char c : key) {
sum += static_cast<unsigned char>(c);
}
return sum;
}
int main() {
ToyTable table(10, sumOfLetters);
table.put("cat", 1);
table.put("act", 2);
table.put("tac", 3);
table.put("dog", 4);
table.printBuckets();
table.resetComparisons();
std::cout << "get tac = " << table.get("tac") << "\n";
std::cout << "comparisons: " << table.comparisons() << "\n";
table.resetComparisons();
std::cout << "get dog = " << table.get("dog") << "\n";
std::cout << "comparisons: " << table.comparisons() << "\n";
table.resetComparisons();
std::cout << "get cow = " << table.get("cow") << "\n";
std::cout << "comparisons: " << table.comparisons() << "\n";
return 0;
}Compile it and run it:
g++ -std=c++20 -Wall -Wextra -o toy toy.cpp
./toyThe output is:
bucket 2: cat=1 act=2 tac=3
bucket 4: dog=4
get tac = 3
comparisons: 3
get dog = 4
comparisons: 1
get cow = -1
comparisons: 0Look at the first line. The three keys cat, act and tac all went to bucket 2. Each of them uses the same letters in a different order, so the sum is 312 for all three. That is a collision. The key dog has a sum of 314, so it went to bucket 4 alone.
The std::function in the constructor lets us pass the hash function in as a value. That is only for this demo. The real std::unordered_map picks its own hash function from the key type.
What a collision costs
A collision does not break the table. The table still finds the right entry. It has to check more entries to find it.
Inside one bucket, the table keeps a short list of entries. To find a key, it walks the list and compares each key with the one it wants. Each check is one comparison. The get function above counts them in comparisons_.
Look at the output again. Looking up tac took 3 comparisons. The bucket held cat, then act, then tac. The table had to look at cat and act before it reached tac. Looking up dog took 1 comparison because dog was alone in its bucket. Looking up cow took 0 comparisons, because cow hashes to bucket 9 and that bucket is empty. The sum of its letters is 99 + 111 + 119 = 329, and 329 % 10 = 9.
The rule is simple. If a bucket holds k entries, a lookup in that bucket makes at most k comparisons. A lookup for a key that is not in the table still has to check every entry in its bucket before it can say "not found".
With a good hash function and a sensible number of buckets, most buckets hold zero or one entry. Then a lookup makes about one comparison, and the work does not grow when the table grows. That is the reason people say hash table lookups take constant time on average. The word "average" matters. It describes the typical case. A bad hash function breaks it.
Example 2: a hash that puts everything in one bucket
Imagine a hash function that always returns 0. Every key goes to bucket 0. The table would have many buckets, but all of its entries would sit in one of them. The table then works like a plain list. Each lookup walks through every entry.
The program below uses a hash function that always returns 0. It also uses the standard library's unordered map, so you can see the same effect in the real container. It inserts 2000 integers, then checks the size of the bucket that holds key 7.
#include <cstddef>
#include <iostream>
#include <unordered_map>
struct AlwaysZero {
std::size_t operator()(int) const noexcept { return 0; }
};
int main() {
std::unordered_map<int, int> good;
std::unordered_map<int, int, AlwaysZero> bad;
for (int i = 0; i < 2000; ++i) {
good[i] = i;
bad[i] = i;
}
std::cout << "good: buckets = " << good.bucket_count()
<< ", bucket of key 7 has " << good.bucket_size(good.bucket(7)) << " key(s)\n";
std::cout << "bad: buckets = " << bad.bucket_count()
<< ", bucket of key 7 has " << bad.bucket_size(bad.bucket(7)) << " key(s)\n";
std::cout << "bad find 1999 = " << bad.find(1999)->second << "\n";
return 0;
}The output on the machine used to test this lesson was:
good: buckets = 2357, bucket of key 7 has 1 key(s)
bad: buckets = 2357, bucket of key 7 has 2000 key(s)
bad find 1999 = 1999Both tables have 2357 buckets. The good one spreads the keys out, so the bucket for key 7 holds only key 7. The bad one puts all 2000 keys into one bucket. Finding key 1999 in the bad table means checking up to 2000 entries. The answer is still correct, but the table is no longer fast. Each new insert also gets slower, because each insert first checks the bucket for a matching key.
The standard library gives you bucket(key) and bucket_size(index) so that you can inspect a table like this. They are useful for debugging. Do not use them in ordinary code, because the bucket numbers depend on the library and can change between versions.
Example 3: measuring how well a hash spreads keys
A hash function is good when it spreads real keys over many buckets. You can measure this. The program below takes 1000 keys, "k0" to "k999", and places each one into 1000 buckets. It then counts how many buckets received at least one key, and how many keys the fullest bucket received. It does this for two hash functions. The first is the letter-sum function from example 1. The second is FNV-1a, a common 64-bit string hash that multiplies and mixes each letter into a running number.
#include <cstddef>
#include <cstdint>
#include <iostream>
#include <string>
#include <vector>
std::size_t sumOfLetters(const std::string& key) {
std::size_t sum = 0;
for (char c : key) sum += static_cast<unsigned char>(c);
return sum;
}
// FNV-1a: a common 64-bit string hash.
std::size_t fnv1a(const std::string& key) {
std::uint64_t hash = 14695981039346656037ULL;
for (char c : key) {
hash ^= static_cast<unsigned char>(c);
hash *= 1099511628211ULL;
}
return static_cast<std::size_t>(hash);
}
void report(const char* name, std::size_t (*hasher)(const std::string&)) {
const std::size_t buckets = 1000;
std::vector<std::size_t> counts(buckets, 0);
for (int i = 0; i < 1000; ++i) {
std::string key = "k" + std::to_string(i);
++counts[hasher(key) % buckets];
}
std::size_t used = 0;
std::size_t longest = 0;
for (std::size_t c : counts) {
if (c > 0) ++used;
if (c > longest) longest = c;
}
std::cout << name << ": non-empty buckets = " << used
<< ", longest bucket = " << longest << "\n";
}
int main() {
report("sum of letters", sumOfLetters);
report("fnv1a ", fnv1a);
return 0;
}Output:
sum of letters: non-empty buckets = 55, longest bucket = 70
fnv1a : non-empty buckets = 644, longest bucket = 4The letter-sum function uses only 55 of the 1000 buckets. The fullest bucket holds 70 keys. FNV-1a uses 644 buckets, and its fullest bucket holds 4 keys.
The letter sum is weak here for a clear reason. Every key starts with k, which has code 107. The digits add between 48 and 57 each. A key such as "k999" has a sum of 107 + 57 + 57 + 57 = 278. The smallest, "k0", has a sum of 107 + 48 = 155. So every sum falls between 155 and 278. Only about 124 buckets out of 1000 can ever be used. The rest stay empty no matter how many keys you add.
This is a common trap. A hash function can look reasonable on paper and still waste most of the table on real data. Testing it on the keys you actually use is the only reliable check.
Why the buckets are a number of primes
The standard library does not always use the number of buckets you might expect. Run this program and look at the bucket counts:
#include <functional>
#include <iostream>
#include <string>
#include <unordered_map>
int main() {
std::cout << "std::hash<int>{}(7) = " << std::hash<int>{}(7) << "\n";
std::cout << "std::hash<int>{}(42) = " << std::hash<int>{}(42) << "\n";
std::unordered_map<int, std::string> names;
names[3] = "Asha";
names[16] = "Ravi";
std::cout << "buckets = " << names.bucket_count() << "\n";
std::cout << "bucket of 3 = " << names.bucket(3)
<< ", bucket of 16 = " << names.bucket(16) << "\n";
std::cout << "keys in bucket 3 = " << names.bucket_size(names.bucket(3)) << "\n";
return 0;
}The output was:
std::hash<int>{}(7) = 7
std::hash<int>{}(42) = 42
buckets = 13
bucket of 3 = 3, bucket of 16 = 3
keys in bucket 3 = 2In the GCC library, the hash for an int is the number itself. Each key goes to the remainder of its value after dividing by the bucket count. The table started with 13 buckets. The number 16 divided by 13 leaves a remainder of 3, the same as 3. So the keys 3 and 16 collide. You do not need to plan for this. The point is that a collision can happen between two keys that look unrelated.
The bucket counts in the outputs above, 13, 29 and 2357, are all prime numbers. A prime count shares no factors with most patterns in the keys, so keys that are all multiples of 10 are less likely to pile into a few buckets. The exact choice belongs to the library, and you should not depend on it.
Load factor and growing the table
The load factor is the number of entries divided by the number of buckets. It is the average number of entries per bucket. A load factor of 0.5 means half a key per bucket on average. A load factor of 2 means two keys per bucket on average, which means longer scans.
The standard library keeps the load factor under a limit. The limit is max_load_factor(). Here is the output of a short check:
#include <iostream>
#include <unordered_map>
int main() {
std::unordered_map<int, int> m;
std::cout << "max_load_factor = " << m.max_load_factor() << "\n";
for (int i = 0; i < 20; ++i) m[i] = i;
std::cout << "size = " << m.size() << ", buckets = " << m.bucket_count()
<< ", load_factor = " << m.load_factor() << "\n";
return 0;
}Output:
max_load_factor = 1
size = 20, buckets = 29, load_factor = 0.689655The default limit is 1. When an insert would push the load factor above the limit, the library builds a larger table, moves every entry into it, and then continues. This step is called rehashing. It costs time, and it is one reason a single insert can take much longer than the others. The average cost stays low because the table grows by a large factor each time.
Rehashing also changes which bucket each key uses, because the bucket count changed. You never need to do this by hand. If you know the table will hold about 10,000 keys, you can call reserve(10000) on it before the inserts. That asks the library to pick a bucket count large enough up front, so it does not have to rehash many times while you fill the table.
Common mistakes
A hash that ignores part of the key. This is the most common cause of slow hash tables in practice. Suppose your key is a pair of numbers (x, y) and your hash function uses only x. Then every point with the same x collides with every other point with that x. A grid with 1000 rows and 1000 columns would put 1000 points into each row's bucket. The fix is to use every field that equality uses. The next lesson, custom keys, shows how to combine several fields.
A hash that changes between calls. A hash function must return the same number for the same key every time the key is used in one run. If it returns different numbers, the table looks in the wrong bucket and reports that a key is missing. The next lesson covers this rule for your own key types.
Using a type that has no hash. The standard library has hash functions for numbers, strings, and a few other types. It does not have one for std::vector. If you use a vector as a key without providing a hash, the compiler stops with an error. This is the real output from GCC 15 for std::unordered_map<std::vector<int>, int> counts;:
/usr/include/c++/15/bits/hashtable.h:210:51: error: static assertion failed: hash function must be copy constructibleThe message is long, because the library reports the error from deep inside its own code. The line that names the problem is the static assertion failed line. It means no usable hash exists for the key type. The fix is to write a hash for your type, as the next lesson shows, or to use a key type that already has one.
Assuming the iteration order. An unordered_map does not store its entries in the order you inserted them, and it does not sort them. Iterating over it walks the buckets in an order that depends on the hash and the bucket count. If you need sorted output, sort the keys yourself, or use an ordered map.
Assuming a bad table is a correct table. A slow table still returns correct answers, so the bug does not show up in tests that use a few keys. It shows up when the number of keys grows. Test your data structure with the size you expect in real use.
Practice
Exercise 1. Using the sumOfLetters function from example 1, which bucket does the key "tca" go to in a table with 10 buckets? Which other keys from the example go to the same bucket?
Show the answer
The letters of "tca" are the same as "cat", so the sum is 312. 312 % 10 is 2, so the key goes to bucket 2. The keys "cat", "act" and "tac" already share bucket 2, so "tca" joins them.
Exercise 2. Using the same sumOfLetters function, do the keys "ab" and "ba" collide in a table with 10 buckets? What are their sums?
Show the answer
Yes. Both keys use the letters a and b, so both sums are 97 + 98 = 195. 195 % 10 is 5, so both go to bucket 5.
Exercise 3. In the program from example 2, change the loop so that it inserts 100 keys instead of 2000. For the bad table, what will bad.bucket_size(bad.bucket(7)) print?
Show the answer
It will print 100. The AlwaysZero hash sends every key to bucket 0, so the bucket that holds key 7 holds every key in the table.
Exercise 4. A lookup for a key that is missing from the table checks every entry in its bucket. If the bucket holds 5 entries and the key is not there, how many comparisons does get make?
Show the answer
It makes 5 comparisons, one for each entry in the bucket. It then returns -1 because the key was not found.
Exercise 5. A table has 500 entries and 250 buckets. What is the load factor? If a hash function spreads the keys evenly, about how many entries does a lookup compare on average?
Show the answer
The load factor is 500 / 250 = 2. With an even spread, each bucket holds about 2 entries. A lookup for a missing key compares about 2 entries, and a lookup for a key that is present stops early, after about 1 or 2 comparisons.
Summary
- A hash table is an array of buckets. A hash function turns a key into a number, and the remainder after dividing by the bucket count picks the bucket.
- A collision is two keys in the same bucket. The table still works, but a lookup must check each entry in that bucket.
- If a bucket holds
kentries, a lookup in it makes at mostkcomparisons. A bad hash function puts many keys in one bucket and makes lookups slow. - A good hash spreads real keys over many buckets. Measure this on your own keys, because a hash can look fine and still use few buckets.
- The load factor is entries divided by buckets. The library rehashes into a larger table when the load factor passes its limit, so keep the limit and
reservein mind for large tables. - The next lesson covers how to write a hash function and equality for your own key types, so the table can tell keys apart correctly.