Hash Tables: Hashing, Collisions, Load Factor, and Amortized Cost

For two weeks we sorted things so we could find them faster. This week we skip the sorting and find things instantly anyway. The trick is called a hash table, and you have used one every time you wrote a Python dictionary. By Thursday you will know how it works inside, why it is fast, when it gets slow, and how to build one yourself — and, in Project 2, how to break one on purpose.

Session planHow we will spend the two sessions

Section 1Finding things instantly

Here is the problem. You have a lot of things, each with a name, and you want to find one by its name. A phone number by a person's name. A student record by an ID. A word's definition by the word.

The simplest plan is to keep everything in a list and look through it from the start until you find the right one. That works, but it is slow when the list is long. If there are a million names, you might check a million names. In Notes 02's words, that is linear time: the work grows in step with the size of the list.

A smarter plan is to sort the list first and use binary search — the halving trick from Notes 02 and Notes 03. That is much faster: about 20 checks for a million names. But it still takes more steps as the list grows, and keeping the list sorted while you add new names is a chore.

Now think about a coat check at a theater. You hand over your coat and get a ticket with a number on it: 47. When you come back, the attendant does not search through every coat. They read the 47, walk to hook 47, and grab your coat. One step. It does not matter if there are 50 coats or 500 — it is still one walk to one hook.

A few words we will use all week:

• A key is the name you look things up by — "cat", a student ID, a phone number.
• A value is the thing stored with that key — the definition, the record, the coat.
• A bucket (or slot) is one numbered spot in the table — one hook.

You already use hash tables every day. Python's dict and set are both hash tables:

ages = {"ana": 20, "ben": 22, "cho": 19}   # a dict: keys → values
print(ages["ben"])        # 22 — straight to the right bucket
print("dan" in ages)     # False — also instant

seen = {"ana", "ben"}        # a set: just keys, no values
seen.add("cho")

names_list = ["ana", "ben", "cho"]
print("dan" in names_list)   # False — but Python had to check every item

The two in checks look the same, but they are not. On the dict, Python jumps to one bucket. On the list, Python walks the whole list. With a few items you will never notice. With a million, the list version is a million times more work. This is one of the most common speed-ups in real code: "I was checking x in some_list inside a loop — I switched it to a set and it went from minutes to seconds."

Notice the words "on average" in the last row. Hold on to them. Most of this week is about what that phrase really means and what can spoil it.

Section 2Hash functions: a key in, a shelf number out

Think of a library. Every book has a call number, and the call number tells you which shelf to walk to. You never search the whole library. A hash function is the rule that gives every key its "call number."

Let's hash the word "cat" by hand, the same way the demos below do it. Every character already has a number code inside the computer (in Python, ord("c") is 99). We start at 0 and, for each letter, multiply what we have by 31 and add the letter's code:

Why multiply by 31? It stirs the letters together, so that every letter and its position changes the result. "cat" and "act" use the same letters but get different hashes. (31 is just a traditional choice; many odd numbers work.)

The last line uses %, Python's remainder operator (also called "mod"). 98262 % 8 asks: "if you split 98,262 into groups of 8, how many are left over?" The answer is always between 0 and 7 — exactly the bucket numbers of an 8-bucket table. Think of a clock: count past 12 and you wrap back around. Mod wraps a big number around the table until it fits.

What makes a good hash function

A hash function has three jobs. Keep these in your head; Project 2 is built on what happens when one of them fails.

1. Same key, same number — every time. If "cat" went to bucket 6 when you stored it, it had better go to bucket 6 when you look for it. Otherwise you would walk to the wrong hook.
2. Spread keys out. Different keys should land in different buckets as much as possible, like guests spread across a whole hotel instead of all crammed into room 1. (Section 7 shows what happens when this fails.)
3. Be fast. The whole point is speed. A hash function that takes longer than scanning the list is useless.

Job 1 has a surprising consequence: keys must not change while they are in the table. If you could edit a key after storing it, its hash would change, and it would be sitting in the wrong bucket forever. That is why Python lets you use strings, numbers and tuples as dict keys, but not lists — lists can be edited:

spots = {}
spots[(3, 4)] = "treasure"     # a tuple can't change — fine as a key
spots[[3, 4]] = "treasure"     # TypeError: unhashable type: 'list'

Section 3Collisions happen

Try hashing "dog" and "owl" into our 8-bucket table. Both land in bucket 4. Two different keys, one bucket. This is called a collision.

