How does Python's dict work internally, and what makes a good hash key?

How to think about it

This one tests whether you grasp the two-step lookup that every hash-based structure in Python — dict, set — is built on. Get that model right and everything else falls out of it: what makes a valid key, why mutable objects can’t be keys, how collisions behave.

Every dict operation — d[key], key in d, d[key] = val — runs the same sequence:

1. slot = hash(key) % table_size — pick a starting slot from the key’s hash.
2. If that slot is empty → the key isn’t there.
3. If the stored key == key → found it.
4. Otherwise → probe on to the next candidate slot and repeat.

So it’s hash to find the slot, then == to confirm. CPython 3.6+ also keeps a separate compact array of entries in insertion order beside the table, which is why a dict preserves insertion order while still doing O(1) lookups.

key        hash(key) % 8   slot
---------  --------------  ----
"name"          3           3
"age"           1           1
"city"          5           5
"name2"         3   → collision → probe → slot 4

Collisions are resolved by jumping to another slot (open addressing), not by chaining a list off the bucket.

A worked example

A valid key has to implement __hash__ (a stable integer) and __eq__. Strings, ints, tuples of hashables, and frozensets qualify; lists and dicts don’t, because they’re mutable:

print("hash(42) =", hash(42))                 # ints hash to themselves
grid = {(0, 0): "origin", (1, 2): "point"}    # tuples are hashable -> valid keys
print("tuple key lookup:", grid[(1, 2)])

# Mutable containers are NOT hashable
for bad in ([1, 2], {"a": 1}):
    try:
        hash(bad)
    except TypeError as e:
        print(f"{type(bad).__name__}:", e)

# The golden rule: equal objects must share a hash
class GoodKey:
    def __init__(self, v): self.v = v
    def __eq__(self, other): return self.v == other.v
    def __hash__(self): return hash(self.v)    # delegate to the value
print("GoodKey lookup:", {GoodKey(1): "found it"}[GoodKey(1)])

# Define __eq__ without __hash__ and the class turns unhashable
class BadKey:
    def __init__(self, v): self.v = v
    def __eq__(self, other): return self.v == other.v
try:
    {BadKey(1): "x"}
except TypeError as e:
    print("BadKey:", e)

hash(42) = 42
tuple key lookup: point
list: unhashable type: 'list'
dict: unhashable type: 'dict'
GoodKey lookup: found it
BadKey: unhashable type: 'BadKey'

GoodKey works as a key because two equal keys hash the same — the dict hashes to the right slot, then __eq__ confirms the match. BadKey defined __eq__ but not __hash__, so Python nulled its hash and refused to let it be a key at all.

Why equal objects MUST share a hash

If a == b but hash(a) != hash(b), a lookup for b would probe a different slot from where a was stored — and the dict would report “not found” even though an equal key is sitting right there. Python can’t verify you’ve kept this promise; it trusts that your __hash__ is consistent with your __eq__.

Operation	Average	Worst case
lookup / insert / delete	O(1)	O(n) — every key collides

The worst case is pathological, and Python guards against it on purpose: it randomises the hash seed at startup (PYTHONHASHSEED) so an attacker can’t craft inputs that all land in one slot — a hash-flooding denial-of-service.