PYTHON / DATA STRUCTURES AND ALGORITHMS
Hash tables and how dict works internally
Explain how CPython turns a key into a table slot, why lookups still compare keys, and write classes whose __hash__ and __eq__ agree.
What you will learn
- Map a key to a slot with hash(key) % capacity and resolve collisions by probing
- Explain why a hash match is only a hint and equality must still be checked
- Write __hash__ from the same immutable fields your __eq__ uses
- Predict dict iteration order from insertion history, not from hash values
Understanding Hash tables and how dict works internally
A dict lookup is arithmetic, not searching. CPython calls hash(key), which returns an integer, and uses the low bits of that integer to pick a slot in a table whose capacity is a power of two, so hash(key) & (capacity - 1) is the same as hash(key) % capacity. Because a huge space of possible hashes is folded into a handful of slots, two unrelated keys regularly land on the same slot, and the table has to have a rule for what happens next. CPython uses open addressing: it keeps probing other slots in a deterministic sequence derived from the full hash until it finds the key or an empty slot, rather than hanging a linked list off each slot.
This is why hashing alone is never enough to answer 'is this key present'. When a probe lands on an occupied slot, CPython first compares identity (a fast pointer check, which is why looking up the exact same object is cheapest) and then compares the stored full hash; only if the hashes match does it call __eq__. Two keys are treated as the same key exactly when their hashes match and they compare equal, which is why 1, 1.0 and True all address one entry, and why a class that defines __eq__ without __hash__ is made unhashable — Python refuses to let you build a table it cannot search correctly.
Since 3.6 a dict is stored as two arrays: a dense entries array holding (hash, key, value) in insertion order, and a sparse array of small integer indices into it. The hash selects a position in the index array; the index array points into the entries array. That layout is why iteration follows insertion order (you are walking the entries array front to back), why dicts got noticeably smaller, and why a deleted-then-reinserted key moves to the end. When the table becomes about two thirds full, CPython allocates a larger index array and rebuilds it, so slot positions and probe lengths change over the life of a dict while insertion order does not; that occasional rebuild is what makes insertion O(1) amortised rather than strictly O(1).
class MiniDict:
def __init__(self, capacity=8):
self.capacity = capacity
self.slots = [None] * capacity
def _find(self, key):
i = hash(key) % self.capacity
probes = 0
while self.slots[i] is not None and self.slots[i][0] != key:
i = (i + 1) % self.capacity
probes += 1
return i, probes
def put(self, key, value):
i, probes = self._find(key)
self.slots[i] = (key, value)
print('put key=%2d -> slot %d (extra probes: %d)' % (key, i, probes))
def get(self, key):
i, _ = self._find(key)
if self.slots[i] is None:
raise KeyError(key)
return self.slots[i][1]
d = MiniDict()
for k in (1, 9, 17, 4):
d.put(k, k * 10)
print('get(17) ->', d.get(17))
print(d.slots)A hash turns a key into a slot number, but only an equality comparison can confirm that the key in that slot is the one you asked for.
Worked examples
__eq__ without __hash__
Shows that a custom class needs both methods to work as a dict key, and that Python blocks the half-done case.
class Point:
def __init__(self, x, y):
self.x = x
self.y = y
def __eq__(self, other):
return isinstance(other, Point) and (self.x, self.y) == (other.x, other.y)
def __hash__(self):
return hash((self.x, self.y))
seen = {Point(1, 2): 'first'}
print(Point(1, 2) in seen)
print(len({Point(0, 0), Point(0, 0)}))
class Loose:
def __eq__(self, other):
return True
try:
{Loose(): 1}
except TypeError as exc:
print(type(exc).__name__, exc)Example explained
Line 1hash((self.x, self.y)) reuses the tuple hash, so two Points built from the same numbers get the same slot.
Line 2Point(1, 2) in seen is True even though it is a different object, because the hash matches and __eq__ says equal.
Line 3The set keeps one element: equal hash plus equal comparison means the second insert overwrites the first.
Line 4Defining __eq__ sets __hash__ to None, so Loose cannot be a key at all — that is a deliberate guard, not a bug.
A key that mutates out of reach
Demonstrates that changing a field your __hash__ depends on strands the entry inside the table.
class Row:
def __init__(self, rid):
self.rid = rid
def __hash__(self):
return self.rid
def __eq__(self, other):
return isinstance(other, Row) and self.rid == other.rid
def __repr__(self):
return 'Row(%d)' % self.rid
r = Row(1)
d = {r: 'cached'}
print(d[Row(1)])
r.rid = 2
print(r in d, Row(2) in d, Row(1) in d)
print(list(d.items()), len(d))Example explained
Line 1hash(Row(1)) is 1, so the entry is filed under slot 1 of an 8-slot table.
Line 2After r.rid = 2 the object hashes to slot 2, which is empty, so r in d is False.
Line 3Row(1) in d fails too: it probes slot 1, finds r, and the equality check 1 == 2 rejects it.
Line 4The pair is still in the entries array, so len(d) is 1 and iteration shows it — reachable only by walking, never by lookup.
Insertion order and the entries array
Shows that updating a key keeps its position while delete-then-insert appends it at the end.
d = {'a': 1, 'b': 2, 'c': 3}
d['a'] = 99
print(list(d))
del d['b']
d['b'] = 5
print(list(d))
print(list(d.values()))Example explained
Line 1d['a'] = 99 finds the existing entry and overwrites its value slot, so position 0 is unchanged.
Line 2del d['b'] marks that entry dead; the later d['b'] = 5 appends a fresh entry after 'c'.
Line 3Iteration order tracks the entries array, so it reflects insertion history and never hash values.
Important notes
Equal-and-same-hash means one entry, so {1: 'a', 1.0: 'b', True: 'c'} has length 1: the first key object is kept and the last value wins.
MiniDict above uses linear probing to keep the code readable; real CPython perturbs the probe sequence with the higher bits of the hash to avoid clustering, but the hash-then-compare logic is identical.
Common mistakes
Using a list, dict or set as a key: hash() raises TypeError immediately, and wrapping in tuple(...) only helps because the tuple is a frozen snapshot, not a live view.
Defining __hash__ over a field that later changes; the entry stays in the dict and counts toward len but no lookup can ever find it again.
Storing hash('some string') in a file or database as a stable id; str and bytes hashing is salted per process, so the value differs on the next run and every lookup misses.
Try it yourself
Change, predict, then run
Write a class Bad whose __hash__ always returns 0, insert 2000 Bad instances and 2000 integers into two dicts, and use time.perf_counter to compare how long 2000 lookups take in each.
Open the Python workspaceCheck your understanding
After the probe finds a slot whose stored hash matches the hash of the key you are looking up, why does CPython still call __eq__?
- Because hash values are salted per process and cannot be trusted within one run
- Because the dict stores keys sorted by hash and needs equality to finish the binary search
- Because different objects can share a hash value, so only equality proves it is the same key
- Because __hash__ may return a float that must be normalised before comparison
Show answer
Hashes are fixed-width integers, so distinct keys can collide on the full hash as well as on the slot index; equality is the only test that distinguishes them. The salting option is tempting because str hashing really is randomised, but that randomisation is fixed for the life of a process and never changes a hash mid-run, so it plays no part in a single lookup.