Can a cleverer hash function avoid collisions completely? No, and the reason is simple. There are endless possible keys — every word, every name, every ID — but the table has only so many buckets. If a coat check has 100 hooks and 101 coats show up, at least two coats must share a hook. No ticket system can prevent that.

The surprise is that collisions show up long before the table is full. Think of a birthday party. How many guests do you need before two of them probably share a birthday? Most people guess around 180 — half of 365. The real answer is 23. The trick is that you are not asking whether someone matches you; you are asking whether any two people match. With 23 guests there are already 253 different pairs of people, and each pair is a fresh chance for a match.

A hash table is the same party: the buckets are the days of the year, and the keys are the guests. Even in a big, mostly empty table, a few keys will bump into each other. So a hash table cannot just hope collisions never happen. It needs a plan for when they do. That plan is the next section.

Section 4Two ways to handle collisions

Plan A — Chaining: every bucket holds a little list

Picture a coat check where each hook holds a small rack instead of a single coat. If two coats get ticket 4, both go on rack 4. To find your coat, the attendant walks to rack 4 and looks through the few coats hanging there.

That is chaining (also called separate chaining). Each bucket holds a small list — a chain — of all the keys that landed there.

• Insert: hash the key, go to its bucket, add the key to that bucket's list (unless it is already there).
• Search: hash the key, go to its bucket, look through that one short list.
• Delete: hash the key, go to its bucket, remove it from that list.

The important point: you only ever look through one bucket's list, never the whole table. If the keys are spread out well, each list is short — usually zero, one or two keys.

Plan B — Linear probing: take the next free spot

Now picture a hotel with one guest per room. Your booking says room 4, but room 4 is taken. The front desk says: "Try room 5." Taken too? "Try room 6." You keep walking down the hall until you find an empty room. If you reach the end of the hall, you wrap around to room 0.

That is open addressing: every key lives directly in a slot of the table, one key per slot. The simplest version is linear probing — if your slot is taken, try the next one, then the next. Each slot you try is called a probe, and the slot a key's hash points to is its home slot.

• Insert: go to the key's home slot. If it is taken, step forward until you reach a free slot, and put the key there.
• Search: go to the home slot and step forward, checking each slot, until you either find the key or hit an empty slot. An empty slot means "stop — the key is not here," because the key would have been placed there if nothing had been in the way.

The tricky part: deleting with linear probing

Deleting is where linear probing gets sneaky. Suppose "fox" and "ant" both have home slot 7. "fox" got there first, so "ant" stepped forward and wrapped around to slot 0. Now delete "fox" by simply emptying slot 7. Later you search for "ant": you go to slot 7, see an empty slot, and stop — "not here." But "ant" is there, one step further. Emptying the slot broke the trail.

The fix is a tombstone: instead of emptying the slot, you leave a small marker that says "someone used to be here — keep walking." Searches step over tombstones. Inserts are allowed to reuse a tombstone's slot. Tombstones get cleaned up for good the next time the table is rebuilt (Section 6). Chaining never needs tombstones, because removing a key from a little list doesn't hide anybody else.

Some things to try, in order:

1. In Chaining mode, search for owl. It shares bucket 4 with dog, so it takes two checks. Search for cat: one check.
2. Switch to Linear probing. The same five keys are inserted again. owl now lives in slot 5, one step past its home.
3. Insert ant. Its home is slot 7, which fox already has, so it wraps around to slot 0.
4. Delete fox, then search for ant. Watch the search step over the tombstone in slot 7 and still find ant.
5. Click Add a random word a few times. When the next key would push the table past 75% full, it grows from 8 to 16 buckets and every key is re-placed. Look at how the bucket numbers change.
6. Turn auto-resize off and keep adding. In chaining mode the lists get long. In probing mode the table eventually fills up completely and refuses new keys.

Section 5Load factor: how full is too full?

Load factor is the single most important number for how fast a hash table runs. As the table fills up, collisions get more common, and every collision means extra checks.

With chaining, the load factor is simply the average length of a chain. A load factor of 0.75 means the average bucket holds less than one key, so searching is quick. A load factor of 5 means chains of about five keys each — it still works, just slower. Chaining slows down gently as it fills, and it can even go past 100% full, because a bucket's list can always grow.

