AmouAI Hub/Courses/Data Structures & Algorithms/Chapter 8

Part 2 · Linear Structures · Chapter 8

Hash Tables

A coat check that computes your ticket number from your coat. Almost magic, entirely mundane once you see the arithmetic — and it explains why Python dicts are so fast.

Reading

CLRS Ch. 11

Focus

Key → address

Cost

average O(1)

Powers

dict · set · caches

By the end of this chapter you can

Explain how a key becomes an array index, in three steps
State why collisions are unavoidable and compare chaining with open addressing
Define load factor and describe what happens when it crosses the threshold
Say what makes a good hash function, and what makes a hashable key
Recognise the situations where a hash table's O(1) degrades to O(n)

1Computing the address instead of searching for it

Every fast structure so far turned a search into arithmetic. A hash table does it for arbitrary keys, not just integer positions.

The coat check

An ordinary coat check gives you ticket number 47 and files your coat in slot 47. To find it later the attendant reads the number and walks straight there.

Now imagine a coat check with no tickets. Instead, the attendant looks at your coat and computes a number from it — length, colour, buttons, whatever — and always gets the same number for the same coat. You do not need to remember anything. Turn up with the coat and the number is recomputed on the spot.

That is a hash table. The key is the ticket.

An array gets O(1) access because you supply an integer index. A hash table extends that to any key by inserting one step: turn the key into an integer first.

the_three_steps.py

key  ──hash()──▶  a big integer  ──% table_size──▶  a bucket index

"cherry"  ──▶  3195375433284198217  ──% 8──▶  1

# Three operations: hash the key, take the remainder, index the array.
# None of them depend on how many keys are stored. That is the O(1).

The three requirements of a hash function

Deterministic — the same key must always give the same number, or you could never find anything again.
Fast — it runs on every single operation. A slow hash function destroys the whole point.
Well spread — similar keys should land in unrelated buckets, so the table fills evenly.

Note what is not required: it does not have to be unique, and it does not have to be secure. Those are different jobs.

2Collisions are guaranteed

Two keys will land in the same bucket. Not might — will. So the interesting question is what happens next.

There are infinitely many possible strings and only table_size buckets. By the pigeonhole principle, collisions are not a flaw to be engineered away — they are arithmetic. Every hash table is really a collision-handling strategy with some hashing attached.

Strategy 1 — chaining

Each bucket holds a small list. Colliding keys are appended to it. Lookup finds the bucket, then scans its (short) list.

Strategy 2 — open addressing

No lists. If a bucket is taken, walk forward to the next free slot (linear probing). Everything lives in the one array.

	Chaining	Open addressing
Where colliding keys live	In a list hanging off the bucket	In another slot of the same array
Memory	Extra pointers per entry	One flat array — better cache behaviour
Load factor above 1	Fine, chains just get longer	Impossible — the array is full
Deletion	Straightforward	Needs tombstones, or lookups break
Weakness	Pointer chasing, cache misses	Clustering: runs of taken slots grow and merge
Used by	Java `HashMap`, most textbooks	Python `dict`, Rust, Google's dense maps

Why deletion is hard with open addressing

Suppose A and B collide, so B was probed into the next slot. Delete A and simply empty its slot — now a lookup for B finds an empty slot where A was, concludes the key is absent, and stops.

B is still sitting there, permanently unreachable. The fix is a tombstone: a marker meaning “empty, but keep probing.” If you ever implement open addressing, this is the bug you will hit.

3Load factor and rehashing

A hash table's performance is not fixed. It depends on how full the table is, and the table manages that itself.

The load factor is stored_keys / bucket_count. It is the single number that predicts how a hash table will behave:

Load factor	Chaining	Open addressing
0.25	Almost no collisions, memory wasted	Fast
0.50	Average chain ~0.5	Fast
0.75	Average chain ~0.75 — the usual threshold	Clustering starts to bite
0.90	Still workable	Probe sequences get long
1.00	Average chain 1	Table is full — no room at all
10.0	Chains of 10; effectively O(n)	Impossible

When the load factor crosses its threshold, the table rehashes: allocate an array roughly twice the size and reinsert every key. Reinsert, not copy — the bucket index is hash % size, and size just changed, so every key belongs somewhere new.

rehash.py

