How Hash Maps Actually Work Under the Hood

Hash maps (dictionaries, objects, associative arrays — same concept, different names) deliver average O(1) lookup by trading memory for speed through a genuinely clever mechanism worth understanding.

# Conceptually, a hash map works roughly like this:
class SimpleHashMap:
    def __init__(self, size=16):
        self.buckets = [[] for _ in range(size)]

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

    def put(self, key, value):
        bucket = self.buckets[self._hash(key)]
        for i, (k, v) in enumerate(bucket):
            if k == key:
                bucket[i] = (key, value)  # update existing
                return
        bucket.append((key, value))

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

Why It’s O(1) on Average

A hash function converts a key into an array index, letting you jump directly to roughly the right location instead of searching — genuinely O(1) on average. The word “average” matters: if many keys hash to the same bucket (a “collision”), that bucket degrades toward O(n) for its own lookups, which is exactly why a good hash function distributing keys evenly is critical to a hash map actually performing well.