Hash Tables — Instant Lookup by Key

What is it? #

A hash table stores values under keys and finds them in roughly one step, no matter how many entries there are.

The trick is a hash function: it turns a key into a number, and that number decides which slot the value goes in. Looking up means running the same function and going straight to that slot.

Two different keys can produce the same slot. That is a collision, and every real implementation has a strategy for handling it, so it is a detail rather than a problem.

The cost is memory and order. A hash table uses more space than a plain array, and the slot order has nothing to do with sort order.

Think of it like this #

A cloakroom at a theatre. Instead of searching every hook for your coat, the attendant uses your ticket number to decide which hook it goes on. Returning it means reading the number and walking straight there.

Occasionally two tickets map to the same hook. The attendant hangs both and checks the names — slightly slower, but rare.

Simple example #

You have a million user records and need to check whether an email is already registered, thousands of times per minute. Scanning a list would be hopeless; a hash-based set answers instantly.

Code #

# Dictionaries and sets are hash tables
users = {"[email protected]": 1, "[email protected]": 2}

print(users["[email protected]"])        # O(1) average
print("[email protected]" in users)       # O(1) average
users["[email protected]"] = 3            # O(1) average

# Why keys must be hashable and stable
print(hash("abc") == hash("abc"))       # True — same value, same hash
# {"list": [1, 2]} as a key -> TypeError: unhashable type: 'list'

# A tiny hash table, to show the mechanics
class SimpleHashMap:
    def __init__(self, buckets=8):
        self._buckets = [[] for _ in range(buckets)]

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

    def put(self, key, value):
        bucket = self._buckets[self._slot(key)]
        for index, (existing_key, _) in enumerate(bucket):
            if existing_key == key:
                bucket[index] = (key, value)     # replace
                return
        bucket.append((key, value))              # collision: chain it

    def get(self, key, default=None):
        for existing_key, value in self._buckets[self._slot(key)]:
            if existing_key == key:
                return value
        return default


m = SimpleHashMap()
m.put("a", 1)
m.put("b", 2)
print(m.get("a"), m.get("zz", "missing"))     # 1 missing


# The pattern that fixes most slow loops
orders = [{"id": 1, "user_id": 7}, {"id": 2, "user_id": 9}]
users_list = [{"id": 7, "name": "Ravi"}, {"id": 9, "name": "Anita"}]

# Slow: O(n * m) — a scan inside a loop
for order in orders:
    user = next(u for u in users_list if u["id"] == order["user_id"])

# Fast: O(n + m) — index once, then look up
by_id = {u["id"]: u for u in users_list}
for order in orders:
    user = by_id[order["user_id"]]

How it works #

hash(key) produces an integer. % len(buckets) turns it into a valid slot number. Both steps are constant time, which is where the O(1) comes from.

put finds the bucket and either replaces a matching key or appends. Storing the key alongside the value is essential — without it you could not tell collided entries apart.

get recomputes the slot and checks only that bucket. With a good hash function the buckets stay short, so the scan is negligible.

Collisions are handled here by chaining — a list per slot. Real implementations, including Python's, use more sophisticated schemes and also resize when the table gets too full, keeping the average bucket small.

The worst case is O(n): if every key landed in one bucket, lookup degrades to a scan. Good hash functions and resizing make this vanishingly rare in practice.

Keys must be hashable and must not change while stored. A list can be modified, which would change its hash and lose the entry, so Python simply refuses to allow it.

The last block is the everyday application. Building an index once turns repeated searching into repeated lookup — the single most useful optimisation in ordinary code.

Real-world use #

Dictionaries, sets, caches, database indexes, deduplication, counting and grouping are all hash tables. Redis is essentially a very large one on a server. Session lookups, feature flags and permission checks all route through them.

Hashing also appears where speed is not the point: password storage uses deliberately slow cryptographic hashes, and content-addressed systems like git name objects by their hash. Different purposes, same basic idea of mapping data to a fixed-size value.

The security angle is worth knowing. If an attacker can predict your hash function, they can craft keys that all collide and turn your O(1) lookups into O(n) — a hash-flooding denial of service. Modern runtimes randomise hashing per process to prevent this.

The memory trade-off is real. A hash table holding a million integers uses considerably more memory than an array of a million integers. That is usually a price worth paying.

Common mistakes #

• Scanning a list inside a loop when a dictionary index would make it instant.
• Trying to use a list or dict as a key. Convert to a tuple, or use an immutable value.
• Relying on dictionary order as if it were sorted order. Insertion order is preserved, not sort order.
• Mutating an object used as a key, which loses the entry.
• Assuming O(1) is always true. With adversarial input or a poor hash it degrades to O(n).

Practice #

Given a list of 100,000 transactions, count how many occurred per user ID using a dictionary, then find the top five users. Then implement two_sum(nums, target), which returns the indexes of two numbers adding to the target, in one pass using a dictionary.