Module F-4 — Hash Maps: Hashing, Collisions, and O(1) Lookups
What this module covers: Three modules in a row have hit the same wall — a loop inside a loop, checking every element against every other element, O(n²). This module is the general-purpose fix. Hash maps trade a bit of memory for the ability to ask "have I seen this before?" in O(1), and that single trick is behind more real-world performance fixes — and more of your production stack — than almost any other structure in this course.
The Problem: Checking Membership Shouldn't Cost O(n)
Every version of the O(n²) bug you've seen so far — .includes() inside a loop (Module F-1), the naive rotation check (Module F-3) — has the same shape: "is this value already somewhere in this collection?" On an array, answering that question means scanning, because arrays only know how to find things by position, not by value.
A hash map answers a different question: instead of "where in memory is this array?", it computes "which bucket should this specific key live in?" — directly, without looking at anything else first.
typescript
Whether seen holds 10 entries or 10 million, .has() costs roughly the same. That's the entire value proposition of a hash map, and it's why "swap the array for a Map/Set" is often the single change that turns a timing-out endpoint into an instant one.
How Hashing Actually Works
Underneath, a hash map is still just an array — the same contiguous, O(1)-indexed structure from Module F-2. The trick is a hash function, which takes a key of any type and any size and deterministically converts it into a number (a hash code), which is then reduced (typically with modulo) into a valid index into that backing array.
index = hash(key) % array.length
typescript
Given the same key, simpleHash always returns the same index — that determinism is what makes .get(key) work: compute the hash once, jump straight to that bucket, and the value is there (or it isn't). No scanning the whole structure — you go directly to where the answer has to be, if it exists at all.
Analogy: A hash map is a library that shelves books by the first letter of the author's last name, computed the instant the book arrives — not alphabetically re-sorted on every new arrival. Looking up "an author starting with M" means walking straight to the M shelf, not scanning every shelf in the building.
Collisions: When Two Keys Hash to the Same Bucket
Different keys can, and eventually will, hash to the same bucket index — this is called a collision, and it's unavoidable once you have more possible keys than buckets (the pigeonhole principle guarantees it eventually). How a hash map handles this determines whether it stays fast or quietly degrades.
Chaining (the more common approach): each bucket holds a small list of entries instead of a single one. A collision just means two entries share a bucket, checked with a short linear scan within that one bucket — not the whole table.
bucket[7] → [("user_42", {...}), ("user_58", {...})] // both hashed to index 7
Open addressing (the alternative): on a collision, the map probes forward to the next open slot according to some rule, rather than growing a list at the colliding bucket.
Both approaches degrade toward O(n) in the worst case — if every key happened to hash to the same bucket, you'd be scanning a list as long as the whole map, no better than an array. In practice, a well-designed hash function spreads keys evenly enough that this worst case is rare, which is why hash maps are described as O(1) average case, not O(1) worst case — a distinction Module F-1 covered directly, and one that matters here more than almost anywhere else in this course.
Load Factor and Resizing
Load factor is the ratio of stored entries to bucket count. As it climbs, collisions become more frequent and lookups slow down. Hash maps manage this the same way dynamic arrays manage running out of space (Module F-2): when the load factor crosses a threshold (commonly around 0.75), the map rehashes — allocates a larger backing array and re-inserts every existing entry, because the same key can land in a different bucket once the bucket count changes.
That rehash is O(n), same shape as the array resize from Module F-2, and it's why hash map operations are also described as O(1) amortized — occasional expensive rehashes, paid for by many cheap operations in between.
Map vs Plain Object
TypeScript/JavaScript gives you two hash-map-like structures, and the difference matters more than "just pick whichever":
typescript
Map preserves insertion order reliably across all key types; plain object key order has historical quirks (numeric-looking keys get reordered).
Map accepts any value as a key — objects, functions, even NaN — while plain objects coerce every key to a string (or Symbol), silently losing type information (obj[1] and obj['1'] are the same key).
Map has no prototype chain to worry about. A plain object inherits from Object.prototype, which means 'toString' in someObject can be true even though you never explicitly set it — a real source of bugs when using a plain object as a general-purpose key/value store built from untrusted input.
Map.size is O(1); getting the number of keys on a plain object requires Object.keys(obj).length, which is O(n).
Rule of thumb: reach for Map when the structure is genuinely a dynamic key-value store (arbitrary keys, added and removed over time). Plain objects are still the right choice for fixed-shape records — a User object with known fields isn't "a hash map," it's a record, even though it happens to use the same underlying mechanism.
The Pattern That Fixes Every O(n²) Problem So Far
Two Sum — given an array and a target, find two numbers that add up to it — is the canonical example, and the fix generalizes to every "check every pair" problem you'll meet:
typescript
twoSumSlow checks every pair explicitly — O(n²). twoSumFast never checks a "pair" at all: for each number, it asks the hash map "have I already seen the value that would complete this pair?" — an O(1) question — and only then remembers the current number for future iterations. One pass, O(n) overall, O(n) space for the map. This exact shape — "remember what you've seen, so the next check is O(1) instead of a fresh scan" — is the single most reusable pattern in this entire course.
The same idea builds a frequency map for grouping or counting:
typescript
Sorting each word's letters is O(k log k) for a word of length k, but it turns "is this an anagram of something I've already grouped?" from a comparison against every existing group into a single O(1) map lookup.
Where This Shows Up in Your Stack
Redis is, functionally, a hash map exposed over the network — every GET key / SET key value is exactly the O(1) hash-and-jump operation described above, which is the entire reason Redis is reached for as a caching layer: it's doing, at the process level, the same trick your in-memory Map does.
PostgreSQL hash indexes apply the same idea to disk-backed lookups — a hash index is built specifically for equality checks (WHERE id = $1), giving O(1)-ish lookups for exact matches, as opposed to a B-Tree index (Module F-11, Module A-13), which supports range queries at O(log n).
Memoization (previewed here, covered fully in Module P-11) is exactly the "remember what you've already computed" pattern from Two Sum, applied to function results instead of array values — a Map from input to already-computed output, turning repeated expensive calls into O(1) lookups on the second and subsequent calls.
Deduplication and idempotency checks — "have we already processed this webhook event ID?", "has this user already been added to the batch?" — are the has-I-seen-this-before question from Two Sum, applied directly. This is commonly backed by a Redis SET with a TTL in production specifically because the check needs to be O(1) even under high request volume.
Summary
Hash maps convert "have I seen this?" from an O(n) scan into an O(1) lookup, by computing a bucket index directly from the key instead of searching for it.
Hashing is deterministic: the same key always maps to the same bucket, which is what makes repeated lookups reliable.
Collisions are unavoidable and handled by chaining or open addressing — both degrade toward O(n) in the worst case, which is why hash maps are O(1) average case, not worst case.
Load factor drives rehashing, an O(n) operation amortized across many cheap operations — the same amortized-cost shape as dynamic array growth from Module F-2.
Map beats plain objects for genuine dynamic key-value stores: reliable ordering, any key type, no prototype-chain surprises, O(1) size.
The core pattern — remember what you've seen, check in O(1) — fixes every nested-loop problem seen so far in this course, and reappears as memoization in Module P-11.
The next module, Bit Manipulation: Flags, Permissions, and Fast Math, is a short, practical detour before Foundation moves into stacks and queues — a different way of packing and checking many boolean facts using a single integer instead of a map or object at all.
Knowledge Check
Why are hash map lookups typically described as O(1) average case rather than O(1) in every case?
In the twoSumFast function, why does checking seen.has(complement) before calling seen.set(nums[i], i) matter for correctness, beyond just performance?
According to the module, why is a plain JavaScript object considered riskier than a Map when used as a general-purpose key/value store built from untrusted or dynamic input (e.g., keys derived from user-supplied strings)?
Test your knowledge with more question sets
Sign in to access a wider variety of questions and get notified when new practice sets are added to this module.
const seen =newMap<string,boolean>();seen.set('user_42',true);seen.has('user_42');// true — O(1), no scanningseen.has('user_99');// false — O(1), no scanning
functionsimpleHash(key:string, bucketCount:number):number{let hash =0;for(let i =0; i < key.length; i++){ hash =(hash *31+ key.charCodeAt(i))% bucketCount;// classic polynomial rolling hash}return hash;}simpleHash('user_42',16);// deterministic — always the same bucket for this exact string
// O(n²) — the naive nested-loop approach from Module F-1functiontwoSumSlow(nums:number[], target:number):[number,number]|null{for(let i =0; i < nums.length; i++){for(let j = i +1; j < nums.length; j++){if(nums[i]+ nums[j]=== target)return[i, j];}}returnnull;}// O(n) — one pass, using a hash map to remember what we've already seenfunctiontwoSumFast(nums:number[], target:number):[number,number]|null{const seen =newMap<number,number>();// value -> indexfor(let i =0; i < nums.length; i++){const complement = target - nums[i];if(seen.has(complement)){return[seen.get(complement)!, i];} seen.set(nums[i], i);}returnnull;}
functiongroupAnagrams(words:string[]): Map<string,string[]>{const groups =newMap<string,string[]>();for(const word of words){const key = word.split('').sort().join('');// same letters -> same sorted keyif(!groups.has(key)) groups.set(key,[]); groups.get(key)!.push(word);}return groups;}