Hash Tables

The problem hash tables solve#

Back in the introduction, we compared checking "does this ID exist?" using a plain list (O(n), check every element) versus a Python set (essentially O(1)). It's time to open up how that's possible. The answer is the hash table — arguably the single most useful data structure in everyday programming, and the engine behind Python's dict and set.

Analogy: imagine a coat check at a theater. Instead of the attendant searching through every coat on the rack to find yours, you're handed a numbered ticket, and your coat is hung at that exact numbered spot. Retrieving your coat later doesn't require a search at all — the attendant reads your ticket number and walks straight to that spot. A hash table gives every piece of data its own "ticket number" mathematically, so retrieval never requires a search either.

How hashing actually works#

A hash table stores key-value pairs. Internally, it keeps an array of buckets (slots). To decide which bucket a given key belongs in, it runs the key through a hash function — a function that takes any input (a string, a number, any hashable value) and deterministically produces an integer (the hash code). That integer is then reduced (typically with a modulo operation) to fit within the bucket array's size, giving a bucket index.

def simple_hash(key: str, num_buckets: int) -> int:
    total = sum(ord(char) for char in key)   # a (very naive) hash: sum of character codes
    return total % num_buckets               # squeeze it into a valid bucket index

print(simple_hash("apple", 10))   # always the same bucket index for "apple"
print(simple_hash("banana", 10))  # a different (usually) bucket index for "banana"

Real hash functions (like the ones Python uses internally for strings, ints, and tuples) are far more carefully engineered than this example — they aim to spread keys as evenly as possible across buckets and to avoid predictable patterns — but the core idea is identical: the same key always produces the same bucket index, computed directly, with no searching involved.

This gives you the mechanism behind O(1) lookup: to find a key's value, compute its hash, jump straight to that bucket, and (assuming no collision) the value is right there.

Collisions, and handling them with chaining#

Two different keys can, by pure bad luck (or a poorly designed hash function), land in the same bucket — this is called a collision, and every hash table implementation needs a strategy for it. The most common strategy is chaining: instead of a bucket holding one item directly, each bucket holds a small list of (key, value) pairs — everything that happens to hash to that index. Looking something up means: compute the hash, go to that bucket, then do a short linear scan through that bucket's (hopefully very short) list to find the exact matching key.

class SimpleHashTable:
    def __init__(self, num_buckets=8):
        self.num_buckets = num_buckets
        self.buckets = [[] for _ in range(num_buckets)]   # each bucket is a list (chain)

    def _hash(self, key):
        return hash(key) % self.num_buckets

    def put(self, key, value):
        index = self._hash(key)
        chain = self.buckets[index]
        for i, (existing_key, _) in enumerate(chain):
            if existing_key == key:
                chain[i] = (key, value)     # update existing key
                return
        chain.append((key, value))          # new key: append to this bucket's chain

    def get(self, key):
        index = self._hash(key)
        chain = self.buckets[index]
        for existing_key, value in chain:
            if existing_key == key:
                return value
        raise KeyError(key)


table = SimpleHashTable()
table.put("name", "Ava")
table.put("age", 21)
print(table.get("name"))  # "Ava"
print(table.get("age"))   # 21

Average-case O(1) vs worst-case O(n)#

Here's the honest, precise claim: hash table lookup is O(1) on average, not always. If a hash function distributes keys well and the table isn't overloaded, each bucket's chain stays very short (often 0 or 1 items), so get/put really do run in roughly constant time. But in the worst case — a bad hash function, or an adversarial set of keys that all happen to collide into the same bucket — every key could end up in a single bucket's chain, degrading lookup to a full linear scan: O(n).

This is why real hash table implementations invest heavily in good hash functions and in resizing: once the table gets too full (a high "load factor" — roughly, number of items / number of buckets), it allocates a bigger bucket array and re-distributes everything, keeping chains short and average-case performance close to O(1). You don't need to implement this yourself — Python's dict and set already do it — but understanding why it's necessary is what separates "I memorized dict is fast" from "I understand why dict is fast, and when it might not be."

Python's dict is a hash table#

Every time you write my_dict[key], key in my_dict, or my_dict[key] = value, you're using a production-grade, heavily optimized hash table — the exact mechanism described above, just far more refined:

ages = {}
ages["Ava"] = 21
ages["Sam"] = 19

print(ages["Ava"])       # O(1) average — direct bucket lookup, no scanning
print("Sam" in ages)     # O(1) average — membership check
del ages["Sam"]          # O(1) average — deletion works the same way

A set is essentially a dict that only stores keys, with no associated values — which is exactly why x in my_set is so much faster than x in my_list for large collections, as shown back in the introduction page.

One important requirement: keys must be hashable, meaning their hash value never changes during their lifetime. This is precisely why Python lists (mutable) can't be dictionary keys, but tuples (immutable) can.

cache = {}
cache[(1, 2)] = "valid — a tuple is hashable"

# cache[[1, 2]] = "invalid" — raises TypeError: unhashable type: 'list'

Classic problem: two sum#

Given a list of numbers and a target value, find the indices of the two numbers that add up to the target. For example, given [2, 7, 11, 15] and target 9, the answer is indices [0, 1], since 2 + 7 == 9.

The naive approach checks every pair of numbers directly — for each element, scan the rest of the list for a partner that completes the sum:

def two_sum_naive(nums, target):
    for i in range(len(nums)):
        for j in range(i + 1, len(nums)):
            if nums[i] + nums[j] == target:
                return [i, j]
    return None

This works, but it's O(n²) — for every one of the n elements, it scans up to the rest of the list again.

The hash map approach flips the question around: instead of asking "what's the other number for this one?", it remembers every number it has already seen (in a dict, mapping value → index) and checks, at each step, "have I already seen the complement I need?"

def two_sum(nums, target):
    seen = {}   # maps a number we've already seen -> its index

    for i, num in enumerate(nums):
        complement = target - num
        if complement in seen:              # O(1) average lookup
            return [seen[complement], i]
        seen[num] = i                        # remember this number for later

    return None


print(two_sum([2, 7, 11, 15], 9))   # [0, 1]  →  2 + 7 == 9

Trace it on [2, 7, 11, 15], target 9:

1. i=0, num=2. Complement needed: 9 - 2 = 7. Is 7 in seen? No. Remember seen = {2: 0}.
2. i=1, num=7. Complement needed: 9 - 7 = 2. Is 2 in seen? Yes — at index 0. Return [0, 1].

This solves the problem in a single pass, doing O(1) average work per element, for O(n) total time — a full order-of-magnitude improvement over the naive O(n²) approach. It costs O(n) extra space for the seen dictionary, which is the classic hash-table trade-off you'll see again and again: spend a bit of extra memory to turn repeated linear scans into single-step lookups.

Common mistakes#

• Assuming hash table operations are always O(1). They're O(1) on average; a pathological hash function or key distribution can degrade this to O(n). This is a favorite interview follow-up question for exactly this reason.
• Using a mutable type as a dictionary key. Lists can't be dict keys (they're unhashable) precisely because their contents — and therefore their hash — could change after insertion, which would break the bucket-lookup mechanism.
• Forgetting to check if complement in seen before inserting the current number, or inserting in the wrong order, which can cause a number to incorrectly pair with itself in some variations of these problems.
• Reaching for nested loops out of habit when a single pass with a hash map would do — "have I seen something related to this before?" is almost always a signal to reach for a dict.