Data Structures & Algorithms
Hashing and Hash Tables
A hash function takes a value and deterministically converts it into a number, called a hash code, which can be used to pick a slot in an underlying array. A hash table, what Python calls a dict, and uses internally for set as well, stores key-value pairs using this idea, so looking up a key does not require scanning the structure - it computes the key's hash, jumps close to the right slot, and checks from there. That mechanism is what gives average-case O(1) lookup, insertion, and deletion by key, instead of the O(n) a plain list requires to find something by value.
Why it matters
- It underlies dictionaries, maps, and sets in virtually every language
- This is not theoretical - every dict lookup in Python relies on exactly this mechanism running underneath the syntax.
- It explains an asymmetry that trips people up: lookup by key is fast, lookup by value is not
- Checking whether a key exists in a dict is close to O(1); checking whether some value exists among a dict's values still means scanning them one by one.
- Collisions and hash quality are a real, practical concern, not just theory
- Anyone implementing caching, deduplication, or an index needs to understand why a hash table's worst case is worse than its average case.
- It explains a real, specific Python error
- Trying to use a mutable object like a list as a dictionary key raises a TypeError, and that error only makes sense once you know why a mutable object cannot safely be hashed.
From key to slot: what a hash function actually does
A hash function is deterministic - the same key always produces the same hash code - and aims to spread different keys across the available slots roughly evenly. The hash code is reduced, commonly with a modulo operation against the table's current size, to pick an actual slot in the underlying array. Because reaching the right slot does not depend on how many keys are already stored, well-distributed lookups stay close to constant time as the table grows, unlike a list, where finding something by scanning gets slower in direct proportion to size.
print(hash('apple')) # some large integer, consistent within one run
print(hash(42)) # 42 - small integers hash to themselves
prices = {'apple': 1.50, 'banana': 0.75}
print(prices['apple']) # near-O(1): computed from hash('apple'), not a scanCollisions, and why average-case O(1) is not worst-case O(1)
Two different keys can hash to the same slot, called a collision, since there are far more possible keys than slots. Hash tables handle this either by chaining, keeping a small list of entries at each slot, or by open addressing, which probes for another free slot nearby. If collisions stay rare, lookup stays close to O(1); if many keys collide, because the hash function distributes poorly or the table is deliberately targeted with adversarial input, lookup degrades toward O(n) in the worst case, since every colliding entry has to be checked. Python's dict manages its own resizing to keep collisions rare under normal use, which is why this rarely needs to be thought about directly, but the worst case genuinely exists underneath that convenience.
Mistakes people make here
- Using a mutable object, like a list, as a dictionary key
- Python raises a TypeError for this, because a key's hash has to stay stable for the lookup to keep working - if the list's contents changed after it was used as a key, its hash would change too, and the entry would become unreachable at its original slot. Tuples, which are immutable, work fine in the same role.
- Assuming dictionary lookup is unconditionally O(1)
- It is average-case O(1) under normal conditions with a reasonably distributed hash function. The worst case, with many collisions, degrades toward O(n) - rare in practice with Python's built-in types, but a real property of hashing as a concept, not just a footnote.
- Relying on a hash table's iteration order as if it were guaranteed by hashing itself
- Python dictionaries do preserve insertion order, but that is a specific language guarantee added in Python 3.7, not a property that follows from hashing as a general concept, and assuming the same about a hash-based structure in another language can be wrong.
- Writing a custom hash for an object without keeping it consistent with equality
- If two objects are considered equal but produce different hash codes, a hash table can fail to recognize that one is already stored under the same effective key - hash and equality have to agree for lookups to behave correctly.
Strengths and trade-offs
Where it is strong
- Average-case O(1) lookup, insertion, and deletion by key - dramatically faster than scanning a list once a collection is even moderately sized.
- Turns 'have I seen this before' and 'does this already exist' into simple, fast operations, powering deduplication, caching, and counting.
- The underlying idea, a deterministic function from key to location, stays simple to reason about even though real implementations add real engineering around resizing and collision handling.
The trade-offs
- Worst-case lookup is O(n) if many keys collide, whether from bad luck, a poorly distributed hash function, or deliberately crafted adversarial input.
- No ordering is inherent to hashing itself; any ordering you observe in a specific structure, like a Python dict's insertion order, is a property of that implementation, not a guarantee of hashing as a concept.
- Keys must be hashable and must keep hash and equality consistent, which rules out ordinary mutable objects as keys and requires care when defining custom ones.
Who needs this
Essentially everyone, since dictionaries, maps, and sets are used constantly in ordinary code. Understanding the actual mechanism matters most once performance or correctness at real scale is genuinely in question, rather than for using a dict day to day.
Questions about hashing and hash tables
- Why can't I use a list as a dictionary key in Python?
- Because a list is mutable, and a key's hash has to stay stable for as long as it is used as a key. If the list changed after being used as a key, its hash would change too, and the dict would no longer be able to find the entry at its original slot. Python refuses this upfront with a TypeError rather than allow a structure that could silently break.
- Is dictionary lookup really always O(1)?
- Average-case, under normal conditions, yes, close enough. Worst-case, if many keys collide, it degrades toward O(n). In everyday Python code this rarely matters, because the built-in hash functions and dict's resizing behavior are engineered to keep collisions rare, but the worst case is a real property, not a hypothetical one.
- What's a collision, and why doesn't it break the hash table?
- A collision is two different keys producing the same slot. It doesn't break anything because hash tables are built to handle it, either by keeping a small list of entries at that slot or by finding another nearby free slot, it just costs a little more work for the keys involved, rather than failing.
- Do Python dictionaries preserve insertion order?
- Yes, since Python 3.7, as an explicit language guarantee - iterating over a dict yields keys in the order they were first inserted. This is a Python-specific guarantee, though; it does not follow automatically from how hashing works in general, and should not be assumed of every hash-based structure in every language.