Hash table¶

Turn each key into a number (its hash), and use that number to pick one of many buckets. To find the key later, compute the same number and look in just that bucket.

Insert / look up / delete	Worst case	Extra space	Keeps order
\(O(1)\) on average	\(O(n)\) if many keys collide	\(O(n)\)	no

The idea¶

A library with a million books could find any book instantly if each title told you its shelf. A hash function does exactly that: it turns a key such as "mars" into a large number, and the number modulo the number of buckets says which bucket the key lives in. Looking a key up means computing its hash again and checking one bucket, not the whole collection.

Two different keys may land in the same bucket: a collision. With separate chaining, each bucket keeps a short list of the keys that landed there. As long as the hash spreads keys evenly and the table grows when it gets full (here, when there are more than 0.75 keys per bucket on average), each list stays short, so every operation is \(O(1)\) on average.

This is how Python's dict and set, Java's HashMap and C++'s unordered_map work (Python uses open addressing, a cousin of chaining; see below).

How it works¶

Hash: for a string \(s_0 s_1 \ldots s_{m-1}\), \(h = s_0 \cdot 31^{m-1} + s_1 \cdot 31^{m-2} + \cdots + s_{m-1}\), kept to 32 bits (exactly Java's String.hashCode).
Put: find bucket h % buckets; if the key is in its list, replace the value, else append it. If the load factor passes 0.75, double the buckets and re-insert every key.
Get: scan the one bucket's list.

Code¶

PythonJavaC++

class HashMap:
    """A hash table with separate chaining: each bucket holds a short list of (key, value) pairs."""
    def __init__(self):
        self.buckets = [[] for _ in range(8)]
        self.size = 0

    def _bucket(self, key):
        return self.buckets[hash_str(key) % len(self.buckets)]

    def put(self, key, value):
        b = self._bucket(key)
        for i, (k, _) in enumerate(b):
            if k == key:
                b[i] = (key, value)          # key already there: replace its value
                return
        b.append((key, value))
        self.size += 1
        if self.size > 0.75 * len(self.buckets):   # too full: double the buckets
            self._resize(2 * len(self.buckets))

    def get(self, key, default=None):
        for k, v in self._bucket(key):
            if k == key:
                return v
        return default

    def _resize(self, n):
        old = self.buckets
        self.buckets = [[] for _ in range(n)]
        for b in old:
            for k, v in b:
                self.buckets[hash_str(k) % n].append((k, v))


def hash_str(s):
    """Polynomial string hash, the same as Java's String.hashCode, kept to 32 bits."""
    h = 0
    for ch in s:
        h = (31 * h + ord(ch)) & 0xFFFFFFFF
    return h


if __name__ == "__main__":
    text = "the quick brown fox jumps over the lazy dog the end"
    m = HashMap()
    for w in text.split():
        m.put(w, m.get(w, 0) + 1)
    for w in sorted(set(text.split())):
        print(w, m.get(w))
    print("buckets:", len(m.buckets), "keys:", m.size, "missing:", m.get("cat", 0))
    print(hash_str("abc"))

import java.util.ArrayList;
import java.util.List;
import java.util.TreeSet;

public class HashTable {
    /** A hash table with separate chaining: each bucket holds a short list of (key, value) pairs. */
    static class HashMap {
        record Entry(String key, int value) {}
        List<List<Entry>> buckets = newBuckets(8);
        int size = 0;

        static List<List<Entry>> newBuckets(int n) {
            List<List<Entry>> b = new ArrayList<>();
            for (int i = 0; i < n; i++) b.add(new ArrayList<>());
            return b;
        }

        List<Entry> bucket(String key) { return buckets.get((int) (hashStr(key) % buckets.size())); }

        void put(String key, int value) {
            List<Entry> b = bucket(key);
            for (int i = 0; i < b.size(); i++)
                if (b.get(i).key().equals(key)) { b.set(i, new Entry(key, value)); return; }  // replace
            b.add(new Entry(key, value));
            size++;
            if (size > 0.75 * buckets.size()) resize(2 * buckets.size());   // too full: double the buckets
        }

        int get(String key, int dflt) {
            for (Entry e : bucket(key)) if (e.key().equals(key)) return e.value();
            return dflt;
        }

        void resize(int n) {
            List<List<Entry>> old = buckets;
            buckets = newBuckets(n);
            for (List<Entry> b : old)
                for (Entry e : b) buckets.get((int) (hashStr(e.key()) % n)).add(e);
        }
    }

    /** Polynomial string hash, the same as Java's String.hashCode, read as an unsigned 32-bit number. */
    static long hashStr(String s) {
        long h = 0;
        for (char ch : s.toCharArray()) h = (31 * h + ch) & 0xFFFFFFFFL;
        return h;
    }

    public static void main(String[] args) {
        String text = "the quick brown fox jumps over the lazy dog the end";
        HashMap m = new HashMap();
        for (String w : text.split(" ")) m.put(w, m.get(w, 0) + 1);
        for (String w : new TreeSet<>(List.of(text.split(" ")))) System.out.println(w + " " + m.get(w, 0));
        System.out.println("buckets: " + m.buckets.size() + " keys: " + m.size + " missing: " + m.get("cat", 0));
        System.out.println(hashStr("abc"));
    }
}

#include <cstdint>
#include <iostream>
#include <set>
#include <sstream>
#include <string>
#include <utility>
#include <vector>
using namespace std;

// Polynomial string hash, the same as Java's String.hashCode, read as an unsigned 32-bit number.
uint32_t hashStr(const string& s) {
    uint32_t h = 0;
    for (unsigned char ch : s) h = 31 * h + ch;      // unsigned arithmetic wraps at 2^32
    return h;
}

// A hash table with separate chaining: each bucket holds a short list of (key, value) pairs.
struct HashMap {
    vector<vector<pair<string, int>>> buckets = vector<vector<pair<string, int>>>(8);
    size_t size = 0;

    vector<pair<string, int>>& bucket(const string& key) { return buckets[hashStr(key) % buckets.size()]; }

    void put(const string& key, int value) {
        auto& b = bucket(key);
        for (auto& kv : b)
            if (kv.first == key) { kv.second = value; return; }   // key already there: replace its value
        b.emplace_back(key, value);
        size++;
        if (size > 0.75 * buckets.size()) resize(2 * buckets.size());   // too full: double the buckets
    }

    int get(const string& key, int dflt) {
        for (auto& kv : bucket(key)) if (kv.first == key) return kv.second;
        return dflt;
    }

    void resize(size_t n) {
        vector<vector<pair<string, int>>> old(n);
        old.swap(buckets);
        for (auto& b : old)
            for (auto& kv : b) buckets[hashStr(kv.first) % n].push_back(kv);
    }
};

int main() {
    string text = "the quick brown fox jumps over the lazy dog the end", w;
    HashMap m;
    set<string> words;
    istringstream in(text);
    while (in >> w) { m.put(w, m.get(w, 0) + 1); words.insert(w); }
    for (auto& x : words) cout << x << " " << m.get(x, 0) << "\n";
    cout << "buckets: " << m.buckets.size() << " keys: " << m.size << " missing: " << m.get("cat", 0) << "\n";
    cout << hashStr("abc") << "\n";
}

Output: each of the 9 distinct words with its count ("the" 3 times), then buckets: 16 keys: 9 missing: 0 (the table doubled from 8 when the 7th key arrived), then 96354, the hash of "abc": \(97 \cdot 31^2 + 98 \cdot 31 + 99\).

When to use it¶

Counting and grouping: word frequencies, votes, anagram groups.
Seen-before checks: removing duplicates, detecting cycles, the "last seen" map of a sliding window.
Caching (memoization) in dynamic programming.
Two-sum in \(O(n)\): for each value \(x\), check whether \(t - x\) is already in a set.
Not when you need keys in sorted order, the smallest key, or range queries: use a search tree instead.

Common mistakes¶

Mutable keys: changing a key after inserting it (say, a list) changes its hash, and it is lost. Python forbids lists as keys for this reason.
Overriding equals without hashCode in Java: equal objects then land in different buckets.
Relying on iteration order: it is not sorted, and in most libraries it can change as the table grows. (Python's dict keeps insertion order since 3.7, but that is a Python promise, not a hash-table one.)
Adversarial input: an attacker who knows the hash function can send many keys that collide, turning \(O(1)\) into \(O(n)\). Languages now randomize string hashes (Python since 3.3) to prevent this.

Going deeper¶

Each part below starts closed; open the ones you want.

Sample walkthrough: hashing a few words into 8 buckets

Word	Hash (\(\bmod 2^{32}\))	Bucket (\(\bmod 8\))
the	114801	1
quick	107947501	5
brown	94011702	6
fox	101583	7
jumps	101487109	5: collides with "quick", the list grows
over	3423444	4
the	114801	1: already there, count becomes 2
lazy	3314548	4: collides with "over"

"lazy" is the 7th distinct key, which pushes the load past \(0.75 \times 8 = 6\), so the table doubles to 16 buckets and every key is placed again by its hash mod 16.

The math: why the average is O(1)

Simple uniform hashing. Assume each key is equally likely to go to any of the \(m\) buckets, independently. With \(n\) keys, the load factor is \(\alpha = n/m\), and the expected length of any bucket's list is \(\alpha\). So:

\[ \mathbb{E}[\text{cost of an unsuccessful search}] = \Theta(1 + \alpha), \qquad \mathbb{E}[\text{cost of a successful search}] = \Theta\!\left(1 + \tfrac{\alpha}{2}\right). \]

Keeping \(\alpha \le 0.75\) by doubling (an \(O(1)\) amortized cost, as for a growing array) makes every operation \(O(1)\) on average.

The birthday paradox says collisions come early: with \(m\) buckets, the first collision is expected after only about \(\sqrt{\pi m / 2}\) keys. With 365 buckets, that is about 24. So collisions must be handled, not avoided.

Universal hashing. Pick the hash function at random from a family where any two different keys collide with probability at most \(1/m\), for example \(h_{a,b}(k) = ((ak + b) \bmod p) \bmod m\) for a prime \(p\) and random \(a \ne 0\), \(b\). Then the expected cost is \(O(1 + \alpha)\) for every input, even one chosen by an adversary who does not know \(a\) and \(b\).

Open addressing (no lists: on a collision, try the next slot) with load \(\alpha < 1\) needs about \(\frac{1}{1-\alpha}\) probes for an unsuccessful search under uniform hashing: 4 probes at \(\alpha = 0.75\).

Watch it step by step

Each row is a bucket; red is the entry just written. (To keep the picture small it stays at 8 buckets; the code doubles to 16 when the 7th key arrives.)

Variations and related ideas

Open addressing: linear probing (fast on modern caches), quadratic probing, double hashing.
Robin Hood hashing and Swiss tables (Google's absl::flat_hash_map, Rust's HashMap) keep probe sequences short and use SIMD to check many slots at once.
Cuckoo hashing: two hash functions, two possible slots per key; look-ups take at most 2 probes.
Bloom filters answer "maybe present / surely absent" in a tiny bit array.
Consistent hashing spreads keys over servers so that adding a server moves few keys.
Cryptographic hashes (SHA-256) are a different tool: much slower, but built so that collisions cannot be found on purpose.

References¶

T. H. Cormen et al., Introduction to Algorithms, 4th ed., Chapter 11 (hash tables).
J. L. Carter, M. N. Wegman, "Universal classes of hash functions", Journal of Computer and System Sciences 18(2), 1979.
D. E. Knuth, The Art of Computer Programming, Vol. 3, 2nd ed., §6.4 (hashing).