Collisions
Sometimes two different words land on the same page. You do not panic — you write both on that page and read the short list to see which one you wanted. Collisions are normal; you just need the lists to stay short.
Two words on one page
step 1 / 19Only 5 pages this time, to force the problem into the open.0 entries / 5 pages — load factor 0.00
The two collision strategies
| strategy | idea | delete | memory | used by |
|---|---|---|---|---|
| separate chaining | each bucket holds a little list; colliders line up in it | easy — unlink from the chain | pointers per entry | Java HashMap, C++ unordered_map |
| open addressing | bucket taken? probe another slot in a fixed pattern | tricky — needs tombstones | one flat array, cache-friendly | CPython dict, V8, Rust HashMap |
Load factor — the crowding dial
load factor = entries / buckets. Low: wasted space but rare collisions. High: compact but chains grow and O(1) rots toward O(n). Every real implementation picks a threshold and RESIZES past it, rehashing every key into a bigger table — an O(n) event amortized across the inserts that caused it. This is the dynamic-array growth story again, wearing a hash.
CPython dict internals
- Open addressing with a pseudo-random probe sequence (perturb): a collision does not check the NEXT slot — it jumps in a pattern derived from the full hash, dodging pile-ups.
- Resizes when 2/3 full — the table you pay for is always ≥1.5× your entries.
- Small ints hash to themselves: hash(42) == 42. Strings use SipHash, randomized per process.
- Two objects that compare equal MUST hash equal — that is why you always override __hash__ together with __eq__.
- A malicious set of all-colliding keys turns a dict into an O(n²) denial-of-service — the reason string hashing is randomized (a real 2011 attack on web frameworks).
buckets = [[] for _ in range(5)]
def put(k, v):
i = my_hash(k, len(buckets))
buckets[i].append((k, v)) # chain, do not overwrite
def get(k):
i = my_hash(k, len(buckets))
for key, val in buckets[i]: # scan the short chain
if key == k:
return valTwo keys hash to bucket 3. The map…
group_by_bucket(keys, n) hashes every key with the same ord-sum % n and returns a list of n buckets (lists) — collisions chain together.