Hash Maps in C++ for Competitive Programming: unordered_map Explained

Hash Maps: The Performance Cheat Code Every Competitive Programmer Relies On

TL;DR: A hash map trades order for speed. It gives up sorted keys to get O(1) average-time reads, writes, and deletes, which is why it's the first tool competitive programmers reach for. In C++ that's std::unordered_map, a hash table. It is not backed by a red-black tree; that's std::map, its ordered sibling.

Anecdotally, many Time Limit Exceeded verdicts on LeetCode and Codeforces come from a linear search where a hash map would have done O(1) lookups. That's motivation, not proof, but most people who have practiced enough have hit it. This post shows how hash maps work, when they win (see the patterns and the cheat sheet), and how they can hurt you (see how hash maps get you hacked).

Contents

1. What is a hash map? The dictionary idea
2. Hashing: the ingredient
3. How std::unordered_map works: the hash table
4. The ordered alternative: std::map and the red-black tree
5. Competitive programming patterns
6. How hash maps get you hacked
7. Hash map vs std::map: complexity cheat sheet for LeetCode
8. FAQ
9. References

Jump to a specific concept

1. What is a hash map? The dictionary idea

A hash map is a dictionary: a set of keys, each pointing to a value. Keys are usually cheap to compare or hash; values can be arbitrarily complex.

Example: a bookstore catalog keyed by author ID, where each value is a std::vector<Book>. Every operation is CRUD:

// Conceptual interface, not a real STL class
template <class K, class V>
class AssociativeArray {
public:
    void insert(const K& key, const V& value);
    void erase(const K& key);
    V&   operator[](const K& key);          // access; inserts a default V if missing
    bool contains(const K& key) const;      // member function since C++20
};

C++ gives you two real implementations of this interface. They are not interchangeable:

Memorize this table. Sections 3 and 4 explain why the numbers are what they are, and the cheat sheet extends it.

↑ Back to contents

2. Hashing: the ingredient

Why this matters: a hash table skips searching entirely, because the hash tells it which bucket to look in. Everything in section 3 builds on that.

A hash function deterministically turns an arbitrary key into a fixed-size number, designed so that:

1. The same input always gives the same output (determinism).
2. Different inputs spread as uniformly as possible (few collisions; what happens when collisions do occur is covered under separate chaining).
3. It's fast to compute: O(k) in the key size k, independent of how many elements are stored.

// Illustrative polynomial rolling hash; real code should use std::hash
struct Hash {
    std::size_t operator()(const std::string& key) const {
        std::size_t h = 0;
        for (char c : key)
            h = h * 31 + static_cast<unsigned char>(c);
        return h;
    }
};

