std::unordered_map and std::unordered_set: Hashing

Part I · Module 19 · Chapter 19.6 · std::unordered_map and std::unordered_set: Hashing

1. How a Hash Table Finds Things

The structure is simpler than a tree. The container holds an array of buckets, and each bucket holds a linked list of the elements that landed in it. To find a key:

1. Compute h = hash(key) — a std::size_t.
2. Reduce it to a bucket index, h % bucket_count().
3. Walk that bucket's list, comparing each element's key with operator== until one matches or the list ends.

Steps 1 and 2 are constant time. Step 3 is constant time if the bucket holds a constant number of elements, which is the condition everything else in the chapter is about. If every key lands in a different bucket, every lookup examines one element. If every key lands in the same bucket, every lookup walks the whole container.

Note that the key type needs two things for this to work: a hash, and operator==. The tree in Chapter 19.5 needed only <. These are disjoint requirements — a type usable in a std::map is not automatically usable in a std::unordered_map and vice versa — and §9 covers supplying both for your own types.

There are four containers: unordered_set, unordered_map, and the multi versions of each. std::hash<K> is specialised by the library for the built-in types, pointers, std::string and a few others; for anything else you supply it.

2. Buckets and the Load Factor

The load factor is size() / bucket_count() — the average number of elements per bucket. The maximum load factor is the threshold above which the container decides it has too few buckets and rehashes.

std::unordered_map<int,int> u;
std::printf("n=0  buckets=%zu load=%.2f max_load=%.2f\n",
            u.bucket_count(), u.load_factor(), u.max_load_factor());
std::size_t last = u.bucket_count();
for (int i = 1; i <= 5000; ++i) {
    u[i] = i;
    if (u.bucket_count() != last) { std::printf("%d(->%zu) ", i, u.bucket_count()); last = u.bucket_count(); }
}

n=0      buckets=0      load=0.00 max_load=1.00
rehash at n = 1(->2) 3(->5) 6(->11) 12(->23) 24(->47) 48(->97) 98(->197)
              198(->397) 398(->797) 798(->1597) 1598(->3203) 3204(->6421)
final: n=5000 buckets=6421 load=0.779

Three things in that output.

The default maximum load factor is 1.0 — on average one element per bucket. So the container rehashes whenever the element count would exceed the bucket count, which is why the rehashes happen at n = 1, 3, 6, 12, 24 and so on, each one just past the previous bucket count.

The bucket counts are prime numbers: 2, 5, 11, 23, 47, 97, 197, 397, 797, 1597, 3203, 6421. This is libc++ choosing primes deliberately, because the bucket index is hash % bucket_count and a prime modulus mixes the hash's bits far better than a power of two does. With 1,024 buckets, h % 1024 keeps only the low ten bits of the hash and throws away everything else, so a hash whose low bits are poor produces heavy collisions. A prime modulus involves all the bits. Other implementations make the opposite choice — power-of-two bucket counts, because h & (n-1) is cheaper than a division — and compensate by mixing the hash themselves.

An empty container has 0 buckets and has allocated nothing, the same property Chapter 19.3 §2 measured for an empty std::vector.

3. Rehashing, and What reserve Prevents

A rehash allocates a new bucket array and redistributes every element into it. The elements themselves are not moved — §5 measures that — but every bucket list is rebuilt, which is O(n) work.

reserve(100): buckets=101 (>= 100 so load stays <= 1.0)
after 100 inserts: buckets=101 (NO rehash) load=0.990

reserve(n) sets the bucket count high enough that n elements will not exceed the maximum load factor — here 101 buckets for 100 elements — and then the hundred insertions caused no rehash at all, finishing at a load factor of 0.990. This is the same discipline as Chapter 19.3's reserve on a vector and it has the same justification: when you know the count, saying so removes work the container would otherwise do by guessing.

The allocation figures:

1000 entries, no reserve: allocs=1010 bytes=49384
1000 entries, reserved:   allocs=1001 bytes=32072

One thousand of those allocations are the element nodes — one per element, unavoidably, as with every node-based container. The extra ten in the unreserved case are the successive bucket arrays, and they account for 17,312 extra bytes. So reserve saves less here than it does on a std::vector, because the dominant cost is the per-element node that reserve cannot eliminate. It still saves the O(n) redistribution work ten times over, which the byte figure does not show.

rehash(n) is the related member that sets the bucket count directly rather than deriving it from an element count; reserve(n) is the one you want.

4. What a Bad Hash Costs

This is the chapter's central measurement. Three hash functions, the same 10,000 keys, the same 200,000 lookups:

struct GoodHash { std::size_t operator()(int k) const { return std::hash<int>{}(k); } };
struct WeakHash { std::size_t operator()(int k) const { return (std::size_t)(k % 16); } };
struct BadHash  { std::size_t operator()(int)   const { return 42; } };

