How Hash Tables Work: Where O(1) Lookup Comes From

A dictionary lookup feels like it should be impossible. The table holds a million keys, you ask for one, and the answer comes back without looking at the other 999,999. Nothing was sorted. Nothing was scanned. Where did the work go?

It went into the key itself — and once you have written the twenty lines that do it, half the "use a hash map" answers in interviews stop being a reflex and start being a decision.

The problem it solves

An array gives you O(1) access by position. nums[7] is one address calculation, no matter how long the array is.

But you almost never know the position. You know a name, an id, a URL. So the question becomes: can you turn the thing you know into a position you can index?

That is the whole idea. A hash function turns a key into a number; the number, taken modulo the table size, is a slot. Lookup becomes arithmetic plus one array access — and arithmetic does not care how much data you have.

The intuition

Three moving parts, and each one can fail on its own:

1. The hash function turns a key of any shape into an integer. It must be deterministic — the same key must always produce the same number, or you could never find anything again.
2. The modulo folds that integer into the range of slots the table actually has.
3. The bucket handles the inevitable: two different keys landing in the same slot. Store a small list per slot and search it.

Step three is the honest part of the story. Slots are finite and keys are not, so collisions are not a flaw, they are arithmetic. The design goal is never "no collisions" — it is "few enough that the bucket search stays short".

Watch it run

Follow one key at a time: it is hashed, folded into a slot, and dropped into that bucket. Coral is the key being placed right now.

Watch what happens when a slot already has something in it. That second entry does not overwrite and does not fail — it joins a chain, and every future lookup for either key has to walk that chain.

The code

def tiny_hash(key):
    """Deliberately small and deliberately readable."""
    total = 0
    for ch in key:
        total = total * 31 + ord(ch)
    return total


class TinyTable:
    def __init__(self, size=8):
        self.buckets = [[] for _ in range(size)]

    def _index(self, key):
        return tiny_hash(key) % len(self.buckets)

    def put(self, key, value):
        bucket = self.buckets[self._index(key)]
        for i, (k, _) in enumerate(bucket):
            if k == key:
                bucket[i] = (key, value)   # replace, never duplicate
                return
        bucket.append((key, value))

    def get(self, key):
        for k, v in self.buckets[self._index(key)]:
            if k == key:
                return v
        raise KeyError(key)


table = TinyTable()
for name, year in [("ada", 1815), ("alan", 1912),
                   ("grace", 1906), ("edsger", 1930)]:
    table.put(name, year)

print(table.get("grace"))                         # 1906
print([table._index(n) for n in ["ada", "alan", "grace", "edsger"]])
# [6, 0, 0, 0]
print([len(b) for b in table.buckets])
# [3, 0, 0, 0, 0, 0, 1, 0]

Four keys, eight slots, and three of them landed in slot 0. That is not a contrived example — it is what this hash and this table size do to those four strings. A get("edsger") now compares against two other keys before it finds its own.

What the complexity actually says

Average case: O(1) for get, put and delete. With a decent hash and a table sized to the data, buckets hold a small constant number of entries, so the chain walk is constant work.

Worst case: O(n). If every key hashes to the same slot, the table degenerates into one list and every lookup scans it. Real implementations fight this with better hash functions, randomised seeds, and by resizing: when the load factor — entries divided by slots — crosses a threshold, allocate a bigger array and rehash everything into it.

That resize is O(n) work, which sounds like it ruins the O(1) claim. It does not, because doubling means the cost is spread over the n insertions that made it necessary. Averaged out, each insertion still pays constant time. That is what "amortised O(1)" means, and saying the word amortised in an interview is worth doing.

Space: O(n). A hash table trades memory for time, deliberately and always.

Where it goes wrong

• Mutable keys. Store an entry under a key, then mutate the key. Its hash changes, the lookup goes to a different slot, and the entry is unreachable while still occupying memory. This is why Python rejects a list as a dictionary key.
• Assuming iteration order is the hash's doing. Python dictionaries preserve insertion order; that is a language guarantee, not a property of hashing. A set gives you no such promise, and code that depends on set order breaks between runs.
• Reaching for a hash map when order matters. It gives you membership and counting, not "the smallest", not "the next one". If the question needs a ranking, you want a heap or a sorted structure.
• Hashing what you cannot afford to hash. The hash reads the whole key. For long strings that is real work per lookup — constant in n, but not free — which matters inside a hot loop.
• Counting in as always constant. x in some_list is a linear scan. x in some_set is a hash lookup. Same keyword, different complexity class, and mixing them up is the most common accidental O(n²) in an interview.

How to say it in an interview

Reach for the structure by naming the property you need:

"I need membership in constant time, so a set. The hash maps each value to a bucket, so a lookup is one hash plus a short bucket walk — O(1) on average, O(n) in the pathological case where everything collides. That gives me O(n) time overall with O(n) extra space. The alternative is sorting first and using two pointers, which is O(n log n) time and O(1) space — better if memory is the constraint rather than time."

Two structures, two cost profiles, one sentence choosing between them. That is the answer the question was asking for.