Hash Tables

After this lesson, you will be able to: Explain how hash functions work, how collisions are handled (chaining vs open addressing), what load factor and rehashing are, and why average operations are O(1).

Hash tables are the most useful data structure in everyday programming: dictionaries, maps, sets, and objects are all hash tables. Understanding how they achieve O(1) lookups, and when that breaks down, makes you dramatically better at writing fast code.

Prerequisites:Queues

The core idea: turn a key into an index

A hash table is an array plus a hash function. The hash function takes your key (a string, a number, anything) and turns it into an array index. To store key->value, you hash the key to get index i and put the value at array[i]. To look it up, you hash the key again and read array[i] directly. Because hashing and array access are both fast, lookup, insert, and delete are all O(1) on average. That is the magic.

A tiny hash table with chaining

Build it to see exactly how a Python dict or JS Map works inside.

python

class HashTable:
    def __init__(self, capacity=8):
        self.buckets = [[] for _ in range(capacity)]
        self.size = 0

    def _index(self, key):
        return hash(key) % len(self.buckets)

    def set(self, key, value):
        bucket = self.buckets[self._index(key)]
        for i, (k, v) in enumerate(bucket):
            if k == key:
                bucket[i] = (key, value)   # update existing
                return
        bucket.append((key, value))        # new key
        self.size += 1

    def get(self, key):
        bucket = self.buckets[self._index(key)]
        for k, v in bucket:
            if k == key:
                return v
        raise KeyError(key)

Collisions: when two keys hash to the same slot

Different keys can hash to the same index. That is a collision, and it is unavoidable. Two strategies handle it. Chaining stores a small list at each slot and appends colliding entries (the code above does this). Open addressing instead probes for the next empty slot (linear probing, quadratic probing, double hashing). Chaining is simpler and degrades gracefully; open addressing is more cache-friendly but trickier to delete from. Both keep operations O(1) as long as collisions stay rare.

Load factor and rehashing

Load factor is size divided by capacity: how full the table is. As it climbs, collisions multiply and operations slow toward O(n). So hash tables watch the load factor and, when it crosses a threshold (often around 0.7), they rehash: allocate a bigger array and reinsert everything. Rehashing is O(n), but like dynamic array resizing, it happens rarely, so the amortized cost stays O(1). This is why a dict can hold millions of entries and still answer instantly.

Common mistakes only experienced devs catch

Using a mutable object as a key, or an object whose hash changes after insertion (then you can never find it again; keys must be immutable and have stable hashes). Assuming iteration order (Python dicts preserve insertion order since 3.7, but do not rely on hash order in general). Forgetting that worst case is O(n). Doing membership checks against a list with 'in' when a set would be O(1). Implementing equality without also implementing a consistent hash, so equal objects land in different buckets.

←Queues

Back to Data Structures

Trees and Binary Search Trees→