The Project | About Us | Contribute | Donations | License

HOME

Module 4 ended on an awkward question: we have spent the whole course writing task["id"] and task["priority"] taking for granted that the lookup is instantaneous — but why does a dict find one key among thousands in constant time, when searching a list is O(n)? We had already measured it in the timeit experiment of lesson 01-02 — the dict curve stayed almost flat while the list curve shot upward — but measuring is not understanding. In this lesson we reveal the trick: the hash table, the structure that turns a key into the exact position to look at. It is one of the most influential ideas in computer science, and understanding it changes how you see almost every piece of software you use: caches, databases, indexes, the Python interpreter itself. We will build a minimal version with our own hands and discover, honestly, where it breaks: that breaking point is the syllabus of the next lesson.

The pending question and the clue we already had
The core idea: turning the key into an index
Two analogies: the lockers and the book index
The dictionary (or map) ADT
The hash function at a high level: hash() and the % operator
A minimal (and naive) hash table
The inevitable problem: two keys, one bucket
TaskFlow: the id→task index
The expected costs

The pending question and the clue we already had

Let's recap what we know about searching:

In a list or LinkedList: looking up by id is O(n). You have to check element by element, because the position of a task bears no relationship to its id. We suffered it in 01-02 and signed off on it again in the find of the LinkedList (02-02).
In an array, by index: accessing position i is O(1). Lesson 01-05 gave us the exact reason: contiguous memory and the formula base + i × size. The processor doesn't search for cell i; it computes its address and goes straight there.
In 02-03 we dropped a hint: "some day we'll have an id→node index that avoids walking the list". That day is today.

Put the first two pieces together and the question sharpens: the array is blazingly fast, but only if you speak its language, which is integer indexes (0, 1, 2...). We want to speak the language of the problem: ids, titles, usernames. The hash table is, quite simply, a translator between the two languages.

The core idea: turning the key into an index

The idea fits in one sentence: if we had a function that turns any key into an array index, looking up by key would cost the same as accessing by index: O(1).

The full plan has three steps:

We reserve an array of capacity buckets (say, 8).
To store the pair (key, value), we compute index = hash_function(key) % capacity and place the pair in array[index].
To retrieve the value for a key, we repeat exactly the same computation and look in that bucket.

graph LR
    K["key<br/>(e.g. id 42)"] --> H["hash_function(key)"]
    H --> M["% capacity"]
    M --> I["index<br/>(e.g. 2)"]
    I --> A["array[2]<br/>base + 2 × size → O(1)"]

Note the detail that holds it all up: storing and looking up use the same computation. There is no need to remember where we left each thing, because the key itself is the address (once translated). That is why hash tables are also called computed addressing structures: they don't search, they compute.

Compare it with what the list did: there, a task's position depended on its arrival order, an arbitrary piece of information we cannot reconstruct from the id; hence the O(n). Here the position depends only on the key, and the key is always in our hand.

Two analogies: the lockers and the book index

The gym lockers. Imagine 100 lockers numbered 0 to 99 and this rule: "each member uses the locker matching the last two digits of their membership number". The member whose number ends in 42 leaves their bag in locker 42 and, when they come back, goes straight to 42: they don't open all 100 one by one. The rule is the hash function; the locker number, the index; and the last two digits are, literally, a % 100. Notice the shadow of the analogy too: if two members have numbers ending in 42, there is a locker conflict. Hold on to that shadow — we'll come back to it.

The alphabetical index of a book. To find "recursion" in an 800-page manual you don't read all 800 pages (linear search): you go to the index at the back, look under the letter R and jump to the exact page. The index is an auxiliary structure, maintained separately, whose sole purpose is to translate "term" → "position". A hash table is exactly that, except the translation isn't written down anywhere: it is computed on the fly.

The dictionary (or map) ADT

As we did with stacks and queues, let's separate the what from the how (the ADT vs. implementation distinction from module 1). The ADT we want is called a dictionary (also map or associative array): a collection of key → value pairs with unique keys. Its contract:

Operation	What it does	In Python (`dict`)
`put(key, value)`	Associates the value with the key; if the key existed, replaces its value	`d[key] = value`
`get(key)`	Returns the value associated with the key	`d[key]` / `d.get(key)`
`delete(key)`	Removes the pair	`del d[key]`
`contains(key)`	Does the key exist?	`key in d`

