Hash Maps & Collision Resolution Strategies
Quick Overview
A hash map is `O(1)` only while collisions stay rare. As the load factor climbs, buckets turn into lists and lookup degrades toward `O(N)`, which is why the table resizes before it fills.
Deep Dive
1. Key-Value Lookup in O(1) Time
A Hash Map transforms a key into an integer array index using a mathematical Hash Function, enabling average O(1) insertions, lookups, and deletions.
2. The Hash Function Pipeline
Key: "user:101" ──► Hash Function ──► Hash Code: 893412 ──► Index: 893412 % 8 = 4
│
Bucket Array: [ 0 | 1 | 2 | 3 | [ "user:101", Data ] | 5 | 6 | 7 ] ◄─┘
3. Handling Hash Collisions
When two distinct keys hash to the same bucket index, a collision occurs. Two standard resolution strategies exist:
- Separate Chaining (Linked List Buckets): Each bucket holds a linked list of key-value pairs. If keys collide, they are appended to the bucket's linked list.
- Open Addressing (Linear Probing): If bucket
iis occupied, probe consecutive indicesi+1, i+2, ...until an empty bucket is found.
4. Load Factor & Dynamic Resizing
load factor (α) = total stored items / bucket array capacity
When the load factor exceeds a threshold (typically 0.75), the hash map reallocates a larger bucket array (usually double capacity) and rehashes all keys to preserve O(1) performance.
5. JavaScript Map vs Object
Mappreserves insertion order, supports any key data type (objects, functions, numbers), and optimizes frequent additions/removals.Objectonly allows strings and symbols as keys and has prototype inheritance overhead.
6. Common Mistakes
- Poor Hash Function Distribution: A hash function that maps all keys to the same bucket degrades hash map performance from
O(1)down toO(N)linear time!
7. Next Steps
Use hash maps for frequency counting and two-sum lookups. Next, let's explore Prefix Sums and Range Queries!
Next Up in Data Structures & Algorithms Core Patterns
Big O Notation: Time & Space Complexity
Big O describes how work grows, not how long it takes. An `O(N^2)` algorithm on 1,000 items does a million steps; the same work at `O(N log N)` does about 10,000.
Dynamic Arrays & Amortized Resizing
A dynamic array doubles rather than growing by one, so the expensive copy lands on the 1st, 2nd, 4th and 8th push. Averaged across every push, that is `O(1)` amortised.
Two Pointers Pattern (Converging & Symmetrical)
A nested loop tests every pair in `O(N^2)`. On sorted data, moving two pointers inward from both ends rules out half the remaining candidates at each step and settles it in one `O(N)` pass.