Hashing shows up well beyond hash tables. Bitcoin chains block headers with SHA-256, though hashing is only one piece of that system: digital signatures (ECDSA) and proof-of-work are equally load-bearing. Passwords should be stored as salted hashes from slow, purpose-built functions such as bcrypt, scrypt, or Argon2. Those are cryptographic hashes with a different goal from the fast, non-cryptographic hashes a hash table uses. (A hash function that's predictable is also a weakness for hash tables; see hash flooding.)

↑ Back to contents

3. How std::unordered_map works: the hash table

A common misconception, including in many tutorials: unordered_map does not use a red-black tree. It's a hash table with buckets. (The red-black tree belongs to std::map; see section 4.) The mental model:

• An array of N buckets.
• hash(key) % N picks a bucket, using the hash function from section 2.
• Collisions (two keys in one bucket) are handled by separate chaining: each bucket holds a linked list of entries.
• When the load factor (elements / N) crosses a threshold, the table rehashes: it grows N and redistributes every element.

template <class K, class V, class Hash = std::hash<K>>
class HashMap {
public:
    V&   operator[](const K& key);               // O(1) avg, O(n) worst
    void insert(const K& key, const V& value);   // O(1) avg
    void erase(const K& key);                    // O(1) avg
    bool contains(const K& key) const;           // O(1) avg
private:
    struct Entry { K key; V value; Entry* next; };
    std::vector<Entry*> buckets;
    std::size_t count;
    Hash hasher;

    std::size_t bucketIndex(const K& key) const {
        return hasher(key) % buckets.size();
    }
    void rehash();  // O(n); triggered when the load factor exceeds its limit
};

Why "O(1) average, O(n) worst"

With a good hash function, keys spread evenly and each bucket holds about one element. A lookup is one hash computation plus a very short list walk. If all n keys collide into a single bucket, that bucket becomes one linked list of length n, and every operation degrades to an O(n) scan. Attackers can trigger exactly this on purpose; see hash flooding.

Separately, the single insert that triggers a rehash costs O(n), though that cost is amortized O(1) over many inserts.

Chaining isn't the only option

Open addressing stores entries directly in the array and probes for another slot on collision. Python's dict and many "flat" hash maps work this way. Chaining is what C++ uses in practice, because the standard requires references to elements to stay valid across a rehash, which pushes implementations toward node-based storage.

Interview follow-up: iterator invalidation

Rehashing invalidates iterators to an unordered_map but not pointers or references to its elements. An insert that doesn't trigger a rehash invalidates nothing. Erasing invalidates only the erased element. Compare with std::map, whose iterators are stable.

Memory overhead

Each element lives in its own heap node with a next pointer, and often a cached hash code. On top of that, the table keeps a bucket array of about one pointer per bucket. This is typically lighter per element than a red-black tree node (three pointers plus a color), but it isn't free, and pointer-chasing hurts cache locality in both.

↑ Back to contents

4. The ordered alternative: std::map and the red-black tree

If a hash map trades order for speed, std::map does the opposite. It keeps keys sorted and pays O(log n) per operation. It's a self-balancing binary search tree called a red-black tree, which guarantees O(log n) even on adversarial input, unlike the hash table's O(n) worst case.

Five properties define it (CLRS, Chapter 13):

1. Every node is red or black.
2. The root is black.
3. Null leaves (nil nodes) are black.
4. A red node never has a red child.
5. Every path from a node to its descendant null leaves has the same number of black nodes (its black-height).

A useful corollary of properties 3 to 5: if a node has exactly one non-nil child, that child must be red with two nil children. Otherwise the black-heights wouldn't match.

These rules bound the height at 2·log₂(n+1) (CLRS Lemma 13.1). So even the worst-case input can't degrade the tree into a linked list, unlike a plain unbalanced BST.

enum class Color { RED, BLACK };

template <class T>
struct RBNode {
    T data;
    Color color;
    RBNode *parent, *left, *right;

    RBNode(const T& value, Color c, RBNode* nil)
        : data(value), color(c), parent(nil), left(nil), right(nil) {}
};

template <class T>
class RBTree {
public:
    void insert(const T& value);        // O(log n)
    bool remove(const T& value);        // O(log n)
    bool search(const T& value) const;  // O(log n)
private:
    RBNode<T>* root;
    RBNode<T>* nil;                     // sentinel, always black
    void leftRotate(RBNode<T>* x);      // O(1)
    void rightRotate(RBNode<T>* y);     // O(1)
    void insertFixup(RBNode<T>* z);     // O(log n); at most 2 rotations
    void deleteFixup(RBNode<T>* x);     // O(log n); at most 3 rotations
};

Full implementation: cpp-software-design repo (replace with your real URL).

Why std::map is a tree and not a hash table

The C++ standard doesn't name a data structure. It requires logarithmic lookup, insertion, and erasure, plus iteration in sorted key order (the associative container requirements). A hash table has no natural order, so it can't meet that contract. A balanced BST can, and libstdc++, libc++, and MSVC STL all implement std::map and std::set as red-black trees. So this is universal in practice, but technically an implementation choice.

Interview follow-up: iterator stability

Inserting into or erasing from a std::map never invalidates iterators, pointers, or references to other elements. Only the erased element's are invalidated. Nodes are individually allocated and never move. This contrasts with unordered_map, whose iterators are invalidated on rehash.

Not sure which container fits your problem? Jump to which container to pick.

↑ Back to contents

5. Competitive programming patterns

Four patterns cover a large share of hash map problems on LeetCode and Codeforces. All of them use unordered_map; for when not to, see which container to pick and how hash maps get you hacked.

Frequency counting

unordered_map<int, int> freq;
for (int x : nums) ++freq[x];   // operator[] default-constructs 0 on first access

Two-sum complements ("seen before?")

vector<int> twoSum(vector<int>& nums, int target) {
    unordered_map<int, int> seen;   // value -> index
    for (int i = 0; i < (int)nums.size(); ++i) {
        auto it = seen.find(target - nums[i]);
        if (it != seen.end()) return {it->second, i};
        seen[nums[i]] = i;
    }
    return {};
}

Prefix sums: count subarrays with sum k

int subarraySum(vector<int>& nums, int k) {
    unordered_map<int, int> count{{0, 1}};   // prefix sum -> occurrences
    int sum = 0, ans = 0;
    for (int x : nums) {
        sum += x;
        auto it = count.find(sum - k);
        if (it != count.end()) ans += it->second;
        ++count[sum];
    }
    return ans;
}

Grouping by a canonical key (anagrams)

vector<vector<string>> groupAnagrams(vector<string>& strs) {
    unordered_map<string, vector<string>> groups;
    for (auto& s : strs) {
        string key = s;
        sort(key.begin(), key.end());
        groups[key].push_back(s);
    }
    vector<vector<string>> res;
    for (auto& [key, group] : groups) res.push_back(move(group));
    return res;
}

Tip: use find when you only want to check for a key. operator[] inserts a default value when the key is missing, which can quietly grow your map.

↑ Back to contents

6. How hash maps get you hacked

An attacker who knows your hash function can craft keys that all collide, turning O(1) into O(n) per operation and O(n²) overall (the worst case from section 3, on purpose). This is called hash flooding. It was formalized in Crosby & Wallach's 2003 paper on algorithmic complexity attacks, and it hit web frameworks hard after a 2011 talk at 28C3 (Klink & Wälde). Full citations are in the references.

Defenses vary by ecosystem:

• Python (3.3+) and Rust randomize hash seeds by default.
• Java's String.hashCode is deterministic, so HashMap instead converts long buckets into balanced trees.
• libstdc++, libc++, and MSVC STL don't randomize std::hash by default. Verify this against your toolchain version.

This matters on Codeforces, where other contestants can submit anti-hash tests during hacking phases. With libstdc++, integer keys hash to themselves and bucket counts are prime numbers, so inserting many multiples of a bucket-count prime piles keys into one bucket.

The fix: a randomly seeded custom hash

#include <chrono>
#include <cstdint>
#include <unordered_map>

struct SplitMix64Hash {
    static uint64_t splitmix64(uint64_t x) {
        x += 0x9e3779b97f4a7c15ULL;
        x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9ULL;
        x = (x ^ (x >> 27)) * 0x94d049bb133111ebULL;
        return x ^ (x >> 31);
    }
    size_t operator()(uint64_t x) const {
        static const uint64_t RANDOM =
            std::chrono::steady_clock::now().time_since_epoch().count();
        return splitmix64(x + RANDOM);
    }
};

std::unordered_map<long long, int, SplitMix64Hash> m;

For string keys, hash the string with std::hash<std::string> first and pass that value through the same mixer. Calling m.reserve(n) up front also avoids repeated rehashes.

If you don't want to think about any of this, std::map has no such weakness: its O(log n) bound holds for every input.

↑ Back to contents

7. Hash map vs std::map: complexity cheat sheet for LeetCode

Which one on LeetCode

• Frequency counts, "seen before?" checks, two-sum complements: unordered_map. You rarely need order, and O(1) average wins at scale. Examples in the patterns section.
• Min/max key, predecessor/successor ("closest key ≤ x"), range queries, ordered iteration: std::map, using begin(), rbegin(), lower_bound, and upper_bound, all in O(log n). unordered_map can't do these at all. See why std::map is ordered.
• Sliding window with a small key space: array<int, 26>. It's effectively a hash map with an identity hash and a true O(1) worst case.
• Graph adjacency: unordered_map<int, vector<int>> for sparse or non-contiguous node IDs; vector<vector<int>> when nodes are 0..n-1.
• Codeforces or any judge with hacks: use a randomly seeded hash or std::map.

↑ Back to contents

8. FAQ

Does unordered_map use a red-black tree? No. It's a hash table with buckets. std::map is the one backed by a red-black tree.

Is unordered_map fast enough for Codeforces? Usually yes, but on Codeforces anti-hash tests can make the default hash O(n) per operation. Use a randomly seeded custom hash or std::map if hacks are possible.

Is unordered_map always faster than map? Not always. It's faster on average for lookups, but has an O(n) worst case, and for small n the difference is often negligible.

When should I use std::map instead? When you need sorted iteration, range queries, lower_bound/upper_bound, or guaranteed O(log n) worst-case behavior. See the container guide.

When should I use a fixed-size array instead of a hash map? When the key space is small and dense (for example, 26 lowercase letters or values in 0..10⁶). An array has no hashing cost, no collisions, and better cache behavior.

Why is unordered_map O(n) in the worst case? If all keys land in one bucket, that bucket is a linked list of n entries, so lookup degrades to a linear scan. Details in section 3.

↑ Back to contents

9. References

• cppreference: std::unordered_map and std::map (complexity and iterator invalidation sections)
• Cormen, Leiserson, Rivest, Stein, Introduction to Algorithms: Ch. 11 (hash tables; §11.2 chaining, §11.4 open addressing) and Ch. 13 (red-black trees; Lemma 13.1 for the height bound, §13.3 insertion, §13.4 deletion)
• ISO C++ standard: associative container requirements and unordered associative container requirements
• Crosby & Wallach, "Denial of Service via Algorithmic Complexity Attacks," USENIX Security 2003
• Klink & Wälde, "Effective Denial of Service Attacks Against Web Application Platforms," 28C3, 2011

↑ Back to contents