Hash Maps

The idea#

Picture a coat check. You hand over a coat and get a ticket. When you come back, they go to that hook. They do not pat down every coat on the rack.

You trade O(n) space for O(1) average lookups, and that trade turns a nested loop into one pass. The worst case is O(n) per operation, when every key lands in the same bucket.

A hash map stores pairs of key and value. A hash set stores keys alone, for "have I seen this." The hash function turns the key into a bucket number. Two different keys can land in one bucket. That is a collision. Chaining keeps a short list in the bucket. Open addressing walks forward to the next empty slot, which is linear probing. The load factor is the number of keys divided by the number of buckets. When it climbs past about 0.75, you rehash: double the buckets and place every key again. That keeps the average operation O(1).

JavaScript's Map remembers insertion order. That is part of the tool, not a side effect you should ignore. The first key you inserted is the first key you meet when you iterate. A frequency map is the everyday idiom: read the old count, or zero if the key is new, add one, store it back.

Why it matters#

Any time you are about to write two loops, one scanning and one searching the same array, stop and ask whether a map or a set would remember the first scan. Two-sum is the poster. The slow version checks every pair, O(n²). One pass stores each number's index and asks whether target - num is already there, O(n) time and O(n) space.

The words that mean "reach for a map" are count, frequency, seen before, pairs that sum to, group by, consecutive, and subarray sum equals. "O(n) required" usually means the same thing: the quadratic answer is obvious, and the map is how you pay for the linear one.

You already depend on this. An object used as a dictionary, a set of user ids you have already processed, a tally of votes. The bug is assuming the average case is a promise. If your hash ignores the key and returns a constant, every operation walks one long chain and you are back to O(n). Say that out loud when someone asks. Then say how a load factor and a rehash keep the chains short.

Map beats a plain object when the keys are not strings, when you need the size, or when insertion order is the order you will evict. An LRU cache can be a Map alone: delete a key and set it again, and it moves to the most recently used end. The oldest key is the first one in iteration order.

A small example#

function twoSum(nums, target) {  const seen = new Map();  for (let i = 0; i < nums.length; i++) {    const need = target - nums[i];    if (seen.has(need)) return [seen.get(need), i];    seen.set(nums[i], i);  }  return [];} const pair = twoSum([2, 7, 11, 15], 9);

pair is [0, 1]. The map held 2 before 7 arrived, so the complement lookup finished the pair in one pass.

What the code below is doing#

Section 1 is the frequency idiom: map.set(k, (map.get(k) ?? 0) + 1). O(n) time, O(k) space for k distinct keys. Section 2 is two-sum, the complement lookup above. Section 3 groups anagrams. The key is a signature of 26 counts joined together, so you never sort the letters. O(n · k) for n words of length k. Section 4 finds the longest consecutive run. Put the numbers in a set. Only start counting at x when x - 1 is absent, then walk forward. Each number is visited a constant number of times, so the whole thing is O(n), even though a loop sits inside a loop.

Section 5 counts subarrays whose sum is k. Keep a map from prefix sum to how many times you have seen it, seeded with {0: 1}. At each index add the count stored at prefix - k. Negatives are fine, which is why a sliding window on this problem would answer a different question. O(n) time and space. Section 6 spots a duplicate within distance k by storing value to last index. Section 8 finds the first non-repeating character with a frequency pass and then an order pass. Map yields keys in insertion order, so the first key whose count is 1 is the answer.

Section 7 is an LRU on Map order. Delete and set on get, so the key moves to the newest end. Over capacity, evict map.keys().next().value. Section 9 intersects two arrays down to unique values with a set. Section 10 buckets values by count and walks from the high count, O(n), for the top k frequent.

Section 11 builds a hash map from scratch. hash(key) % buckets picks a list of [key, value] pairs. Put updates a pair that is already in the chain, or appends one. Get and remove scan that one chain. Past a load factor of about 0.75, rehash doubles the bucket array and inserts again. That is the sentence to say: chaining or open addressing for collisions, rehash to keep the average O(1).

When you talk about it, say this: a map spends O(n) space to answer "have I seen this" in O(1) on average, and a bad hash that piles every key into one bucket falls back to O(n).

Everything below is the demonstration. Same idea, written as code you can run.