Data Structures · Lesson 6 of 8

Hash Tables

Hash functions, collisions, and average O(1) lookup.

• Intermediate
• 14 min read
• 3 objectives

Before this lessonLesson 5: Trees

A hash table stores key-value pairs and finds a value from its key in about constant time, no matter how many items it holds. It is the structure behind Python's dict and set, Java's HashMap and JavaScript's Map and objects. If you learn one structure deeply, make it this one.

The trick behind instant lookup

Searching a list means checking items one by one. A hash table avoids searching by computing where an item lives. It runs the key through a hash function that turns it into a number, and uses that number as a position in an array. To find the key later, hash it again and go straight to the same spot. Python's dict and set are hash tables, which is why they are so fast.

How it works

The table is really an array of buckets. To store a key, a hash function turns it into a number, and that number modulo the array size picks the bucket. To look the key up later, you run the same hash and go straight to that bucket instead of searching.

def bucket_index(key, size):
    return hash(key) % size

print(bucket_index("user:42", 8))   # always the same for the same key

Collisions

Two different keys can land in the same bucket. That is called a collision, and every hash table needs a plan for it:

• Chaining: each bucket holds a small list of entries that share it.
• Open addressing: if a bucket is taken, probe the next free one.

When the table gets too full it resizes, allocating more buckets and re-hashing every key. This keeps chains short so lookups stay fast.

Complexity

• Insert, lookup and delete: O(1) average.
• Worst case O(n) if nearly every key collides, which good hash functions make very unlikely.
• Keys must be hashable, meaning immutable: strings, numbers and tuples work; lists do not.

Everyday uses

cache = {}
cache["user:42"] = {"name": "Amar"}
print(cache.get("user:42"))

# Membership testing: set is much faster than list for large data
seen = set()
for n in [3, 1, 3, 2]:
    if n in seen:
        print("duplicate:", n)
    seen.add(n)

{'name': 'Amar'}
duplicate: 3

Worked example: two-sum

Find two numbers in a list that add to a target. Checking every pair is O(n squared). With a hash table you remember what you have seen and check for the complement in O(1), giving O(n) overall.

def two_sum(nums, target):
    seen = {}
    for i, n in enumerate(nums):
        need = target - n
        if need in seen:
            return seen[need], i
        seen[n] = i

print(two_sum([2, 7, 11, 15], 9))

(0, 1)

Watching hashing happen

buckets = 8
for key in ["ada", "linus", "grace", "alan"]:
    slot = sum(ord(c) for c in key) % buckets   # a toy hash function
    print(f"{key:<6} -> slot {slot}")

ada    -> slot 6
linus  -> slot 3
grace  -> slot 2
alan   -> slot 4

Each key maps to a slot number. Two different keys can land on the same slot; that is called a collision, and real tables handle it by keeping a small list per slot or probing to the next free slot. With a good hash function and enough slots collisions are rare and lookups stay near O(1).

What can be a key?

Keys must be hashable, meaning immutable. Strings, numbers and tuples work. Lists and dicts do not, because their contents (and therefore their hash) could change.

locations = {(0, 0): "start", (2, 5): "shop"}
print(locations[(2, 5)])

try:
    bad = {[1, 2]: "nope"}
except TypeError as e:
    print("TypeError:", e)

shop
TypeError: cannot use 'list' as a dict key (unhashable type: 'list')

Worked example: find duplicates in one pass

def first_duplicate(items):
    seen = set()
    for x in items:
        if x in seen:
            return x
        seen.add(x)
    return None

print(first_duplicate([3, 1, 4, 1, 5, 9]))
print(first_duplicate([1, 2, 3]))

1
None

Without a set you would compare every pair of items, which is O(n^2). With one you touch each item once: O(n). Turning a nested loop into a set lookup is one of the most valuable optimisations you will ever learn.

Key takeaways

• A hash table computes a slot from the key, giving average O(1) lookup, insert and delete.
• Collisions are handled internally; you just use dict and set.
• Keys must be immutable (hashable): use tuples, not lists.
• A set or dict often replaces a slow nested loop.

# Write your solution here