Hash Tables
The problem
Looking up a value by key in an array means scanning every element — O(n) — which is too slow once a collection has more than a handful of items. Hash tables give near-constant-time lookup by turning a key directly into a storage location instead of searching for it.
Why now
Arrays give O(1) access only if you already know the numeric index; a hash table's whole purpose is turning an arbitrary key (a string, an object) into that index. Modular arithmetic already explained how to map an unbounded range of numbers into a fixed number of buckets — a hash table is exactly that idea, with a hash function providing the number to reduce.
Mental model
A hash function converts a key into a number; modular arithmetic reduces that number into one of N buckets; the value lives in that bucket. Lookup, insert, and delete are all 'compute the bucket, go there directly' — no searching, as long as collisions (two keys landing in the same bucket) stay rare, which is exactly the birthday-paradox question probability already answered.
Requires
- Modular ArithmeticMathematical Thinking
Reducing a hash's numeric output down to one of N buckets is a direct application of the mod operation and its wraparound guarantees.
- Arrays & ListsProgramming Fundamentals
A hash table's buckets are stored in an underlying array; the O(1) bucket access is exactly array indexing, applied after the hash-to-index step.
Helps
- Probability BasicsMathematical Thinking
Reasoning about how full a hash table can get before collisions become likely (the load factor) is a direct application of the birthday-paradox probability calculation.
Unlocks
Used in
- Objects/dictionaries/maps in every major programming language
- Database indexes (hash indexes for equality lookups)
- Caching layers (Redis, Memcached) — key-value stores are hash tables at scale
- Set membership testing and deduplication
Projects
- Implement a hash table from scratch with your own hash function and collision handling (chaining), then measure lookup time as load factor increases
- Use a hash set to solve a duplicate-detection problem in O(n) instead of the naive O(n²) nested-loop approach
Examples
- A JavaScript object obj[key] is, under the hood, a hash table mapping string keys to bucket locations
- Two different keys hashing to the same bucket (a collision) is resolved by chaining a small list at that bucket
Resources
Mastery checklist
- I can explain how a hash function and modular arithmetic combine to select a bucket
- I can explain at least one collision-resolution strategy (chaining or open addressing)
- I can explain why hash table lookup is O(1) average case but not guaranteed worst case
- I can choose a hash table over an array when a problem needs fast key-based lookup