Hash maps

What you'll learn

How a hash map stores key-value pairs, why lookup is fast, and two classic uses: counting and remembering.

Why it matters

Hash maps (also called dictionaries or objects) are the most useful tool in coding interviews and real code. Anywhere you hear "look up by name", it is probably a hash map.

Explanation

A hash map stores key-value pairs: "asha" -> 91. You give it a key and it hands back the value.

Under the hood it runs the key through a hash function that turns it into an array index. The value is stored at that index, so a lookup is a direct jump, O(1) on average.

In JavaScript the built-in Map is a hash map. Plain objects work too, but Map is cleaner for arbitrary keys.

Two patterns to remember:

• Counting: map each item to how many times you have seen it.
• Remembering: store what you have seen so you can check "have I seen this before?" in O(1).

Example

Step-by-step walkthrough

1. set stores a pair and get fetches by key: 91.
2. has asks "is this key present?" and answers false for zoya.
3. For "banana", the loop reads one letter at a time. counts.get(ch) || 0 gives the old count (or 0 if new), and we store it plus one.
4. After the loop: b is 1, a is 3, n is 2. Object.fromEntries turns the map into a plain object for printing: { b: 1, a: 3, n: 2 }.

Try it yourself

Count how often each word appears in ["red", "blue", "red", "green", "blue", "red"].

Count wordsJavaScript

Editable codeconst words = ["red", "blue", "red", "green", "blue", "red"]; const counts = new Map(); for (const w of words) { counts.set(w, (counts.get(w) || 0) + 1); } console.log(Object.fromEntries(counts));

Run ResetCopyCtrl+Enter to run

Common mistakes

• Using an array to look things up and scanning it every time (O(n)).
• Forgetting the default. counts.get(x) + 1 is NaN for a new key. Use || 0.
• Mutating keys. Use simple strings or numbers as keys.
• Assuming order. Do not rely on the order of keys in a hash map.

Quick quiz

Summary

• Hash maps store key-value pairs with O(1) average lookup.
• Use them for counting and for remembering what you have seen.
• Do not depend on key order.

Next: stacks, the pile of plates.

const scores = new Map();
scores.set("asha", 91);
scores.set("ravi", 78);

console.log(scores.get("asha"));   // 91
console.log(scores.has("zoya"));   // false

// Counting letters
const counts = new Map();
for (const ch of "banana") {
  counts.set(ch, (counts.get(ch) || 0) + 1);
}
console.log(Object.fromEntries(counts));