def _maybe_grow(self):
    if self._count / len(self._buckets) > 0.75:
        old = self._buckets
        self._buckets = [[] for _ in range(len(old) * 2)]
        self._count = 0
        for bucket in old:
            for k, v in bucket:
                self.put(k, v)        # recomputed index — NOT a memcpy

# This one operation is O(n). It is exactly the dynamic-array bargain
# from Chapter 3: rare, expensive resizes amortise to O(1) per insert
# because they get exponentially rarer as the table grows.

Lookup (average)

O(1)

Insert (amortised)

O(1)

Delete (average)

O(1)

Lookup (worst)

O(n)

Ordered traversal

O(n log n)

Space

O(n)

The worst case is real

If every key hashes to the same bucket, a chained table degenerates into one linked list and every operation becomes O(n). With random keys this essentially never happens — but an attacker who knows your hash function can craft keys that do, turning a web request into a denial-of-service.

That is why Python randomises string hashing per process, controlled by PYTHONHASHSEED. It is also why hash("a") gives a different number in each run — which surprises people, and is a security feature rather than a bug.

4What makes a key hashable

Not everything can be a dictionary key, and the reason is a direct consequence of how the table works.

A key's bucket is computed from its hash. If the key changes after it has been filed, its hash changes, and it is now sitting in a bucket the table would never look in. The key becomes unreachable while still occupying space.

So the rule: a key must be immutable.

hashable.py

d = {}

d[(1, 2)] = "ok"      # tuple: immutable, hashable  ✓
d["hello"] = "ok"     # str:   immutable, hashable  ✓
d[42] = "ok"          # int:   immutable, hashable  ✓
d[frozenset([1,2])] = "ok"                        # ✓

d[[1, 2]] = "boom"    # TypeError: unhashable type: G
d[{1: 2}] = "boom"    # TypeError: unhashable type: I

# Why lists are refused — a demonstration of what would go wrong:
key = [1, 2]
# imagine this were allowed:
#   d[key] = J          filed under hash([1,2])
#   key.append(3)         the SAME object now hashes differently
#   d[key]                looks in a different bucket → KeyError
#   d[[1,2]]              also fails — the stored key mutated too
# The entry would be permanently lost. Python refuses up front.

The contract between `hash` and `eq`

If you write your own class and want to use it as a dictionary key, you must honour one rule:

Equal objects must have equal hashes

If a == b, then hash(a) == hash(b) must hold. Otherwise two equal keys land in different buckets and the dictionary will happily store both, which is precisely the bug a dictionary exists to prevent.

The reverse is not required: unequal objects may share a hash. That is just a collision, and the table handles it by comparing keys within the bucket.

custom_key.py

class Point:
    def __init__(self, x, y):
        self.x = x
        self.y = y

    def __eq__(self, other):
        return isinstance(other, Point) and (self.x, self.y) == (other.x, other.y)

    def __hash__(self):
        return hash((self.x, self.y))     # delegate to the tuple. Always do this.

# Defining __eq__ without __hash__ makes the class UNHASHABLE — Python
# sets __hash__ to None, because it assumes you would otherwise break the
# contract by accident. That error message confuses everyone once.

5Python dicts and sets

You have used these since your first week. Here is what they are, and the two behaviours that surprise people.

A Python dict is an open-addressed hash table with a twist: since 3.6 it keeps a compact array of entries in insertion order, and the hash table stores indices into that array. That is why iteration order is insertion order — guaranteed since Python 3.7 — without giving up O(1) lookup.

A set is the same machinery with the values thrown away. That is the whole difference.

in_costs.py

# The three lookups people confuse, and their real costs:

d = {"a": 1, "b": 2}
"a" in d              # O(1)  — hashes the key
1 in d.values()       # O(n)  — no index on values; this SCANS

s = {1, 2, 3}
2 in s                # O(1)

xs = [1, 2, 3]
2 in xs               # O(n)  — the classic mistake

# The syntax is nearly identical. The costs are not.

Two behaviours worth knowing

two_surprises.py

# 1. Deleting does not shrink the table.
d = {i: i for i in range(1_000_000)}
d.clear()
# The bucket array stays large. Hash tables grow eagerly and shrink
# reluctantly, because shrinking risks thrashing. If you need the memory
# back, build a new dict.

# 2. A dict of 1M ints uses far more memory than a list of 1M ints,
#    because it stores keys, values, hashes and empty slots.
#    Reach for a dict when you need lookup BY KEY — not as a default
#    container.

