C++ unordered_map and unordered_set: Hashing, Equality and a Custom-Key Frequency Counter

unordered_map and unordered_set can look like automatic constant-time containers until a custom key, a weak hash, or an accidental insertion through operator[] produces a surprise. Lookup, insertion and erasure are average O(1) with a suitable hash and controlled load, not unconditionally O(1); if many keys collect in one bucket, worst-case work can grow to O(n). Hashes, equality, buckets and load factor explain how a custom-key frequency counter handles a collision. Any small bucket calculation below is a teaching model, not a prediction of a library's hash values, bucket policy or iteration order.

C++ unordered_map versus unordered_set: choose by the stored value

std::unordered_set<Key> stores unique keys. unordered_set<int>{4, 4, 7, 4, 7, 9} has size 3 and contains 4, 7 and 9, but its iteration order is unspecified. std::unordered_map<Key, Value> stores one mapped value per unique key. Counting red, blue, red, green, blue, red gives red -> 3, blue -> 2 and green -> 1.

Ordering is a container-choice question, not something to recover from one observed run. The broader Unordered Containers in C++: unordered_set and unordered_map with Worked Examples compares all four unordered types and basic integer and string examples. Composite keys add a narrower requirement: hashing and equality must encode the same identity, even when unequal keys collide. The Coding & DSA Courses for Placements page provides the broader study route.

C++ hashing and equality: the custom-key contract

Lookup has two stages. The hasher produces a size_t code that directs the search to a bucket; equality decides whether a key there is the requested key.

The required implication is:

KeyEqual(a, b) == true implies Hash(a) == Hash(b).

The converse is not required because unequal keys may collide.

For VisitKey { int userId; int topicId; }, equality requires both fields to match. Use the deliberately simple teaching hash userId * 10 + topicId:

• (7,12): 7 * 10 + 12 = 82

• (8,2): 8 * 10 + 2 = 82

• (9,1): 9 * 10 + 1 = 91

The first two collide but remain distinct. This hasher is poor for production because many pairs produce the same sum.

If equality compares only userId, it treats (7,12) and (7,13) as equivalent, while their hashes are 82 and 83. The violated implication can break lookup or uniqueness. Define identity first, then use the same fields in equality and hashing.

C++ unordered_map worked example: count through a collision

This complete program uses small non-negative inputs so the teaching arithmetic stays visible:

#include <cstddef>
#include <unordered_map>

struct VisitKey {
    int userId;
    int topicId;
};

struct VisitKeyHash {
    std::size_t operator()(const VisitKey& k) const {
        return static_cast<std::size_t>(k.userId) * 10u
             + static_cast<std::size_t>(k.topicId);
    }
};

struct VisitKeyEqual {
    bool operator()(const VisitKey& a, const VisitKey& b) const {
        return a.userId == b.userId && a.topicId == b.topicId;
    }
};

int main() {
    std::unordered_map<VisitKey, int, VisitKeyHash, VisitKeyEqual> frequency;
    VisitKey visits[]{{7, 12}, {8, 2}, {7, 12},
                      {9, 1}, {8, 2}, {7, 12}};

    for (const VisitKey& key : visits) {
        ++frequency[key];
    }
}

On a missing key, operator[] inserts a value-initialised int of 0; prefix ++ makes it 1. Hash 82 does not merge the first two keys because equality returns false. Final size is 3: (7,12) -> 3, (8,2) -> 2, (9,1) -> 1.

C++ unordered buckets and collision cost

In a separate five-bucket teaching model, bucket = hash % 5. Hash 82 puts (7,12) and (8,2) in bucket 2; hash 91 puts (9,1) in bucket 1. Missing key (6,22) hashes to 6 * 10 + 22 = 82, reaches bucket 2 and compares with both keys. The library controls its real bucket reduction and internal order.

Two size 4, bucket-count 5 tables both have load factor 4 / 5 = 0.8, yet behave differently:

Load factor measures average occupancy; hash quality controls its unevenness. Hashing and Collision Resolution develops the underlying ideas. Good expected distribution plus bounded load supports average O(1) operations; a chain of n keys gives O(n) lookup work.

C++ load_factor, reserve and rehash with exact arithmetic

load_factor() is size() / bucket_count(): size 3 and bucket count 5 give 3 / 5 = 0.6. max_load_factor() is a capacity threshold, not a chain-length guarantee. A bad hasher can still crowd one bucket.

For table.max_load_factor(0.75f); table.reserve(100);, minimum requested capacity is ceil(100 / 0.75) = ceil(133.333...) = 134 buckets. The library may choose 137, 149, 256 or another permitted count. reserve(100) plans for about 100 elements at the threshold; rehash(100) requests at least 100 buckets, subject to the size requirement.

A rehash redistributes existing elements, so one insertion can take linear time. It invalidates iterators and may change iteration order, but references and pointers to non-erased elements remain valid. Reserve before a known large batch, not inside the loop.

C++ unordered container traps: query without mutation

On the finished table, frequency[{7,12}] reads 3; frequency[{5,5}] inserts 0 and raises size from 3 to 4. find({4,4}) reports absence without insertion. contains({4,4}) does likewise in C++20 and later; use find before C++20.

For unordered_set<VisitKey, VisitKeyHash, VisitKeyEqual> s, s.insert({7,12}) returns inserted = true, then false when repeated. Inserting (8,2) succeeds despite hash 82 because equality differs. An unordered_set has no mapped count or operator[].

Keep these fixes together:

• Equal hashes do not mean equal keys. Apply equality.

• Use the same identity fields for hashing and equality.

• For ordered output, copy and sort.

• Reacquire iterators after an insertion that may rehash.

Never mutate a stored map key or set element in a way that changes its hash or equality identity.

C++ unordered_map and unordered_set trace questions

Try these before reading the answers:

1. For unordered_set<int> s{4,4,7,4,7,9}, what is s.size(), and is printed order determined?

2. After the six custom-key inputs, what are frequency.size(), frequency[{7,12}] and frequency[{8,2}]?

3. A table has size 12, bucket count 16 and maximum load factor 0.75. What is its load factor, and what happens when a thirteenth distinct key is inserted?

4. Equality compares only userId, so (11,4) and (11,9) are equivalent, while hashing both fields gives 114 and 119. Is this legal?

Answers: (1) size 3; order is not determined. (2) 3, 3, 2. (3) 12 / 16 = 0.75; 13 / 16 = 0.8125, so insertion triggers rehashing, but the new exact bucket count is not derivable from the interface. (4) No. Equivalent keys need equal hashes. Compare both fields or hash only userId, according to the intended identity.

Continue with Hashing MCQs: 12 Solved on Hash Functions (GATE) for bucket traces, load-factor calculations and collision reasoning.

C++ unordered_map and unordered_set: the short version

• Use unordered_set for uniqueness.

• Use unordered_map for key-to-value state.

• Define equality first for a custom key.

• Hash the same logical identity, combining every field used by equality and no equality-ignored field.

• Reserve when the expected element count is known.

Collisions are normal. The hash/equality contract controls correctness; distribution controls speed. A normal combiner gets h1 = std::hash<int>{}(userId) and h2 = std::hash<int>{}(topicId), then returns h1 ^ (h2 + 0x9e3779b9U + (h1 << 6) + (h1 >> 2)). This reduces obvious structural collisions but cannot promise collision freedom. No numeric output is worked because std::hash is implementation-dependent.

Use C++ Programming to place these containers in a fuller language sequence. Implement the six-input counter, print the three counts, then swap in a constant hasher. The answers stay correct while bucket concentration and lookup work worsen.