The harness also walks every bucket and reports the longest chain, so the cause is measured alongside the effect:

good hash    buckets=12853 non-empty=10000 longest chain=1            1.5 ns/lookup
16 buckets   buckets=12853 non-empty=16    longest chain=625       1828.0 ns/lookup
ALL collide  buckets=12853 non-empty=1     longest chain=10000     9287.4 ns/lookup

slowdown: weak = 1216.5x good,  all-collide = 6180x good

Read the non-empty column first, because it is the diagnosis. All three containers allocated 12,853 buckets — the container did its job identically in all three cases. With the good hash, 10,000 of those buckets are in use and the longest holds one element. With WeakHash, 16 buckets are in use out of 12,853, because the hash only ever produces 16 distinct values, and the 10,000 keys divide into 16 chains of 625. With BadHash, one bucket is in use and it holds all 10,000.

Then the timing. 1.5 ns with a good hash is a hash computation, a modulus and one comparison. 1,828 ns is walking an average of 312 elements of a linked list. 9,287 ns is walking an average of 5,000. The factors are 1,216× and 6,180×.

And the container is still O(1) by the standard's definition, because the complexity requirements for these containers are stated on average, with the average taken over a hash that distributes keys uniformly. Supply a hash that does not, and you have not violated the standard; you have invalidated the assumption its guarantee rests on. There is no diagnostic, no warning, and no runtime check. The only symptom is that the program is slow.

This is why §9's advice about writing a hash is the most consequential paragraph in the chapter, and why bucket_count, bucket_size and load_factor are public members at all: they exist so you can diagnose exactly this.

5. The Invalidation Rule That Is Different

Chapter 19.1 §7 introduced this and it belongs here in full, because these are the containers where it matters.

std::unordered_map<int,int> u; u[0] = 0;
const void* p = &u.at(0);
std::size_t b0 = u.bucket_count();
for (int i = 1; i < 500; ++i) u[i] = i;

buckets 2 -> 797 (rehashed)
&u.at(0) UNCHANGED  <-- pointers and references SURVIVE a rehash
but the ITERATION ORDER is rebuilt; first 8 keys now: 499 498 497 496 495 494 493 492

The bucket count went from 2 to 797, so a rehash certainly happened, and the element's address did not change. The nodes are allocated individually and a rehash only rebuilds the array of bucket pointers; it never relocates an element.

So the rule is:

• Insertion invalidates iterators if it causes a rehash — which, because you cannot easily predict it, means assume always unless you have reserved.
• Insertion never invalidates pointers or references. Ever.
• Erasure invalidates iterators, pointers and references to the erased element only.

The iteration order being rebuilt is the visible consequence and the honest form of the measurement. Dereferencing an iterator invalidated by a rehash is undefined behaviour, so it cannot be measured — what can be measured is that the sequence the container yields is reorganised, which is the same fact from the legal side. An iterator has to know which bucket it is in to find the next element; after a rehash, that information is wrong.

The practical consequence: in an unordered container, hold a pointer, never an iterator, across an insertion. This is the opposite of the advice for std::vector, where the pointer is the dangerous thing and an index is safe.

6. There Is No Ordering, and No Range Query

unordered_map iterated: 200(b) 100(a) 300(c)
there is no lower_bound/upper_bound member at all

The iteration order is whatever the bucket layout produces. It is not insertion order, it is not key order, and it changes when the container rehashes. Code that depends on it is wrong even if it works today.

More importantly, the ordered operations do not exist. There is no lower_bound, no upper_bound, no equal_range over a key range, and no meaningful rbegin. A hash deliberately destroys the relationship between nearby keys — that is what makes it spread them out — so there is no way to recover "the keys between 200 and 400" except to look at every element:

set: keys in [500000,500100] = 16, found by two O(log n) walks
unordered_set: same answer = 16, but only by scanning all 181424 elements

Both found the same sixteen keys. The tree located the range with two logarithmic descents; the hash table examined 181,424 elements. That is the trade Chapter 19.5 §7 described from the other side, and it is the single question that decides between the two containers.

7. The Comparison With std::map

The row that decides most cases is range / nearest-key query. If the code needs it, the tree is the only option. If it does not, the hash is several times faster at the operation that remains.

8. Choosing the Maximum Load Factor

max_load_factor(f) is the one tuning knob besides the hash, and the trade is straightforward.

A lower maximum load factor means more buckets for the same element count, so shorter chains and faster lookups, at the cost of more memory and a sparser bucket array that is itself less cache-friendly to scan during iteration.

A higher one means fewer buckets, less memory, longer chains and slower lookups.

