How does a hash table work?
A hash function converts a key into an integer, which is used as an index into an array. That is why lookups are O(1) — no searching is involved.
#The mechanism
- Hash the key:
hash("python") → 8472619 - Reduce it to a slot:
8472619 % 16 → 11 - Store the key and value in bucket 11.
Lookup repeats the same steps and goes straight to bucket 11. No scanning, regardless of how many entries exist.
#Collisions
Two keys can land in the same bucket. Two standard fixes:
Chaining — each bucket holds a small list. On collision, append; on lookup, scan that short list.
Open addressing — on collision, probe the next free slot. Python uses a variant of this.
Either way, a good hash function spreads keys evenly, so chains stay short and lookups stay effectively constant.
#Resizing
When the table gets around 2/3 full, collisions become frequent. The table allocates a larger array and rehashes every key into it — an O(n) operation, but rare enough that the amortised cost per insert stays O(1).
#Why worst case is O(n)
If every key hashes to the same bucket, every lookup scans the whole chain. Adversarial input can trigger this deliberately, which is why languages randomise their hash seed per process.
#What this means for your code
Keys must be immutable. Mutating a key after insertion changes its hash, and the entry becomes unreachable — this is why Python allows tuples as dict keys but not lists.
Order is not guaranteed by the structure. Python dicts preserve insertion order as an implementation guarantee since 3.7, but that is a separate feature layered on top.
Use sets for membership. x in some_set is a hash lookup; x in some_list is a linear scan. On a large collection the difference is the difference between instant and unusable.