Hash Tables and Hashing

What is a Hash Table?

A hash table stores key-value pairs in an underlying array of buckets. To find where a key belongs, its hash is computed and reduced to a valid array index:

Because array indexing is O(1) (Lesson 2), and computing a hash is O(1) for typical keys, a hash table lookup is O(1) on average, no matter how many entries it holds.

Hash Functions

A good hash function is deterministic (the same input always produces the same output within a single run), fast to compute, and spreads keys uniformly across buckets to minimize collisions. Python exposes this directly through the built-in hash() function:

print(hash(42))
print(hash(True), hash(1))     # bool is an int subclass, True hashes exactly like 1
print(hash(3.0), hash(3))      # equal values hash equally, even across numeric types

# Within a single run, the same string always hashes the same way...
print(hash("apple") == hash("apple"))

42
1 1
3 3
True

Turning a hash into a bucket index just needs the remainder after dividing by the number of buckets:

def bucket_index(key: str, capacity: int) -> int:
    return hash(key) % capacity

# hash(key) can be negative, but Python's % always follows the sign
# of the divisor, so the result is guaranteed to land in [0, capacity)
print(-17 % 8)

7

Unlike some other languages, Python's % always follows the sign of the divisor, so hash(key) % capacity never needs an extra abs() to stay within bounds.

Handling Collisions

With a fixed number of buckets and an unbounded number of possible keys, two different keys will eventually hash to the same bucket, a collision. It's not a bug, it's mathematically unavoidable (the pigeonhole principle), so every hash table needs a strategy to handle it.

We'll build a hash table using separate chaining, since it maps directly onto structures you already know: an array of buckets, each one a small list.

Building a Hash Table from Scratch

A minimal hash table needs put to insert or update a key, and get to retrieve one:

class HashMap:
    def __init__(self, capacity: int = 8) -> None:
        self._capacity = capacity
        self._size = 0
        self._buckets: list[list[tuple[str, int]]] = [[] for _ in range(capacity)]

    def _bucket_index(self, key: str) -> int:
        return hash(key) % self._capacity

    def put(self, key: str, value: int) -> None:
        index = self._bucket_index(key)
        bucket = self._buckets[index]
        for i, (existing_key, _) in enumerate(bucket):
            if existing_key == key:
                bucket[i] = (key, value)   # overwrite the existing entry
                return
        bucket.append((key, value))
        self._size += 1
        if self._size / self._capacity > 0.75:   # load factor exceeded
            self._resize()

    def get(self, key: str) -> int:
        index = self._bucket_index(key)
        for existing_key, value in self._buckets[index]:
            if existing_key == key:
                return value
        raise KeyError(key)

    def _resize(self) -> None:
        # Same idea as Lesson 2's dynamic array: double the capacity and
        # rehash every entry into its new bucket
        old_buckets = self._buckets
        self._capacity *= 2
        self._buckets = [[] for _ in range(self._capacity)]
        for bucket in old_buckets:
            for key, value in bucket:
                index = self._bucket_index(key)
                self._buckets[index].append((key, value))

m = HashMap(capacity=4)
m.put("apple", 1)
m.put("banana", 2)
m.put("apple", 10)     # overwrites the previous value

print(m.get("apple"))
print(m.get("banana"))

try:
    m.get("cherry")
except KeyError:
    print("KeyError: cherry not found")

10
2
KeyError: cherry not found

Load Factor and Resizing

The load factor is the ratio of stored entries to bucket count. As it climbs, buckets get longer, chains get longer, and average lookup time drifts away from O(1) toward O(n). The fix is the same amortized doubling strategy from Lesson 2's dynamic array: once the load factor crosses a threshold (0.75 in our implementation), allocate a larger bucket array and rehash every entry into it.

That rehashing is O(n), but it happens rarely enough, and gets rarer as the table grows, that the amortized cost of any single put stays O(1), the exact same argument used for list.append().

How Python's Real dict Differs

Our HashMap is a faithful teaching model, but CPython's actual dict is more sophisticated. Since Python 3.6, it combines a sparse index array (open addressing, not chaining) with a separate dense array holding the actual key-value pairs in insertion order, which is also how modern dict guarantees the insertion-order iteration you may already rely on.