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.

Related pages