Hash Tables — O(1) Average-Case Lookup

Build the mental model

Suppose you need to look up lesson content by slug — a naive approach linearly scans a list of (slug, content) tuples, which is O(n) since a match near the end costs as much as checking every entry before it. A hash table solves this differently: it runs the key (the slug) through a hash function that computes an integer index, and uses that index directly as a 'bucket' position in an underlying array, so a lookup computes the index in O(1) and jumps straight to the bucket. Two different keys can hash to the same index — a collision — and one simple resolution strategy is chaining: instead of storing a single value per bucket, each bucket holds a small list, and colliding keys just get appended to it. With few collisions, lookups stay O(1) on average, but a poor hash function (or adversarial input) can pile many keys into one bucket, degrading worst case to O(n). Python's dict and set are production-quality hash table implementations built on exactly this idea.

Connect it to a real scenario

The Tutorial Platform's slug-to-content lookup is the classic hash table use case — even with hundreds of lessons in a course, a dict lookup like lessons_by_slug[slug] stays O(1), which is exactly what lets the URL router resolve a slug to content instantly.

A hash function computes a bucket index from a key, giving O(1) average-case lookup
Two keys hashing to the same index is a collision; chaining is one resolution strategy
Python's dict/set are hash tables — average O(1), but worst case can degrade to O(n)

Try the working example

python

lessons = [
    ("linked-lists", "Linked Lists content..."),
    ("stacks", "Stacks content..."),
    ("queues", "Queues content..."),
    ("hash-tables", "Hash Tables content..."),
]

# Naive approach: linear scan through a list of tuples - O(n) worst case
def find_naive(slug):
    for s, content in lessons:
        if s == slug:
            return content
    return None

# Hash table approach: dict hashes the slug straight to a bucket - O(1) average
lesson_map = dict(lessons)

def find_hashed(slug):
    return lesson_map.get(slug)

print(find_naive("hash-tables"))
print(find_hashed("hash-tables"))

You should see

Both print the same string, "Hash Tables content...", but find_naive scans the list while find_hashed jumps straight to the hashed bucket.

5-minute try-it

Extend the lessons list to about 10,000 entries and use the time module to measure find_naive vs find_hashed — how big is the gap?

One important caution

Trying to use a mutable object like a list as a dict key raises a TypeError — dict keys must be hashable (immutable)

Assuming hash tables guarantee O(1) in the worst case — with a poor hash function or heavy collisions, a single lookup can degrade to O(n)

Wikipedia — Hash table — Data Structures & Algorithms