The default of 1.0 is a reasonable balance and the honest advice is to leave it alone until a measurement says otherwise. It is worth knowing the knob exists, because when profiling shows time in find on a container with a known-good hash, raising the bucket count — through reserve, or by lowering the maximum load factor — is the remaining lever. What it cannot fix is §4's problem: with BadHash, 12,853 buckets were allocated and one was used, and no load factor would have changed that.

9. Writing a Hash for Your Own Type

To use your own type as a key you need both requirements from §1. operator== is ordinary. The hash is supplied by specialising std::hash:

struct DeviceId { int bus; int slot; };

bool operator==(const DeviceId& a, const DeviceId& b)
{ return a.bus == b.bus && a.slot == b.slot; }

template <>
struct std::hash<DeviceId> {
    std::size_t operator()(const DeviceId& d) const noexcept
    {
        std::size_t h = std::hash<int>{}(d.bus);
        h ^= std::hash<int>{}(d.slot) + 0x9e3779b97f4a7c15ULL + (h << 6) + (h >> 2);
        return h;
    }
};

Three rules, and the first two are requirements rather than advice.

Equal keys must hash equally. If a == b then hash(a) must equal hash(b). Violating this breaks the container outright: the element is inserted into one bucket and looked for in another, so find fails on a key that is present. This is the one hashing bug that produces wrong answers rather than slowness.

The hash must be consistent with operator== on exactly the same members. If operator== ignores a field, the hash must ignore it too. A hash that includes a field the comparison ignores means two equal keys hash differently — the same bug.

Spread the bits. Do not simply XOR the members together: hash(a) ^ hash(b) makes {1,2} and {2,1} collide, and for a type like DeviceId where small integers are typical, a plain XOR concentrates everything into the low bits. The combine step above is the one Boost popularised, with the shift-and-add mixing the accumulated value so position matters. §4 is the measurement of what happens when this rule is ignored.

Mark it noexcept if it cannot throw; some operations are more efficient when the hash is known not to throw.

10. When to Use Which

• Use an unordered container when you only look things up and nothing depends on order. This is the common case and it is several times faster than the tree.
• Use std::map / std::set when order matters: ordered iteration, range queries, nearest-key lookup, or min and max. §6 measured the alternative as a full scan.
• Use std::map when you need iterator stability across insertion. The unordered containers give you reference stability but not iterator stability.
• Use std::map when a worst case must be bounded. O(log n) always, versus O(n) when the hash fails — which matters for adversarial input, where a caller who can choose keys that collide can turn your lookup table into a linear scan on purpose.
• Consider a sorted std::vector for build-once-query-many data; Chapter 19.7 §3 measures it against both.

11. What to Actually Do

• Reach for unordered_map by default for keyed lookup, and map when you can name an ordering requirement.
• Call reserve(n) when the count is known. Measured: 100 insertions into a reserved container caused no rehash.
• Hash exactly the members operator== compares — no more, no fewer.
• Mix the bits when combining member hashes; never plain XOR.
• Mark the hash noexcept when it cannot throw.
• Never depend on iteration order, and never iterate to produce output that must be stable.
• Hold pointers, not iterators, across insertion.
• Diagnose slow lookups with bucket_count and bucket_size before changing anything else.
• Leave max_load_factor alone until a measurement justifies moving it.
• Prefer std::map where input is untrusted and a worst case must hold.

12. Mistakes Worth Making Once

A hash inconsistent with operator==. find fails on a key that is present. The worst bug in the chapter because it is a wrong answer.

Adding a field to operator== and not to the hash. The same bug, arrived at by maintenance.

Combining member hashes with plain XOR. {1,2} and {2,1} collide, and small integers pile into the low bits. Measured consequence: up to 6,180×.

Depending on iteration order. It is arbitrary and it changes on rehash — measured, the first eight keys came back as 499, 498, 497, …

Holding an iterator across an insertion. Undefined behaviour, and because the element's address is unchanged it will often appear to work.

Assuming unordered_map is always faster than map. With a bad hash it is 6,180× slower, and it cannot answer a range query at all.

Expecting lower_bound. It does not exist. The replacement is a scan of all 181,424 elements.

Using an unordered container for untrusted keys in a security-relevant path. A caller who can choose colliding keys can force the worst case deliberately.

Calling rehash(n) when you meant reserve(n). rehash takes a bucket count, reserve takes an element count.

13. Interview Relevance

The frozen curriculum marks this chapter Critical, and the questions reliably probe whether you know the guarantee is conditional.

"What is the complexity of unordered_map::find?" O(1) on average, O(n) in the worst case. Stopping at "O(1)" is the answer the question is designed to catch; the worst case and its cause are the content.

