Hash TableHash tables

01Why it exists

Reach for it when you see:Look a value up by key, deduplicate, check whether something has been seen, caching, O(1) lookup, keys that are not consecutive integers.

02The core idea

An array is addressed by position, but real-world keys are strings, IDs and coordinates, not integers from 0 to n−1. A hash table runs a hash function over an arbitrary key to turn it into an integer, then takes that modulo the capacity to get the number of the bucket the key belongs in. A lookup becomes: hash once, jump straight to that bucket. O(1) on average.

Two different keys can land in the same bucket, which is a collision. The most common fix is separate chaining: each bucket holds a short list, colliding keys are strung together, and a lookup walks the chain comparing keys. The other is open addressing: on a collision, probe forward for the next free slot (this is what Python's dict does). Either way, the chain or the probe sequence has to stay short.

What keeps it short is the load factor — the number of elements divided by the number of buckets. When it passes a threshold (usually 0.75), double the bucket count and re-place every element, which is called a rehash. That costs O(n), but it happens half as often each time n doubles, so amortised, each insertion is still O(1). It is the same argument as growing a dynamic array. The worst case (every key colliding into one bucket) is O(n), which is why we say "O(1) on average" rather than "O(1), always"; a good hash function makes the worst case practically impossible.

The price is that a hash table has no order: you cannot ask for "the smallest key greater than k" or iterate in sorted order. When you need order, use a balanced tree (map in C++) — which belongs to the chapter on trees.

03The algorithm

1. 1Compute h = hash(key), and the bucket number b = h % capacity.
2. 2Lookup: walk the chain in bucket b comparing keys; return the value on a match, and reaching the end means the key is absent. The average chain length is the load factor, so this is O(1).
3. 3Insertion: search as in step 2 first. If the key is there, overwrite it; if not, append to the end of the chain and increment the element count.
4. 4After inserting, check the load factor: if it is over the threshold, double the capacity and re-place every existing key using hash % new capacity.
5. 5Deletion: find the entry and unlink it from the chain. Open addressing has to leave a tombstone marker behind when deleting, while chaining does not — which is why chaining is the easier one to teach.

04Interactive demo

Insert keys starting from 4 buckets and watch collisions build up chains. Once the load factor passes 0.75, the bucket count doubles, every key is redistributed, and the chains get short again.

05Code

A hash table with separate chaining written from scratch, walking through get, put, remove and rehash, followed by the built-in containers you should actually reach for in practice.

class HashMap:
    """Separate chaining: each bucket is a list of (key, value) pairs."""

    MAX_LOAD = 0.75

    def __init__(self, capacity=4):
        self.capacity = capacity
        self.size = 0
        self.buckets = [[] for _ in range(capacity)]

    def _index(self, key):
        return hash(key) % self.capacity        # hash function -> bucket number

    def get(self, key, default=None):
        for k, v in self.buckets[self._index(key)]:   # only this one bucket
            if k == key:
                return v
        return default

    def put(self, key, value):
        bucket = self.buckets[self._index(key)]
        for i, (k, _) in enumerate(bucket):
            if k == key:                            # already present: overwrite
                bucket[i] = (key, value)
                return
        bucket.append((key, value))                 # new key: append to the end of the chain
        self.size += 1
        if self.size / self.capacity > self.MAX_LOAD:
            self._rehash()

    def remove(self, key):
        bucket = self.buckets[self._index(key)]
        for i, (k, _) in enumerate(bucket):
            if k == key:
                bucket.pop(i)
                self.size -= 1
                return True
        return False

    def _rehash(self):
        # Double the capacity and re-bucket every key. O(n), but amortised each put is still O(1)
        old = self.buckets
        self.capacity *= 2
        self.buckets = [[] for _ in range(self.capacity)]
        for bucket in old:
            for k, v in bucket:
                self.buckets[self._index(k)].append((k, v))


# In real code, reach for the built-in dict / set: they are hash tables
m = {}
m["alice"] = 30          # O(1) average
m.get("bob", 0)          # O(1) average
"alice" in m             # O(1) average
del m["alice"]           # O(1) average

06Practice

• LeetCode 705Design HashSetEasy
• LeetCode 706Design HashMapEasy
• LeetCode 217Contains DuplicateEasy
• LeetCode 380Insert Delete GetRandom O(1) (a hash table plus an array)Medium
• LeetCode 146LRU Cache (a hash table plus a doubly linked list)Medium