With linear probing, things go bad much faster. Think of a parking garage where you take the first free spot after your assigned one. Cars bunch up into long solid rows, called clusters. When a new car's spot is in the middle of a cluster, it has to drive past the whole cluster to find a space — and then it parks at the end, making the cluster even longer. Clusters grow, and the bigger they are, the faster they grow. And of course a probing table can never go past 100%: one key per slot.

Here is roughly how much looking it takes to learn that a key is not in the table (a "miss"), measured by experiment on a big table with a good hash:

Look at the last column. Between half full and 90% full, the work goes up about twenty times. That is why every real hash table picks a maximum load factor and grows before it gets there. Java's HashMap (which uses chaining) grows at 75% full. Python's dict (which uses a fancier kind of open addressing) grows when it is about two-thirds full. Our demo uses 75%.

Section 6Growing the table, and amortized cost

When the table gets too full, we make a bigger one and move everything into it. This is called resizing. The usual rule is: double the number of buckets.

There is a catch. You cannot just copy each key into the same bucket number, because the bucket came from "hash mod table size" — and the table size just changed. In a 16-bucket table, "cat" happens to stay in bucket 6 (98,262 % 16 is also 6), but "dog" moves from bucket 4 to bucket 12. So every key must be hashed again and placed into the new table. This is called rehashing. It is also when tombstones finally disappear: we only move the real keys.

Rehashing touches every key, so a resize is slow: with a million keys, that one insert has to move a million keys. Doesn't that ruin our "constant time" story?

The moving-apartments story

Imagine you collect books. Your apartment fits 4 books. When book 5 arrives, you move to an apartment that fits 8 — and moving means carrying all 4 old books. When book 9 arrives, you move to one that fits 16, carrying 8 books. Then 32, carrying 16. Moving day is hard work. But look how rare moving days become: each move gives you as much new room as you had in total before. Most days, a new book just goes on the shelf.

Now add up all the work you ever did. To reach 64 books you carried 4 + 8 + 16 + 32 = 60 books during moves, plus 64 books shelved when they arrived. That is 124 units of work for 64 books — under 2 per book. Grow to a million books and the answer is still under 3 per book. The occasional expensive move, spread over all the cheap days before it, adds only a small, fixed amount to each book.

The savings-jar story

Here is another way to see it. Pretend every insert must pay 3 coins, no matter what. A normal insert really costs just 1 coin, so it drops the other 2 into a savings jar. When moving day comes, the jar pays for carrying the old books. With doubling, the jar never runs out: between two moves, enough cheap inserts happen to save up for the next move. So 3 coins per insert always covers everything. The demo below keeps an eye on the jar for you.

Press Play and watch the shape. The red spikes get taller each time (more keys to move), but they also get further apart. The blue average line jumps up a little at each spike and then sinks back, and it never climbs above the green 3-coin line. Now switch to Add 4 more slots. The spikes come every 4 inserts forever, the blue line keeps climbing, and the savings jar runs dry. Growing by a fixed amount means moving day comes just as often no matter how big you get, so the cost per insert keeps rising. Growing by a multiple (doubling, or even 1.5×) is what keeps the average flat.

Section 7Bad hash functions

Everything good about hash tables depends on job 2 from Section 2: spread the keys out. Let's see what happens when a hash function fails at it.

The worst possible hash sends every key to bucket 0. The table still works — every key can still be found — but now bucket 0 holds one long chain with everything in it. Finding a key means walking that chain from the start. That is just a list scan in disguise: linear time, the very thing we were trying to escape. Hash functions that only look at part of the key are milder versions of the same problem. The demo below runs five hash functions on the same list — the names of the 50 US states — in a 16-bucket chaining table.

"Number of letters" is a great example of a hash that looks reasonable. It does job 1 perfectly. But state names are between 4 and 14 characters long, so several buckets can never be used, and the 12 states with exactly 8 letters all pile into bucket 8. "First letter" ignores everything after the first letter, so the eight states that start with M share one bucket and the eight that start with N share another — and no bigger table can ever separate them. "Add up the letters" does fine on this list, but it has a hidden flaw: words made of the same letters ("dog" and "god", "listen" and "silent") always collide, because adding doesn't care about order. The ×31 recipe stirs in each letter's position, so it avoids that trap. Notice that even the good hash is not perfectly even: a fair hash scatters keys like random throws, and random throws always make small lumps — the birthday party again. "Good" means no big pile-ups, not perfection.

Section 8Build one in Python

