Hash table explained: how it works, code and complexity

What problem a hash table solves

Suppose you store one million user records and need to find one by email. Scanning a list is O(n). Keeping the list sorted allows binary search in O(log n), but inserts become slow. A hash table finds the record in O(1) average time, no matter how many records there are, and inserts and deletes are just as fast.

That is why hash tables are everywhere: dictionaries and sets in programming languages, database hash indexes, caches, symbol tables in compilers, and deduplication.

The idea in plain words

Imagine a cloakroom with 100 numbered hooks. Instead of searching all hooks for your coat, the attendant computes a hook number from your name and goes straight there. The function that computes the number is the hash function. A good hash function is fast, always gives the same number for the same key, and spreads different keys evenly over the hooks.

1. Compute h = hash(key).
2. Pick the bucket: index = h % capacity.
3. Look only in that bucket for the key.

Worked example: collisions with chaining

Take a table with 4 buckets and a toy hash function: the sum of the letter positions (a = 1, b = 2, ...).

act and bee collide with cat. Looking up bee now means checking three entries in bucket 0. With a poor hash function (letter sums ignore order) or too few buckets, chains grow long and the table becomes slow. Real hash functions mix all bits of the key, and real tables grow when they get too full.

Python implementation with separate chaining

Each bucket is a list of [key, value] pairs. When the number of items exceeds 0.75 times the number of buckets (the load factor), the table doubles its capacity and re-inserts everything.

class HashTable:
    def __init__(self, capacity=8):
        self.buckets = [[] for _ in range(capacity)]
        self.size = 0
    def _bucket(self, key):
        return self.buckets[hash(key) % len(self.buckets)]
    def put(self, key, value):
        bucket = self._bucket(key)
        for pair in bucket:
            if pair[0] == key:
                pair[1] = value        # update existing key
                return
        bucket.append([key, value])
        self.size += 1
        if self.size > 0.75 * len(self.buckets):
            self._resize()
    def get(self, key, default=None):
        for k, v in self._bucket(key):
            if k == key:
                return v
        return default
    def delete(self, key):
        bucket = self._bucket(key)
        for i, (k, _) in enumerate(bucket):
            if k == key:
                bucket.pop(i)
                self.size -= 1
                return True
        return False
    def _resize(self):
        old = [pair for bucket in self.buckets for pair in bucket]
        self.buckets = [[] for _ in range(2 * len(self.buckets))]
        self.size = 0
        for k, v in old:
            self.put(k, v)

t = HashTable()
for i, word in enumerate(["red", "green", "blue", "cyan", "pink", "gold", "gray"]):
    t.put(word, i)
t.put("red", 100)
t.delete("blue")
print(t.get("red"), t.get("blue"), t.size, len(t.buckets))  # 100 None 6 16

Collision strategies compared

CPython's dict uses open addressing with a perturbed probe sequence and, since Python 3.7, guarantees that iteration follows insertion order. Java's HashMap uses chaining and turns long chains into balanced trees.

Time and space complexity

The O(1) average depends on a good hash function and a bounded load factor. Python randomizes string hashes per process (hash seeding) so that an attacker cannot easily send many keys that collide and slow a server down to O(n) per request.

Common mistakes

• Using a mutable object as a key, or defining __eq__ on a class without a matching __hash__. Objects that are equal must have equal hashes.
• Expecting sorted order. A hash table gives fast lookup, not order; use a sorted list or a balanced tree (a binary search tree) when you need range queries or the minimum key.
• Relying on hash() values across runs: string hashes change between Python processes unless PYTHONHASHSEED is fixed. Use hashlib for stable hashes.
• Treating a hash table as a security primitive. Hash tables use fast non-cryptographic hashes; passwords need dedicated password hashing functions.

When to use it and typical interview uses

Use a hash table whenever you need to answer "have I seen this?" or "what value belongs to this key?" quickly. Use a binary search tree or sorted array when you also need order, ranges or nearest keys.

Classic problems: two sum (store each number's index, look up target - x), counting frequencies (collections.Counter), grouping anagrams by sorted letters, detecting duplicates, and memoizing results in dynamic programming.

def two_sum(nums, target):
    seen = {}                      # value -> index
    for i, x in enumerate(nums):
        if target - x in seen:
            return seen[target - x], i
        seen[x] = i
    return None
print(two_sum([2, 7, 11, 15], 9))  # (0, 1)