Hash tables

How a hash function gives near-constant-time lookup, and what happens on a collision. · 8 min read

A hash table stores key/value pairs and finds them in O(1) on average. The trick is a hash function that turns any key into a bucket index. To store or find a key, you hash it and go straight to that bucket — no scanning.

The intuition

Think of a hash table like a wall of labelled lockers. Without hashing, finding a key means walking down a hallway asking every locker, "are you the one?" With hashing, the key itself tells you which locker to open. A good hash function spreads keys across lockers so most lockers stay short and easy to inspect.

The core recipe is:

1. Convert the key into an integer hash code.
2. Compress that integer into a valid bucket index, often hash % bucket_count.
3. Store the key/value pair in that bucket.
4. On lookup, hash the key again and inspect only that bucket.

Here we insert keys into 7 buckets with h(k) = k mod 7. Watch what happens when two keys want the same bucket:

Interactive visualization: Insert with h(k) = k mod 7 (separate chaining) — step through it frame by frame on this page.

C++ separate chaining example

This small table stores integers using key % bucketCount. Each bucket is a vector<int>, so collisions are handled by keeping multiple keys in the same bucket chain.

class HashSet {
    static const int bucketCount = 7;
    vector<int> buckets[bucketCount];

    int hash(int key) {
        return key % bucketCount;
    }

public:
    void insert(int key) {
        int i = hash(key);
        for (int x : buckets[i]) {
            if (x == key) return;      // already present
        }
        buckets[i].push_back(key);     // collision? append to chain
    }

    bool contains(int key) {
        int i = hash(key);
        for (int x : buckets[i]) {
            if (x == key) return true;
        }
        return false;
    }
};

Hash collisions

When two keys hash to the same bucket — a collision — we chain them in a little linked list in that bucket. As long as the table isn't too full, chains stay short and lookups stay fast.

Example: with h(k)=k mod 7, the keys 12, 19, and 26 all land in bucket 5, because each leaves remainder 5. The hash table has not failed; collision handling is part of the design. The danger is not one collision, but too many collisions in the same bucket, which turns lookup back into a small linear search.

What makes a hash function good?

For a hash table, a good hash function is:

• Deterministic: the same key always gives the same hash.
• Uniform enough: common inputs spread across buckets instead of clustering.
• Fast: hashing should be cheaper than the search it replaces.
• Consistent with equality: if two keys are equal, they must hash to the same value.

A hash function does not need to be random, and it does not need to avoid all collisions. It needs to make collisions rare enough that buckets stay short.

Resizing

When the load factor gets too high, the table allocates more buckets and rehashes every key into the larger table. That resize is expensive in the moment, but it happens occasionally; spread over many insertions, hash-table insert remains amortized O(1).