Hash Tables

Turn a key into an array index with a hash function. Average constant-time lookup, insert, and delete.

Level: intermediate

What is it?

A hash table stores key-value pairs in an array of buckets. A hash function converts the key into an integer, and the index is that integer modulo the array size. Different keys can land in the same bucket (a collision), handled by chaining (each bucket holds a list) or open addressing (probe for another free slot). When the load factor grows too high the table resizes and rehashes.

Why does it matter?

It is the most useful data structure in practice: dictionaries, sets, caches, symbol tables, deduplication, and counting all rely on average O(1) lookups. It also turns many O(n²) solutions into O(n).

Mental model

A coat check. You hand over a coat and get a numbered ticket; the number tells the attendant exactly which hook to check, so retrieval does not depend on how many coats there are. Two coats on the same hook is a collision.

How it works

index = hash(key) mod capacity. A good hash function spreads keys evenly and is deterministic.
Keys must be hashable: equal keys must give equal hashes, and the key must not change while stored (use immutable keys).
Chaining stores colliding entries in a list per bucket; open addressing probes for the next free slot.
Load factor = entries / buckets. Keep it below about 0.7 by doubling and rehashing, which is O(n) but amortized away.
No ordering: iteration order is arbitrary in principle (Python dicts preserve insertion order, but the structure is still a hash table).
Worst case is O(n) if many keys collide, which is why hash functions are randomized in security-sensitive code.

Steps

Hash the key to an integer
Take it modulo the bucket count
Look in that bucket
Compare keys to resolve collisions
Resize when the load factor is high

Code example: A tiny hash map with chaining

class ChainedMap:
    def __init__(self, buckets=8):
        self.buckets = [[] for _ in range(buckets)]

    def _bucket(self, key):
        return self.buckets[hash(key) % len(self.buckets)]

    def put(self, key, value):
        b = self._bucket(key)
        for i, (k, _) in enumerate(b):
            if k == key:
                b[i] = (key, value)       # update existing key
                return
        b.append((key, value))

    def get(self, key):
        for k, v in self._bucket(key):
            if k == key:
                return v
        raise KeyError(key)

m = ChainedMap()
m.put("cat", 1)
m.put("dog", 2)
print(m.get("dog"))   # 2

Complexity and trade-offs

Time: Average O(1) for get/put/delete; worst case O(n)

Space: O(n) plus spare capacity

Trade-offs

Fastest exact-match lookup available
No ordering and no range queries — use a tree or sorted array for those
Resizing causes occasional O(n) pauses; poor hashes cause collisions

Real-world usage

Dictionaries, sets, and caches in every language
Counting, grouping, and deduplicating records
Database hash indexes and hash joins

Common mistakes

Using a mutable object as a key and then mutating it.
Assuming iteration order carries meaning.
Writing a hash function that sends most keys to few buckets.

Interview questions

How does a hash table handle collisions?

Chaining keeps a list per bucket; open addressing probes other slots (linear probing, quadratic probing, double hashing). Both keep lookups near O(1) while the load factor stays low.

Why is the average lookup O(1) but the worst case O(n)?

With a good hash and a low load factor each bucket holds a few entries, so lookups take constant time. If many keys land in one bucket, lookup degrades to scanning that bucket, which can be all n entries.

Hash table or balanced tree?

A hash table gives O(1) average exact lookups and no order. A balanced tree gives O(log n) lookups but keeps keys sorted, supporting range queries and ordered iteration.