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.
A Hash Map transforms a key into an integer array index using a mathematical Hash Function, enabling average O(1) insertions, lookups, and deletions.
Key: "user:101" ──► Hash Function ──► Hash Code: 893412 ──► Index: 893412 % 8 = 4
│
Bucket Array: [ 0 | 1 | 2 | 3 | [ "user:101", Data ] | 5 | 6 | 7 ] ◄─┘
When two distinct keys hash to the same bucket index, a collision occurs. Two standard resolution strategies exist:
i is occupied, probe consecutive indices i+1, i+2, ... until an empty bucket is found.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.
Map preserves insertion order, supports any key data type (objects, functions, numbers), and optimizes frequent additions/removals.Object only allows strings and symbols as keys and has prototype inheritance overhead.O(1) down to O(N) linear time!Use hash maps for frequency counting and two-sum lookups. Next, let's explore Prefix Sums and Range Queries!
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.
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.
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.