"When does the worst case happen?" When many keys hash to the same bucket — a poor hash, or an adversary choosing keys. Quoting the 6,180× measurement and the one-bucket-in-12,853 diagnosis is a strong answer.

"What is the load factor?" size() / bucket_count(). The default maximum is 1.0, and exceeding it triggers a rehash that rebuilds the bucket array in O(n).

"What does a rehash invalidate?" Iterators, yes. Pointers and references, no, ever. This is the discriminating question in the whole container area and few candidates get it cleanly.

"What does a key type need?" A hash and operator==. Not <. The follow-up — the relationship the hash must have with == — is the one worth being precise on.

"map or unordered_map?" Unordered for plain lookup; ordered when anything depends on order, when iterator stability is needed, or when a worst case must be bounded against untrusted input.

"Why are libc++'s bucket counts prime?" Because the index is hash % bucket_count, and a prime modulus uses all the hash's bits where a power of two keeps only the low ones. Volunteering this is a genuine differentiator.

14. What You Should Be Able to Say Now

• The three steps of a hash lookup, and which one is only conditionally constant.
• That the key needs a hash and operator==, and that this is disjoint from std::map's requirement of <.
• That the load factor is size()/bucket_count(), defaults to a maximum of 1.0, and that exceeding it rehashes in O(n).
• That libc++ uses prime bucket counts — measured 2, 5, 11, 23, 47, … 6421 — and why.
• That a hash with 16 distinct values cost 1,216× and a constant hash 6,180×, with the longest chain going from 1 to 625 to 10,000.
• That the O(1) guarantee is an average over an assumption the library cannot check, and that bucket_size is how you check it.
• That a rehash invalidates iterators and never invalidates references — so hold pointers, not iterators.
• That there is no lower_bound, and the ordered query costs a full scan.
• That a hash inconsistent with operator== produces wrong answers, not slow ones.

15. Exercises

Exercise 1 — the three hashes. Reproduce §4 and confirm the chain lengths. Then add a fourth hash returning k / 1000 and predict the longest chain before measuring it.

Exercise 2 — the diagnostic. Write a function that takes any unordered container and prints its bucket count, the number of non-empty buckets, the longest chain and the mean chain length. Run it on a container keyed by std::string with 100,000 realistic keys.

Exercise 3 — the wrong-answer bug. Write a two-field type whose operator== compares both fields and whose hash uses only one, insert elements, and show a find succeeding. Then make the hash use a field == ignores and show a find failing on a present key.

Exercise 4 — prime versus power of two. Implement both bucket-index schemes over your own tiny hash table, feed them keys whose low bits are all identical, and compare the chain-length distributions.

Exercise 5 — reserve. Measure rehash count and total allocation for building a 100,000-element container with and without reserve. Report what reserve did and did not save.

Exercise 6 — the load factor. Sweep max_load_factor from 0.25 to 8.0 for a fixed container and plot lookup time and memory. State where you would set it and why.

Exercise 7 — the two promises. Hold a pointer and an iterator to one element, force a rehash, and verify the pointer. Explain why no test of the iterator would be valid evidence.

Exercise 8 — order dependence. Write a program whose output depends on unordered_map iteration order, then change only the insertion count and show the output changing.

16. Summary

• A hash lookup is: hash the key, reduce to a bucket, walk that bucket. Only the third step is conditionally constant.
• The key needs a hash and operator== — disjoint from std::map's <.
• Measured: load factor maxes at 1.0 by default and libc++ uses prime bucket counts (2, 5, 11, 23, 47, 97, … 6421) so the modulus uses all the hash's bits.
• Measured: reserve(100) gave 101 buckets and 100 insertions caused no rehash, finishing at load 0.990.
• Measured, 10,000 keys: good hash → longest chain 1, 1.5 ns; 16-value hash → 16 buckets used of 12,853, chains of 625, 1,828 ns (1,216×); constant hash → one bucket, chain of 10,000, 9,287 ns (6,180×).
• The O(1) guarantee is an average over a uniform hash — supplying a bad one violates nothing and gets no diagnostic.
• Measured: a rehash from 2 to 797 buckets left the element's address unchanged while rebuilding the iteration order. References survive; iterators do not.
• Measured: there is no lower_bound — the range query a tree answers in O(log n + k) required scanning all 181,424 elements.
• A hash inconsistent with operator== returns wrong answers, which is the one hashing bug that is not merely slow.

Five containers have now been measured against each other on their own terms, and the obvious question has not yet been answered directly: given a problem, which one do you pick? Chapter 19.7 answers it as a decision path — a short sequence of questions, in order, each of which eliminates candidates — and then validates the path by measurement rather than assertion, running the same data through three containers under three different access patterns and showing that the winner changes each time. The chapter after it explains why the winner changes, which turns out to have very little to do with the complexity tables these five chapters have been quoting.