Data structures · intermediate
Hash table
A hash table uses a hash of each key to select a bucket or probe sequence, providing expected constant-time lookup, insertion, and deletion when keys are well distributed and load is controlled.
Why it matters
Hash tables make fast key-based indexing practical, but correctness depends on stable equality and hash behavior while performance depends on collisions and resizing.
Mental model
How to reason about hash table
The hash narrows a large key space to a table position. Collisions are resolved by chaining or probing, and resizing restores short searches as occupancy rises.
Analogy
A coat-check number sends an attendant to a small section of racks. If several coats share a section, their labels still need comparison before the correct one is returned.
Examples
See the boundary, not just the happy path
Worked example · Count occurrences
counts[word] = counts.get(word, 0) + 1Each word is located by key rather than by scanning all previously seen words, giving expected Theta(n) total time.
Worked example · Resolve a collision
bucket 3: [('cat', 4), ('act', 7)]Sharing a bucket does not make keys equal; the table compares keys within the collision structure.
Useful contrast · Worst-case behavior
every key maps to one bucketA pathological distribution can make lookup linear. Expected O(1) is not an unconditional worst-case guarantee.
Common mistakes
Misconceptions to remove early
Mutating a key after insertion
If mutation changes equality or the hash, lookup searches a different location. Hash-table keys must remain stable while stored.
Using equality and hash inconsistently
Keys considered equal must produce the same hash. Violating that contract can create duplicate-looking entries or failed lookups.
Quick check
Can you predict the result?
1. What must be true when two keys compare equal?
- • They must have the same hash value
- • They must be the same object
- • They must occupy different buckets
2. Why do hash tables resize as load grows?
Keep building