What a hash table is
You have a list of numbers
[2, 7, 11, 15] and a target 9 — which two add up to it? The brute-force move checks every pair (2+7, 2+11, 2+15, 7+11, …), a loop inside a loop, O(n²): 6 checks for four numbers, half a trillion for a million.A hash table stores key → value pairs and finds any key almost instantly. The magic is a hash function that turns a key into a bucket index: so you jump straight to it instead of searching. It's a coat check: your ticket number points right to the one hook holding your coat — no scanning the whole rack. Insert, look up, and delete are all
O(1) on average.That instant "have I seen this?" is what turns the two-sum wall into a one-pass sweep.
You already met a baby version of this in the Strings lesson — the frequency map that tallied letters. In the animation below, watch where each key lands: the hash function computes
key % 7, and the key drops straight into that bucket with no searching. When two keys land in the same bucket, that is a collision — notice the table still works, the bucket just holds more than one entry.This section has a step-by-step animation in the interactive lesson.
Quick check
A hash table finds a key in O(1) on average because…
Answer it in the interactive lesson to keep your progress.
The core operations
Think of a hash table as a fast notebook. When you see a new item, write it down with a key. Later, when you need it, you read it back instantly instead of searching.
- set
map.set(key, value)— jot down the fact. - get
map.get(key)— look it up. - has
map.has(key)— check whether it exists. - delete
map.delete(key)— erase it. - size
map.size— see how many facts you remember.
These operations are
O(1) on average. Use a Map for flexible key types and a plain {} for simple string/number keys. Use a Set when you only care whether an item has appeared.const pets = new Map();
pets.set('cat', 3);
pets.set('dog', 5);
pets.set('bird', 1);
console.log(pets.get('cat')); // 3
console.log(pets.has('dog')); // true
pets.delete('dog');
console.log(pets.has('dog')); // false
console.log(pets.size); // 2Quick check
You only need to answer "has this value appeared before?" — nothing else. The right tool is…
Answer it in the interactive lesson to keep your progress.
Your first hash-table problem: two sum
In
[2, 7, 11, 15], find the two numbers that add up to 9. The brute force tests every pair (O(n²)). A hash table does it in one pass by remembering each number as we go and asking whether its partner has already appeared.The steps
- Keep a
seenmap of the numbers encountered so far. - For each number
x, compute the partner it needs:target - x. - If that partner is already in
seen→ we've found the pair. - Otherwise, add
xtoseenand move on.
Trace it for target 9:
x = 2: partner needed is7. Seen7? No → remember2.x = 7: partner needed is2. Seen2? Yes → pair found.
One pass, not nested loops — the hash table is the memory that instantly answers "did the matching partner already appear?" In JavaScript, one way to write those steps:
As the animation steps through the array, watch the
seen map grow on the side: each number is written down after its partner check fails. Before every step, predict the partner (target - x) and whether it is already in the map — the step where your prediction says "yes" is the step the search ends.This section has a step-by-step animation in the interactive lesson.
function twoSum(nums, target) {
const seen = new Map(); // value -> its index
for (let i = 0; i < nums.length; i++) {
const need = target - nums[i]; // the complement that completes the pair
if (seen.has(need)) return [seen.get(need), i];
seen.set(nums[i], i); // remember this value for later
}
return [];
}
console.log(twoSum([2, 7, 11, 15], 9)); // [0, 1]Quick check
In two-sum, at value x you look up…
Answer it in the interactive lesson to keep your progress.
Where it breaks (and how not to get burned)
Hash tables are fast, but they have limits. Keep these in mind:
- Plain objects stringify keys.
1and'1'become the same key, and objects can turn complex keys into'[object Object]'. UseMapinstead of{}when your keys are not simple strings or numbers. O(1)is average, not magical. If many keys land in the same bucket, lookups can slow towardO(n). Good implementations keep collisions rare, but the cost is still real.- Ordering is not guaranteed. A
Mapkeeps insertion order, but a plain object should not be relied on for sorted or stable traversal. - Reference keys compare by identity. Two different arrays with the same contents are different keys unless they are the same object.
Quick check
Two different keys landing in the same bucket is called…
Answer it in the interactive lesson to keep your progress.
How fast is it? (complexity)
Using the vocabulary from the Complexity & Time lesson, insertions and lookups are
O(1) on average — so a problem that would be O(n²) with brute force becomes O(n):| Approach to two-sum | Time | Space | Why |
|---|---|---|---|
| brute force — check every pair | O(n²) | O(1) | a loop inside a loop |
hash table — one pass with seen | O(n) | O(n) | each lookup is O(1) on average |
That row swap — spending
O(n) memory to erase a factor of n in time — is the single most common trade in interviews.Key takeaways:
- A hash function directs a key to a bucket so you go straight to the answer.
- Use a hash table whenever the problem asks have I seen this before?, how many are there?, or what pair matches this?.
- Use
Mapfor flexible key types, andSetwhen you only need membership.
Once you can count or remember values with a map, problems like grouping anagrams, two-sum, and the first unique character become much easier — each its own lesson later. Next up in order: Two Pointers — walking an array from both ends at once.
const words = ['apple', 'banana', 'apple', 'cherry', 'banana', 'apple'];
const counts = new Map();
for (const w of words) {
counts.set(w, (counts.get(w) || 0) + 1);
}
console.log([...counts.entries()]); // [['apple',3],['banana',2],['cherry',1]]
console.log(counts.get('apple')); // 3