Hashing — the Basics
EasyO(1) average lookups, counts & sets
A hash map is like a magic backpack: you stick a label on something and can grab it back instantly without searching.
The idea
A hash map/set stores keys for near-instant lookup, insertion and deletion. Use it to count occurrences, remember what you've seen, or map keys to values in a single pass.
4
2
4
1
2
4
0
1
2
3
4
5
Step 1 of 8. One pass builds a frequency map: for each value, bump its count. Values: 4, 2, 4, 1, 2, 4.
1/8
Optimal
timeO(n)spaceO(n)
Tally in one pass.
1const freq = new Map();2for (const x of arr)3 freq.set(x, (freq.get(x) ?? 0) + 1);Input
- array
- [4, 2, 4, 1, 2, 4]
Memory
- #4
- —
- #2
- —
- #1
- —
Output
- #1
- —
- #2
- —
- #4
- —
Check yourself
3 quick questions about this walkthrough. A wrong answer costs nothing.
Examples
Example 1
- Input:
- counts = {}; for c in "banana": counts[c] += 1
- Output:
- {b: 1, a: 3, n: 2}
- Explanation:
- Each letter is looked up and bumped in constant time, so the whole string costs one pass rather than a scan per distinct letter.
Example 2
- Input:
- seen = set(); 4 in seen after adding [1, 4, 9]
- Output:
- true
- Explanation:
- A set answers 'have I met this before?' without walking the list, which is what turns an O(n²) double loop into O(n).
Finished the walkthrough? Add it to your streak.