How a hash map keeps lookups fast on average

A hash map turns a key into a number, maps it to a slot, and checks only the few keys that landed there. The table grows as it fills, so slots stay short and lookups are O(1) on average. Many keys colliding in one slot, from a poor hash or crafted input, degrades a lookup towards O(n).

Growth keeps the load (keys per slot) under a fixed limit; each growth rehashes every key, but it happens rarely enough that inserts stay O(1) amortized.

CPython's dict uses open addressing: a collision probes other slots in a fixed pseudo-random order instead of chaining a list.

String hashing is randomised per process (PYTHONHASHSEED), which blocks attackers from precomputing colliding keys.

class SameHash:
    def __init__(self, v: int) -> None:
        self.v = v

    def __hash__(self) -> int:
        return 7

    def __eq__(self, o: object) -> bool:
        return isinstance(o, SameHash) and o.v == self.v


d = {SameHash(i): i for i in range(1000)}
print(len(d), d[SameHash(999)])

Common mistakes

• Saying lookups are O(1) without 'on average'.
• Using mutable objects as keys and then changing them, which loses the entry.

The words that matter are 'average', 'amortized' and 'collisions'. Mention hash flooding and randomised hashing to show you know the worst case is real.

Follow-up questions

Think of your answer first, then open the hint.

1. Why must equal keys have equal hashes?

   Show hint

   The lookup only compares keys inside one slot; equal keys in different slots would never meet.

2. What does Java do when one bucket gets long?

   Show hint

   Since Java 8, a long bucket turns into a balanced tree, capping that bucket at O(log n).

Similar on Android: Data classes Kotlin data classes generate equals and hashCode from their properties; in Python you write __eq__ and __hash__ yourself or use a frozen dataclass.