Two important observations:

The contract says nothing about order. A dictionary doesn't promise "the first one", "the last one" or "the highest priority"; it promises access by key. It's a different contract from stack, queue or list — another tool, another problem.
Keys are unique: inserting the same key twice doesn't create two entries; it overwrites the value. Exactly what we want in a task index: one id, one task.

The hash table is the star implementation of this ADT (not the only one: in module 6 we'll see that binary search trees also implement it, with other virtues). Python's dict is a hash table; so is set, storing only keys without values. We'll use them "from the inside" in 05-03; first let's earn the right by building one.

The hash function at a high level: `hash()` and the `%` operator

A hash function takes a key of any type (integer, string, tuple...) and returns an integer, always the same one for the same key. Python ships with one built in:

print(hash(42))          # 42  → for small integers, hash(n) == n
print(hash("revision"))  # e.g. -8103770210014465245 (a huge integer)
print(hash("revision"))  # the SAME integer, within the same run
print(hash((1, "a")))    # tuples have hashes too

For small integers, hash(n) is n itself: the translation is trivial.
For strings and other objects, Python mixes their bytes until it produces an integer that looks random but is deterministic. How that mixing is cooked — and what makes it good or bad — is the heart of lesson 05-02; for today it's enough to use it as a black box, just as we did with heapq in 04-04.
Practical note: the hash of strings changes between runs of the program (Python randomizes it for security). Within a single run it is stable, which is what the table needs; but don't print hash("hello") today and expect the same number tomorrow.

That huge (or negative) integer is useless as an index into an 8-bucket array. The final adjustment is done by the modulo operator, an old friend from the CircularQueue (04-03): % capacity folds any integer into the range 0..capacity-1, and in Python the result is never negative if capacity is positive.

capacity = 8
print(hash(42) % capacity)          # 2 → id 42 lives in bucket 2
print(hash("revision") % capacity)  # some value between 0 and 7

A minimal (and naive) hash table

With those two pieces we can already write a complete hash table... if we allow ourselves a naivety that will soon cost us dearly. Each bucket of the array will hold one (key, value) pair, or None if it's free:

class NaiveHashTable:
    """Key→value dictionary on top of an array. WARNING: naive on purpose."""

    def __init__(self, capacity=8):
        self.capacity = capacity
        self.buckets = [None] * capacity     # array of empty buckets

    def _index(self, key):
        """The translator: from key to array position."""
        return hash(key) % self.capacity

    def put(self, key, value):
        """Stores the pair wherever the hash says. Cost: O(1)."""
        self.buckets[self._index(key)] = (key, value)

    def get(self, key):
        """Repeats the same computation and checks that bucket. Cost: O(1)."""
        pair = self.buckets[self._index(key)]
        if pair is not None and pair[0] == key:
            return pair[1]
        return None                          # empty bucket, or another key's

    def contains(self, key):
        return self.get(key) is not None

Let's unpack the decisions:

_index concentrates the translation in one place: hash() mixes, % capacity folds. The underscore marks it as an internal method.
put walks over nothing: it computes and writes. get walks over nothing: it computes and reads. Not a single loop — that's where the O(1) lives.
In get we also store the key inside the pair and check it (pair[0] == key). Paranoia? No: it's the first crack of the naivety showing. If another key had landed in that bucket, without this check we would return someone else's value without warning.

Let's try it with TaskFlow tasks:

t1 = {"id": 1, "title": "Design logo", "priority": 2, "status": "pending"}
t5 = {"id": 5, "title": "Migrate server", "priority": 1, "status": "in_progress"}

table = NaiveHashTable(capacity=8)
table.put(1, t1)     # hash(1) % 8 = 1 → bucket 1
table.put(5, t5)     # hash(5) % 8 = 5 → bucket 5

print(table.get(5)["title"])   # Migrate server  (straight to bucket 5)
print(table.get(3))            # None            (bucket 3 empty: doesn't exist)

It works, and it works in O(1). Let's enjoy it for three seconds, because...

The inevitable problem: two keys, one bucket

...the capacity is 8 and the possible ids are infinite. Sooner or later, two different keys will produce the same index. With integers it's easy to provoke: 3 % 8 and 11 % 8 both give 3.

t3 = {"id": 3, "title": "Review budget", "priority": 3, "status": "pending"}
t11 = {"id": 11, "title": "Close sprint", "priority": 1, "status": "pending"}

table.put(3, t3)      # hash(3) % 8 = 3  → bucket 3
table.put(11, t11)    # hash(11) % 8 = 3 → the SAME bucket 3!

print(table.get(11)["title"])  # Close sprint   (fine...)
print(table.get(3))            # None           (task 3 has VANISHED!)

What just happened is called a collision: two different keys, one same index. Our naive version handles it in the worst possible way: the second tenant flattens the first. Task 3 isn't "hard to find"; it is lost. And thanks to the pair[0] == key check, at least get(3) returns None instead of lying to us by handing over task 11 as if it were task 3 — without it, the failure would be silent, the worst kind of failure.

Let it be clear from today: collisions are not a rare edge case you can ignore; they are mathematically inevitable (in 05-02 we'll prove it with the pigeonhole principle, and along the way you'll see they happen much sooner than intuition suggests). Every real hash table devotes half of its engineering to living with them. How it does so — chaining, open addressing, resizing — is exactly the syllabus of the next lesson.

TaskFlow: the id→task index

Let's place the piece in our application. Until today, TaskFlow keeps its tasks in structures that preserve an order (the LinkedList from module 2, the queues from module 4), and every time someone asks for a specific id we pay for a full walk:

def find_by_id_slow(tasks, target_id):
    """The version we have used (and suffered) since module 1. Cost: O(n)."""
    for task in tasks:
        if task["id"] == target_id:
            return task
    return None

The plan for module 5 is to maintain an index: an id→task hash table that lives alongside the main structure, just as a book's index lives alongside its pages:

class TaskIndex:
    """TaskFlow's id→task index. Version 0.1: on top of the naive table."""

    def __init__(self, capacity=8):
        self.table = NaiveHashTable(capacity)

    def register(self, task):
        self.table.put(task["id"], task)

    def find_by_id(self, task_id):
        return self.table.get(task_id)   # O(1): compute and look

The arithmetic is simple: with 10,000 tasks, find_by_id_slow examines 5,000 on average; the index examines one bucket. It is the explanation of the 01-02 experiment that we had owed for four modules. But version 0.1 inherits its table's disease: register tasks 3 and 11 and one of the two evaporates. A task manager that loses tasks is not a task manager; before wiring this index into the rest of TaskFlow we need the real table of 05-02.

The expected costs

Let's close with the cost table this module promises and 05-02 will justify:

Operation	Hash table (average)	Hash table (worst case)	`list` / `LinkedList`
`put(key, value)`	O(1)	O(n)	O(1) at the end
`get(key)`	O(1)	O(n)	O(n) search
`delete(key)`	O(1)	O(n)	O(n)
`contains(key)`	O(1)	O(n)	O(n)

Two honest readings:

The headline is the average column: access by key in O(1), the property no structure from modules 1–4 could offer.
The fine print is the worst case O(n): if fate (or a bad hash function) piles all the keys into the same bucket, the table degenerates into a linear search in disguise. Why the average is excellent despite this, and how the worst case is kept in check, is part of what 05-02 has to explain.

Common Mistakes and Tips

Confusing the hash with the index. They are two distinct steps: hash(key) produces an arbitrary integer (huge, maybe negative); % capacity folds it into the bucket range. Mixing them up leads to bugs like using hash(key) directly as an index (IndexError or, worse, negative indexes that in Python work by counting from the end... into the wrong bucket).
Forgetting to store the key next to the value. If the bucket stores only the value, there is no way to detect that the bucket is occupied by another key, and get returns someone else's data without an error. Storing the full pair turns a silent failure into a visible one.
Persisting string hashes. Since the hash of str changes between runs, saving hash("tag") to a file or database and reusing it the next day will break the program in baffling ways. The hash lives and dies with the run.
Assuming the dictionary provides order. Its contract is access by key; if your problem needs "the next in arrival order" or "the highest priority", the structures from modules 2–4 remain the right ones. Index and ordered structure usually coexist, not compete.
Tip: when you doubt why the hash table is O(1), mentally go back to 01-05. The whole building rests on base + i × size; the hash merely manufactures the i.

Exercises

By hand, no computer. With capacity = 10 and knowing that for integers hash(n) == n, compute the bucket for ids 7, 23, 40, 17 and 100. Which pairs of ids collide? Which ids would have collided with capacity = 8?
Complete the naive table. Add to NaiveHashTable the method delete(key), which empties the bucket and returns the deleted value (or None if the key wasn't there). Careful with a subtlety: what should happen if the bucket is occupied by another key that collided with the one you're looking for?
Hunt the collision. Write a function first_collision(keys, capacity) that takes a list of integer ids and returns the first pair (a, b) landing in the same bucket, or None if there is none. Try it with the ids [1, 9, 4, 12, 6] and capacity = 8.

Solutions

Exercise 1. With capacity = 10, the bucket is the last digit: 7→7, 23→3, 40→0, 17→7, 100→0. 7 and 17 collide (bucket 7) and so do 40 and 100 (bucket 0). With capacity = 8: 7→7, 23→7, 40→0, 17→1, 100→4 — 7 and 23 collide. A double moral: collisions depend on the keys as much as on the capacity, and changing the capacity relocates everything (an idea that will reappear in 05-02 under the name rehashing).

Exercise 2.

    def delete(self, key):
        """Empties the key's bucket and returns its value, or None."""
        i = self._index(key)
        pair = self.buckets[i]
        if pair is not None and pair[0] == key:   # occupied AND by this key
            self.buckets[i] = None
            return pair[1]
        return None                               # empty, or another key's

The subtlety lives in pair[0] == key: if the bucket is occupied by a different key (collision), deleting blindly would destroy someone else's data. With the check, delete(3) after the pile-up of section 7 returns None — consistent, because task 3 had already been flattened by task 11. The naive table cannot do better; the one in 05-02 can.

Exercise 3.

def first_collision(keys, capacity):
    occupied = {}                       # bucket → key that claimed it first
    for key in keys:
        bucket = hash(key) % capacity
        if bucket in occupied:
            return (occupied[bucket], key)
        occupied[bucket] = key
    return None

print(first_collision([1, 9, 4, 12, 6], 8))   # (1, 9): both → bucket 1

With [1, 9, 4, 12, 6] and capacity 8: 1→1, 9→1 → immediate collision (1, 9). A self-referential wink: we used a dict (a hash table) to study hash table collisions — with a list of occupied buckets, the function would be O(n²).

Conclusion

You now hold the idea that props up half of modern software: a hash function turns the key into an array index, and the positional access from 01-05 does the rest — searching stops being walking and becomes computing. We formalized the dictionary ADT (put, get, delete, contains), built a NaiveHashTable that genuinely answers in O(1), and mounted on top of it version 0.1 of TaskFlow's id→task index... which loses tasks as soon as two ids land in the same bucket. That is the exact frontier between the toy and the real structure: collisions. In the next lesson we'll see what makes a hash function good (and measure the difference between a good one and a bad one), prove that collisions are inevitable, and build the definitive HashTable that resolves them — reusing, by the way, an old friend from module 2: the LinkedList. See you in 05-02.

Introduction to Hash Tables

Contents

The pending question and the clue we already had

The core idea: turning the key into an index

Two analogies: the lockers and the book index

The dictionary (or map) ADT

The hash function at a high level: `hash()` and the `%` operator

A minimal (and naive) hash table

The inevitable problem: two keys, one bucket

TaskFlow: the id→task index

The expected costs

Common Mistakes and Tips

Exercises

Solutions

Conclusion

Data Structures Course

Module 1: Introduction to Data Structures

Module 2: Lists

Module 3: Stacks

Module 4: Queues

Module 5: Hash Tables and Dictionaries

Module 6: Trees

Module 7: Graphs

Module 8: Conclusions and Further Resources

Introduction to Hash Tables

Contents

The pending question and the clue we already had

The core idea: turning the key into an index

Two analogies: the lockers and the book index

The dictionary (or map) ADT

The hash function at a high level: hash() and the % operator

A minimal (and naive) hash table

The inevitable problem: two keys, one bucket

TaskFlow: the id→task index

The expected costs

Common Mistakes and Tips

Exercises

Solutions

Conclusion

Data Structures Course

Module 1: Introduction to Data Structures

Module 2: Lists

Module 3: Stacks

Module 4: Queues

Module 5: Hash Tables and Dictionaries

Module 6: Trees

Module 7: Graphs

Module 8: Conclusions and Further Resources

The hash function at a high level: `hash()` and the `%` operator