Hash Tables: Hashing, Collisions, Load Factor, and Open Addressing vs Chaining

From key to slot: the pipeline

The path from a key to a bucket has three stages:

1. Hash: the key is converted to an integer. For strings, a polynomial rolling hash (h = h·31 + c) is the classic exam example; for integers, the identity is common but poor for structured keys.
2. Compress: the integer is squeezed into the table's index range, almost always with modulo: index = h(key) % capacity.
3. Resolve: if that slot is already occupied by a different key, apply the collision strategy.

A good hash function has two properties: it distributes keys uniformly (no slot systematically favored), and it is deterministic (same key, same slot, every time — otherwise lookups break immediately). C++'s std::hash provides stage 1 for built-in types; the container handles 2 and 3.

// The classic exam-sized version: string key, int value, chaining.
struct Node {
    std::string key;
    int value;
    Node* next;
};

class SimpleHashMap {
    static const int CAPACITY = 101;      // prime reduces clustering
    Node* buckets[CAPACITY] = {};

    static size_t hash(const std::string& s) {
        size_t h = 0;                     // polynomial rolling hash
        for (char c : s) h = h * 31 + static_cast<unsigned char>(c);
        return h;
    }
public:
    void put(const std::string& k, int v) {
        size_t i = hash(k) % CAPACITY;
        for (Node* p = buckets[i]; p; p = p->next)
            if (p->key == k) { p->value = v; return; }   // update
        buckets[i] = new Node{k, v, buckets[i]};          // prepend
    }
    bool get(const std::string& k, int& out) const {
        for (Node* p = buckets[hash(k) % CAPACITY]; p; p = p->next)
            if (p->key == k) { out = p->value; return true; }
        return false;
    }
};

Collision strategy 1: separate chaining

Each slot holds a pointer to a linked list of all keys that hashed there. Insertion prepends to the list (O(1)); lookup walks the list comparing keys with ==.

Why it works: collisions stop being a problem and become ordinary list entries. The cost: average lookup is O(1 + α) where α is the load factor (n / capacity) — with a good hash, lists stay short and this is effectively constant. The worst case: all keys collide into one slot, degrading to O(n) — the pathological case every exam asks you to name (usually caused by a constant hash function or adversarial keys).

Collision strategy 2: open addressing

No lists: every entry lives in the table itself. On collision, probe for another slot. The three probe sequences to know:

• Linear probing: index = (h + i) % capacity for i = 0, 1, 2, ... — cache-friendly but suffers primary clustering (long runs of occupied slots grow longer).
• Quadratic probing: index = (h + i²) % capacity — breaks up runs, but suffers secondary clustering among keys with the same base hash.
• Double hashing: index = (h1 + i·h2(k)) % capacity — the second hash gives each key its own stride; fewest clustering problems.

Deletion is the classic trap: emptying a slot breaks the probe chain of later keys, so you mark it with a tombstone instead of clearing it. That is open addressing's signature complexity in practice.

Load factor and rehashing

The load factor α = n / capacity measures how full the table is. For chaining, average cost degrades gracefully with α; for open addressing, performance falls off a cliff as α → 1 because probe sequences lengthen fast. Both strategies therefore pick a threshold (commonly 0.75) and rehash when it is exceeded: allocate a bigger array (typically double), then re-insert every element — its index changes because h(key) % capacity changed.

Rehashing is O(n), but amortized over the n insertions that caused it, insertion remains O(1) average — the same accounting trick as a dynamic array's growth.

Chaining vs open addressing: the exam table

std::unordered_map is specified as a hash table with chaining and O(1) average operations — which is why the standard answer to "which container for O(1) lookup by key" is unordered_map, while "sorted order iteration" points back to std::map (a balanced BST, O(log n)).

Exercises with solutions

Work through each question before opening the solution below it.

Which C++ standard does this page assume?

Standard C++17. C++ began as C with Classes in 1979 and first shipped commercially in 1985; what a compiler flag actually selects today is one of the ISO revisions below, and the committee has published a new one every 3 years since 2011. Build these listings with -std=c++17 and they compile as written.

Common questions

Where can I check this against the language itself?

Nothing on this page outranks the standard or the library reference. When this page and one of these disagree, they are right and we want to know.

• cppreference — the C++ standard library referenceThe fastest correct answer for what a container or algorithm actually guarantees.
• isocpp.org — the Standard C++ FoundationThe FAQ and the core guidelines, written by the people who define the language.
• ISO/IEC JTC1/SC22/WG21 — the C++ standards committeeWorking drafts of the standard itself, free to read, when the wording is the question.
• GCC online documentationWhat -Wall, -Wextra and the sanitizers used on these listings actually check.
• Microsoft Learn — C++ language documentationThe MSVC view, for readers whose lab machines build with Visual Studio.

Related pages