Hash Maps (How dict Works) — cheat sheet — Algorithms & Data Structures with Python

A hash map is the machinery under dict and set: it turns a key into a slot number so lookups avoid scanning the whole collection.

Core mechanism

Hash function: takes a key, returns a fixed-size number (the hash). Good ones are deterministic (same key, same number) and spread keys out.
Path from key to box: key -> hash() -> big number -> % num_slots -> slot index (always 0 to slots - 1).
Slot: a numbered box; each slot holds a bucket (a small list of pairs).
Python’s hash: hash(42) is 42; string hashes are randomized between separate runs, stable within one run.

"Alice" -> hash() -> 6182644... -> % 8 -> slot 4

Collision: two different keys map to the same slot. Guaranteed once keys outnumber slots; normal, not an error, and never affect correctness (only speed).
Separate chaining: each slot’s bucket holds all colliding pairs; lookup scans that short list.
Open addressing: no side-lists; probe for the next free slot by a fixed rule. Python’s real dict uses a form of this.

Load factor = entries / slots. Low = short buckets, wasted memory; high = long buckets, slower lookups.
Resize: when load factor crosses a threshold (Python’s dict ~ two-thirds full), allocate a bigger array (~double) and rehash every entry, because the slot came from hash(key) % num_slots and num_slots changed.
A single resize is O(n) but rare and doubles capacity, so insert stays amortized O(1).

Average O(1): hash, jump to slot, scan a near-constant bucket. Worst O(n): every key collides into one bucket.
Space is O(n).

A key must be hashable; in Python that means immutable. Numbers, strings, tuples of immutables work; lists, dicts, sets do not.
Reason: the slot comes from the hash. A mutable key’s hash could change, moving its correct slot while the pair stays in the old slot, so the value gets “lost.”
Values have no restriction; only the key feeds the hash.

Convert a mutable key first: d[tuple(my_list)] = v.
Don’t save a hash value or rely on hash-driven order across runs.
dict preserves insertion order (guaranteed since 3.7); set does not.
O(1) is an average, not “instant” or “always”; state it as “O(1) average, O(n) worst.”
set is a hash map with values removed: membership is O(1) average, elements must be hashable.