What is a hash table?
A hash table is a structure that stores key → value pairs — a name and the fact attached to it — and can find any key almost instantly, no matter how much it holds. It does this with a hash function: a small calculation that turns the key itself into the number of the slot (called a bucket) where the entry lives. The key tells you where to look, so there is nothing to search.
In this lesson you'll learn the handful of operations a hash table gives you, and how its instant "have I seen this before?" turns slow, rescanning code into a single pass.
Think of a coat check. You hand over your coat and get ticket 17; when you return, the attendant walks straight to hook 17 — nobody searches the rack. The ticket number is the location. A hash function plays the same trick with any key: for example, add up the letters' alphabet positions and keep the remainder after dividing by the number of buckets. "Ana" sums to 16, and 16 divided by 5 buckets leaves remainder 1 — so Ana lives in bucket 1, always.
Store three contacts in words first, into 5 buckets: Ana's letters sum to 16, and 16 ÷ 5 leaves remainder 1 — bucket 1. Mia sums to 23, remainder 3 — bucket 3. Raj sums to 29, remainder 4 — bucket 4. Now look Raj up: run the same math — 29, remainder 4 — and jump straight to bucket 4. One step, whether you store three contacts or three million. Watch it below. (When two keys happen to land in the same bucket, that's called a collision; the bucket simply holds both entries, and the table still works.)
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.Map and Set Operations in JavaScript
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 way tests every pair — a loop inside a loop, O(n²) checks. 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 | partner needed | already in seen? | action |
|---|---|---|---|
| 2 | 9 − 2 = 7 | no | remember 2 |
| 7 | 9 − 7 = 2 | yes | pair found: [0, 1] |
Two steps, done — the nested loops never happen. The hash table is the memory that instantly answers "did the matching partner already appear?"
Two Sum with a Hash Map in JavaScript
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.
The See it step animates the two classics: keys dropping straight into their buckets (collisions included), and the famous two-sum sweep with the
seen map growing beside the array. Once you can count or remember values with a map, problems like grouping anagrams 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.Counting with a Map in JavaScript
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