You want	Use	Why
Lookup by key	`dict`	That is the job
Membership only	`set`	Same speed, no space for values
Counting occurrences	`collections.Counter`	A dict with counting built in
A default for missing keys	`collections.defaultdict`	No `if k not in d` dance
Keys in sorted order	not a hash table	Hashing destroys order — use a balanced tree, Ch. 16
Range queries (“all keys 10–20”)	not a hash table	Same reason

The honest limitation

A hash table's O(1) is bought by scattering keys deliberately. That means there is no order to exploit, ever. “The smallest key,” “the next key after x,” “every key between 10 and 20” — all O(n), all requiring a full scan.

When you need those, you need a tree. That is Chapter 15, and it is the direct counterpart to this chapter.

What to carry forward

A hash table turns a key into an array index in three steps: hash, modulo, index. None of them depend on how many keys are stored.
Collisions are guaranteed by the pigeonhole principle. Chaining puts a list in each bucket; open addressing probes for a free slot.
Load factor = keys / buckets. Past about 0.7 the table doubles and rehashes — every key gets a new index because the modulus changed.
Keys must be immutable, and equal objects must have equal hashes. Defining __eq__ without __hash__ makes a class unhashable.
Python's dict preserves insertion order via a compact entries array; a set is the same thing without values.
The price of O(1) is that order is destroyed. Sorted iteration, ranges and 'next key after x' all need a tree instead.

>_Playground

A working hash table with chaining and automatic rehashing. Watch the chain lengths, then force a collision on purpose.

scratch.pypython not loaded

class HashMap:
    def __init__(self, buckets=8):
        self._buckets = [[] for _ in range(buckets)]
        self._count = 0

def _index(self, key):
        return hash(key) % len(self._buckets)

def put(self, key, value):
        b = self._buckets[self._index(key)]
        for i, (k, _) in enumerate(b):
            if k == key:
                b[i] = (key, value)      # replace, do not duplicate
                return
        b.append((key, value))
        self._count += 1
        if self._count / len(self._buckets) > 0.75:
            self._grow()

def get(self, key, default=None):
        for k, v in self._buckets[self._index(key)]:
            if k == key:
                return v
        return default

def _grow(self):
        old = self._buckets
        self._buckets = [[] for _ in range(len(old) * 2)]
        self._count = 0
        for bucket in old:
            for k, v in bucket:
                self.put(k, v)

def stats(self):
        lens = [len(b) for b in self._buckets]
        return (f"{self._count} keys in {len(self._buckets)} buckets  "
                f"load={self._count/len(self._buckets):.2f}  "
                f"longest chain={max(lens)}  empty={lens.count(0)}")

m = HashMap()
for w in "apple banana cherry date elderberry fig grape honeydew kiwi lemon".split():
    m.put(w, len(w))
    print(f"put {w:12} -> {m.stats()}")

print()
print("get('fig')     =", m.get("fig"))
print("get('missing') =", m.get("missing"))
print()

# --- force collisions: a deliberately terrible hash function ---
class Terrible:
    def __init__(self, n): self.n = n
    def __hash__(self):    return 0        # EVERY key collides
    def __eq__(self, o):   return isinstance(o, Terrible) and self.n == o.n

bad = HashMap(8)
for i in range(20):
    bad.put(Terrible(i), i)
print("with a constant hash:", bad.stats())
print("^ one chain holds everything, so lookup is O(n). The table is fine;")
print("  the hash function was the problem.")

Real Python, running in your browser. Nothing is installed or uploaded.

Output appears here. The first run takes a few seconds while Python loads.

✓Exercises

Checked automatically the moment you submit. Work top to bottom — each one assumes the last. Your answers are saved in this browser.

All Warm-up Core Challenge Reset chapter

Chapter 9 — Sets, Maps and Choosing the Right Container

Half of practical algorithm work is picking a container and letting it do the work. A decision procedure you can actually follow.

Continue →

Hash Tables

By the end of this chapter you can

1Computing the address instead of searching for it

2Collisions are guaranteed

Strategy 1 — chaining

Strategy 2 — open addressing

3Load factor and rehashing

4What makes a key hashable

The contract between __hash__ and __eq__

5Python dicts and sets

Two behaviours worth knowing

What to carry forward

>_Playground

✓Exercises

Chapter 9 — Sets, Maps and Choosing the Right Container

The contract between `hash` and `eq`