Here is a complete hash table using chaining, with resizing at 75% full. It is short on purpose. Read it slowly — every line is one of the ideas above. It works like a small dict: put stores a value under a key, get looks one up, remove deletes one.

MAX_LOAD = 0.75     # grow before the table gets more than 75% full


class HashTable:
    """A key → value map built from scratch, using chaining.

    Each bucket is a small Python list of (key, value) pairs.
    """

    def __init__(self, capacity=8, hash_fn=hash):
        self.buckets = [[] for _ in range(capacity)]   # empty racks
        self.size = 0                                  # keys stored
        self.hash_fn = hash_fn                         # swappable, for testing

    def _index(self, key):
        """Which bucket does this key belong in?"""
        return self.hash_fn(key) % len(self.buckets)

    def put(self, key, value):
        bucket = self.buckets[self._index(key)]
        for i, (k, v) in enumerate(bucket):
            if k == key:                         # already here: just update
                bucket[i] = (key, value)
                return
        if (self.size + 1) / len(self.buckets) > MAX_LOAD:
            self._resize(2 * len(self.buckets))        # make room first...
            bucket = self.buckets[self._index(key)]    # ...then find the NEW bucket
        bucket.append((key, value))
        self.size += 1

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

    def remove(self, key):
        bucket = self.buckets[self._index(key)]
        for i, (k, v) in enumerate(bucket):
            if k == key:
                del bucket[i]
                self.size -= 1
                return
        raise KeyError(key)

    def __contains__(self, key):              # makes  key in table  work
        return any(k == key for k, v in self.buckets[self._index(key)])

    def __len__(self):                         # makes  len(table)  work
        return self.size

    def _resize(self, new_capacity):
        old_buckets = self.buckets
        self.buckets = [[] for _ in range(new_capacity)]
        for bucket in old_buckets:                # rehash: every key gets
            for k, v in bucket:                    # a fresh bucket number
                self.buckets[self._index(k)].append((k, v))


def times31_hash(text):
    """The hash from Section 2 and the demos: times 31, plus the code."""
    h = 0
    for ch in text:
        h = h * 31 + ord(ch)
    return h


t = HashTable(hash_fn=times31_hash)
t.put("cat", 3)
t.put("dog", 5)
t.put("cat", 4)                    # updates — no second "cat"
print(t.get("cat"), len(t))         # 4 2
print("owl" in t)                  # False
print(times31_hash("cat") % 8)    # 6 — same bucket as the demo

Three details worth pointing at:

• put checks for the key before adding. Storing "cat" twice must update it, not create a second copy. Forgetting this is one of the most common bugs in hand-built tables.
• After a resize, put looks up the bucket again. The old bucket belonged to the old table. Using it would drop the key somewhere get can never find it.
• _resize doesn't change size. It moves the same keys into a bigger table; the count stays the same.

def test_everything_collides():
    t = HashTable(hash_fn=lambda key: 0)    # the worst hash, on purpose
    for word in ["ant", "bee", "cat"]:
        t.put(word, len(word))
    t.remove("bee")
    assert "bee" not in t
    assert t.get("cat") == 3
    assert len(t) == 2

def test_many_keys_survive_resizing():
    t = HashTable()
    for i in range(1000):                    # forces several resizes
        t.put(i, i * i)
    assert len(t) == 1000
    for i in range(1000):
        assert t.get(i) == i * i

Section 9When not to use a hash table

Hash tables are amazing at one question: "Is this exact key here, and what is stored with it?" They are bad at almost every question about order, because hashing deliberately scatters keys all over the table. Words that sit next to each other in the dictionary end up in random, unrelated buckets.

• Sorted order. "List all students alphabetically." A hash table has no idea; you would have to pull everything out and sort it.
• Ranges. "Every score between 80 and 90." A hash table can only answer this by checking every key.
• Smallest, largest, or nearest. "Who has the earliest deadline?" "What's the closest price to $20?" Again, a full scan.
• Hard speed promises. A hash table is fast on average, and each resize is a pause. If even one slow operation is unacceptable, you may want a structure with a firm worst-case guarantee.

All four of these are what trees are good at. A balanced binary search tree keeps keys in sorted order and answers "find," "range," "smallest" and "next one up" in a number of steps that grows only slowly with the size — like binary search, but on a structure you can keep adding to. A heap hands you the smallest item right away. That is next week.

Section 10Before next week