unordered: hash, equivalence, and rehash

Hash and KeyEqual are one joint contract

A hash value is not a unique identifier; different keys may collide. KeyEqual decides whether two keys are equivalent. Hash must give equivalent keys the same hash; the converse does not hold. The equality predicate must be an equivalence relation, and while a key is stored both functions must keep returning consistent results for that key.

The example Account identifies identity only by id. The display name does not participate in hashing or equality, so two objects with the same id occupy one slot. If equality ignores case, the hash must normalize characters by the same rule. Changing only one of the two functions violates the container's requirements; it is not merely a small performance loss.

Buckets and load behind average-constant time

Lookup, ordinary single-element insertion, and erasure by key usually have average-constant complexity. The worst case can degrade to linear; a bad distribution or adversarial input can pack many keys into a few buckets. The standard does not promise a prime-sized bucket table, a fixed growth factor, or a particular hash algorithm, and it does not promise that traversal order is insertion order.

load_factor() is the number of elements divided by the number of buckets. max_load_factor() controls the allowed average load. For a bulk build, set the load policy first, then reserve(expected_count). That argument is an element count. rehash(bucket_count) takes a lower bound on the number of buckets and must still satisfy the load requirement for the current element count. You cannot assert that requesting 100 buckets yields exactly 100, and you should not try to repair a broken hash by lowering the load.

Rearranging buckets does not move element identity

A rehash invalidates iterators and may change traversal order, yet it does not invalidate element references and pointers. Insertion that does not trigger a rehash keeps existing iterators valid. Erasure invalidates only handles to the erased element. Inserting new keys while iterating therefore needs explicit capacity conditions. The conservative, easy-to-maintain approach is to collect modifications first and apply them in a batch.

The example saves an element pointer, requests more buckets, then obtains an iterator with find again and checks that the object is still at the same address. Pointer stability is not an unbounded lifetime: erase, clear, and destruction of the container still end the corresponding object's lifetime. When output needs a stable order, sort the keys separately. Do not write one machine's traversal order into a protocol or a test expectation.

Pitfalls

• Equivalent keys must have the same hash; the same hash need not mean equivalent keys. Collision handling cannot skip the equality check.
• After a rehash, old iterators must not be used further. Even if a saved element pointer is still valid, obtain a traversal position with find again.

Minimum C++11 · complete program · Download .cpp

#include <cassert>
#include <cstddef>
#include <functional>
#include <iostream>
#include <string>
#include <unordered_set>

struct Account { int id; std::string name; };
struct HashId {
    std::size_t operator()(const Account& a) const {
        return std::hash<int>{}(a.id);
    }
};
struct EqualId {
    bool operator()(const Account& a, const Account& b) const {
        return a.id == b.id;
    }
};

int main() {
    std::unordered_set<Account, HashId, EqualId> accounts;
    accounts.max_load_factor(0.75f);
    accounts.reserve(8);
    auto inserted = accounts.insert(Account{7, "Ada"});
    auto duplicate = accounts.insert(Account{7, "Alias"});
    assert(inserted.second && !duplicate.second);
    const Account* saved = &*inserted.first;
    accounts.rehash(accounts.bucket_count() + 1);
    auto found = accounts.find(Account{7, "ignored"});
    assert(found != accounts.end() && &*found == saved);
    assert(saved->name == "Ada" && accounts.size() == 1);
    std::cout << saved->id << ' ' << saved->name << '\n';
}

Compile locally

g++ -std=c++11 -Wall -Wextra -Wpedantic -pthread stl-unordered.cpp -o example && ./example

Expected result

7 Ada

CHECK YOUR UNDERSTANDING

Close the answer. Explain it.

A hash function always returns 0, but the equality predicate is correct. Does that violate unordered_set correctness requirements? Can reserve fully fix the lookup cost?

Check the sources

• Working draft [unord.req]: hash consistency, load, and iterator invalidation

Drafts and official chapters change. The version mark is only the example’s minimum.