Hashing

What a hash map actually does

A hash function turns a key into a number, and that number picks a "bucket" in an underlying array. Look-up doesn't search — it computes the bucket from the key and jumps straight there. That's why Map/Set/object lookups are O(1) average case: the cost of hashing the key doesn't grow with how many other keys are already stored.

Map/Set vs plain objects

In interviews, default to Map/Set unless there's a specific reason not to — it sidesteps a whole category of "wait, why is this key already there" bugs.

The pattern: trade space for time

Almost every "hashing" interview question is the same trade: spend O(n) space to remember what you've already seen, so a second O(n) pass (or even the same pass) can answer "have I seen this before?" in O(1) instead of O(n).

// Two Sum — brute force: O(n²) time, O(1) space
function twoSumSlow(nums, target) {
  for (let i = 0; i < nums.length; i++) {
    for (let j = i + 1; j < nums.length; j++) {
      if (nums[i] + nums[j] === target) return [i, j];
    }
  }
}

// Two Sum — hashed: O(n) time, O(n) space
function twoSumFast(nums, target) {
  const seen = new Map(); // value → index
  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);
  }
}

Dry run: twoSumFast([2, 7, 11, 15], 9)

Notice the map is only ever looked up for the value we still need, and only ever written for values we've already passed. That single pass does the work a nested loop would need two passes (and O(n²) time) to do.

Frequency counting — the other 80% of hashing questions

function frequency(arr) {
  const counts = new Map();
  for (const x of arr) {
    counts.set(x, (counts.get(x) || 0) + 1);
  }
  return counts;
}

// anagram check: same characters, same counts
function isAnagram(a, b) {
  if (a.length !== b.length) return false;
  const counts = new Map();
  for (const c of a) counts.set(c, (counts.get(c) || 0) + 1);
  for (const c of b) {
    if (!counts.get(c)) return false;
    counts.set(c, counts.get(c) - 1);
  }
  return true;
}

Grouping — building a Map of arrays

// group anagrams: same sorted letters → same bucket
function groupAnagrams(words) {
  const groups = new Map();
  for (const word of words) {
    const key = [...word].sort().join("");
    if (!groups.has(key)) groups.set(key, []);
    groups.get(key).push(word);
  }
  return [...groups.values()];
}

Set membership: asking "is the neighbour here?"

Many hashing problems do not need a count or an index, only the answer to "is this value present?". A Set gives that in O(1), and it changes what you can afford to do inside a loop. Two problems show it.

Longest consecutive sequence. Given unsorted integers, find the length of the longest run of consecutive values, such as 1, 2, 3, 4, in O(n) time. Sorting gives O(n log n). With a set, you can ask "does x + 1 exist?" directly, so a run can be walked one step at a time. The danger is walking the same run many times. If you start a walk from every element, the run 1, 2, ..., n is walked once from each of its n elements, n(n+1)/2 steps in all, O(n²). The fix is to start a walk only at the beginning of a run, which is a value whose predecessor is missing.

function longestConsecutive(nums) {
  const set = new Set(nums);
  let best = 0;
  for (const x of set) {
    if (set.has(x - 1)) continue;
    let length = 1;
    while (set.has(x + length)) length++;
    if (length > best) best = length;
  }
  return best;
}

Dry run: longestConsecutive([100, 4, 200, 1, 3, 2])

The answer is 4. Why this is O(n) even though there is a while inside a for: the inner loop only runs from a run's first element, and every value belongs to exactly one run, so across the whole call the inner steps visit each value at most once. The outer loop adds n more. Total at most 2n set lookups.

Happy number. Replace a number by the sum of the squares of its digits, and repeat. Does it reach 1, or loop forever? A set of the values already seen answers it: stop at 1 (happy), or at a value you have met before (a cycle, so never happy).

function digitSquareSum(n) {
  let sum = 0;
  while (n > 0) {
    const digit = n % 10;
    sum += digit * digit;
    n = Math.floor(n / 10);
  }
  return sum;
}

function isHappy(n) {
  const seen = new Set();
  while (n !== 1 && !seen.has(n)) {
    seen.add(n);
    n = digitSquareSum(n);
  }
  return n === 1;
}

isHappy(19) follows 19 → 82 → 68 → 100 → 1 and returns true. isHappy(2) follows 2 → 4 → 16 → 37 → 58 → 89 → 145 → 42 → 20 → 4 and meets the 4 again, so it returns false. The loop must end, because the sequence cannot grow forever: a number with d digits maps to at most 81 · d, which is smaller than the number itself from four digits up, and any number below 1,000 maps to at most 243. So every sequence lives in a finite range, and a finite range forces either 1 or a repeat. The set costs O(1) extra per step; remembering nothing and detecting the cycle with a slow and a fast pointer (see Two pointers) trades the set for O(1) space.

Top-k frequent: count, then bucket by frequency

"Return the k most frequent values" has a standard first half: count every value with a Map, which costs O(n). The second half, picking the top k counts, can be done in several ways, and the comparison is a classic interview discussion.

The bucket idea: a count can only be a whole number from 1 to n, so make an array indexed by count, and put each value in the bucket of its count. The most frequent values then sit in the highest buckets; read from the top until you have k. It is counting sort applied to the counts themselves.

function topKFrequent(nums, k) {
  const counts = new Map();
  for (const x of nums) counts.set(x, (counts.get(x) || 0) + 1);

  const buckets = Array.from({ length: nums.length + 1 }, () => []);
  for (const [value, count] of counts) buckets[count].push(value);

  const out = [];
  for (let count = buckets.length - 1; count >= 1 && out.length < k; count--) {
    for (const value of buckets[count]) {
      out.push(value);
      if (out.length === k) break;
    }
  }
  return out;
}

Dry run: topKFrequent([1, 1, 1, 2, 2, 3], 2)

Time O(n): counting n values, filling at most m buckets, and reading at most n + 1 buckets, with O(n) extra space for the buckets. When the boundary bucket holds more values than there are slots left, the statement has to say which to take: if it guarantees a unique answer there is no such tie, and if it asks for, say, alphabetical order among ties, sort the values inside each bucket.

Canonical keys: make things that are equal look equal

Grouping problems ask which items are "the same" in some sense: anagrams, shifted strings, patterns with the same shape. The hashing recipe is to compute a canonical key for each item, a value that is identical for every item in the same class and different for items in different classes, and then group by that key in a Map. The sorted-letters key from the grouping section above is one. Its cost is O(L log L) per word of length L. Counting letters gives a faster one:

function groupAnagramsByCount(words) {
  const groups = new Map();
  for (const word of words) {
    const counts = new Array(26).fill(0);
    for (const ch of word) counts[ch.charCodeAt(0) - 97]++;
    const key = counts.join("#");
    if (!groups.has(key)) groups.set(key, []);
    groups.get(key).push(word);
  }
  return [...groups.values()];
}

Building a key costs O(L + 26) per word, so the whole grouping is O(n · (L + 26)), against O(n · L log L) for sorting each word. The "#" separator is not decoration. Without it, the count lists [1, 11] and [11, 1] would both join to "111", and two different words would share a key. A good key has three properties: equal items give equal keys; different items give different keys (so separators or fixed widths); and building it is cheap.

The same recipe handles "shifted" strings ("abc" and "bcd" are the same shape). Describe a word by the gaps between neighbouring letters instead of the letters themselves:

function shiftKey(word) {
  const diffs = [];
  for (let i = 1; i < word.length; i++) {
    diffs.push((word.charCodeAt(i) - word.charCodeAt(i - 1) + 26) % 26);
  }
  return diffs.join(",");
}

shiftKey("abc") and shiftKey("bcd") are both "1,1"; shiftKey("az") is "25" and shiftKey("ba") is "25" too, because the + 26 and % 26 wrap the gap around the end of the alphabet. A single letter has no gaps, so its key is the empty string, and all single-letter words land in one group, which is right since each is a shift of the other.

Bijections: two maps for isomorphic strings and word patterns

Some problems need a one-to-one correspondence, not just "same group". "egg" and "add" are isomorphic: replace e with a and g with d, and no two different letters may map to the same letter. One map is not enough. With only a forward map from s to t, the strings "bar" and "foo" pass, because b → f, a → o and r → o are each consistent, even though two different letters collide on o. A second map, in the opposite direction, catches that.

function isIsomorphic(s, t) {
  if (s.length !== t.length) return false;
  const forward = new Map();
  const backward = new Map();
  for (let i = 0; i < s.length; i++) {
    const a = s[i];
    const b = t[i];
    if (forward.has(a) && forward.get(a) !== b) return false;
    if (backward.has(b) && backward.get(b) !== a) return false;
    forward.set(a, b);
    backward.set(b, a);
  }
  return true;
}

Dry run: isIsomorphic("bar", "foo")

Word pattern is the same problem with a pattern letter on one side and a whole word, from s.split(" "), on the other. Check that the number of words equals the pattern length first, or the loop will compare against undefined. An equivalent approach is a canonical key: replace each character by the index of its first appearance, so "egg" and "add" both become [0, 1, 1], and compare the two lists. The two-map version stops at the first conflict and is easier to explain under pressure.

Composite keys: a Map compares objects by reference

A Map or Set treats two objects as the same key only if they are the same object. Arrays are objects, so a pair of coordinates stored as an array is never found again:

const visited = new Set();
visited.add([1, 2]);
visited.has([1, 2]);  // false: a different array that merely looks equal

The fix is to turn the composite value into a primitive key that is equal exactly when the parts are equal. There are three options:

• A string, such as x + "," + y. Easy, and works for any number of parts. The separator is required: "1" + "11" and "11" + "1" are the same string without it. Building the string costs O(length), and hashing it costs the same.
• A number, such as row * cols + col, when both parts have known bounds. It is the fastest, and it needs 0 <= col < cols to be one-to-one.
• Nested maps (a Map from x to a Map or Set of y). No string building, but more code.

function distinctVisited(moves) {
  let x = 0;
  let y = 0;
  const seen = new Set(["0,0"]);
  for (const move of moves) {
    if (move === "U") y++;
    else if (move === "D") y--;
    else if (move === "L") x--;
    else x++;
    seen.add(x + "," + y);
  }
  return seen.size;
}

distinctVisited("UDUD") visits (0,0), (0,1), (0,0), (0,1), (0,0), so the set holds 2 keys and the function returns 2. Negative coordinates are fine with a separator: the keys "-1,0" and "1,0" are different strings. JSON.stringify([x, y]) also works as a key but is slower, and is only safe for plain arrays and objects built in a consistent order.

Complement lookups: find each value's partner

Two Sum is one case of a wider pattern: for each item, compute the partner that would complete the answer, then ask the map whether it exists. Two variations show how far it stretches.

4Sum II. Four arrays a, b, c, d of length n each. Count the tuples (i, j, k, l) with a[i] + b[j] + c[k] + d[l] === 0. Four nested loops cost O(n⁴). Split the problem in two halves: the sums of an a-element and a b-element on one side, and of a c-element and a d-element on the other. The tuple works exactly when the left sum is the negative of the right sum. Store the left sums with their counts, then look up the negative of each right sum.

function fourSumCount(a, b, c, d) {
  const sums = new Map();
  for (const x of a) {
    for (const y of b) {
      const sum = x + y;
      sums.set(sum, (sums.get(sum) || 0) + 1);
    }
  }
  let count = 0;
  for (const x of c) {
    for (const y of d) {
      count += sums.get(-(x + y)) || 0;
    }
  }
  return count;
}

Time O(n²) and space O(n²) for the map of pair sums. Take a = [1, 2], b = [-2, -1], c = [-1, 2] and d = [0, 2]. The sums of an a-element and a b-element are -1, 0, 0 and 1, stored as {-1: 1, 0: 2, 1: 1}. The sums of a c-element and a d-element are -1, 1, 2 and 4. Their negatives are 1, -1, -2 and -4: the lookup of 1 finds one pair and the lookup of -1 finds one, while -2 and -4 find nothing, so the count is 2. A detail to trust: when x + y is 0, -(x + y) is -0, and a Map treats 0 and -0 as the same key, so the lookup still finds a stored 0.

Contains duplicate II. Is there a value that appears twice with the two positions at most k apart? For each element, the only earlier position that matters is the nearest one, the most recent time the same value appeared. A map from value to last index holds exactly that.

function containsNearbyDuplicate(nums, k) {
  const lastIndex = new Map();
  for (let i = 0; i < nums.length; i++) {
    if (lastIndex.has(nums[i]) && i - lastIndex.get(nums[i]) <= k) {
      return true;
    }
    lastIndex.set(nums[i], i);
  }
  return false;
}

containsNearbyDuplicate([1, 0, 1, 1], 1) reaches the third element, finds last index 0 and distance 2 (too far), then overwrites the stored index with 2, and at the fourth element finds distance 1 and returns true. Skipping that overwrite, keeping the first index, is the usual bug: it would compare against 0 and miss the pair. The same question can be answered with a window: a Set of the last k values, adding nums[i] and removing nums[i − k], which uses O(k) space.

Counting subarrays whose sum is a target is the complement idea applied to running totals (the partner of a prefix sum is the prefix sum minus the target). That is the main technique of Prefix sums.

How a hash map works inside: buckets, collisions and resizing

The opening section said a key picks a bucket. Here is the rest of the story, using the textbook design. Real engines vary in the details, but the costs below are why "average O(1)" is the honest claim.

1. Hash. A hash function turns the key into a large integer. Equal keys must give equal hashes; different keys should spread out.
2. Bucket. Reduce the hash to a position: hash % capacity. The table is an array of capacity buckets.
3. Collision. Two different keys can land in the same bucket. In chaining, each bucket holds a small list of its entries; a lookup goes to the bucket and walks that list, comparing keys. (The other common design, open addressing, probes neighbouring slots instead.)
4. Resize. Let the load factor be size ÷ capacity. When it passes a threshold (0.75 is a common choice), allocate a table with twice the capacity and re-insert every entry, because the bucket depends on the capacity. This costs O(n) but happens rarely.

With a good hash and a bounded load factor, the lists stay short (the average length is the load factor, below 1), so lookup, insert and delete take O(1) on average. The resize is the same doubling argument as the array's push: expensive occasionally, amortized O(1) per insert (see Complexity analysis). The worst case is every key in one bucket: O(n) per operation. A bad hash function, or keys chosen by an adversary who knows the hash, can cause it, which is why production hash tables seed or randomize their hashing.

What counts as "the same key" is a language decision, and JavaScript has specific rules:

Map and Set compare keys with a rule called SameValueZero. It differs from === in exactly one way that matters: NaN equals NaN. That is also why [NaN].includes(NaN) is true while [NaN].indexOf(NaN) is -1: includes uses SameValueZero and indexOf uses ===. A Map also remembers insertion order, and re-inserting an existing key keeps its place, but deleting a key and adding it again moves it to the end.

Build a HashMap from scratch

Interviewers like "implement a hash map" because it checks that you know what the library hides. The design below uses string keys, chaining, a polynomial string hash, and doubling at load factor 0.75.

function hashString(s) {
  let h = 0;
  for (let i = 0; i < s.length; i++) {
    h = (h * 31 + s.charCodeAt(i)) >>> 0;
  }
  return h;
}

class ChainedMap {
  constructor() {
    this.capacity = 8;
    this.size = 0;
    this.buckets = Array.from({ length: this.capacity }, () => []);
  }

  indexFor(key, capacity) {
    return hashString(key) % capacity;
  }

  get(key) {
    const bucket = this.buckets[this.indexFor(key, this.capacity)];
    for (const entry of bucket) {
      if (entry[0] === key) return entry[1];
    }
    return undefined;
  }

  has(key) {
    const bucket = this.buckets[this.indexFor(key, this.capacity)];
    return bucket.some((entry) => entry[0] === key);
  }

  put(key, value) {
    const bucket = this.buckets[this.indexFor(key, this.capacity)];
    for (const entry of bucket) {
      if (entry[0] === key) {
        entry[1] = value;
        return;
      }
    }
    bucket.push([key, value]);
    this.size++;
    if (this.size > this.capacity * 0.75) this.grow();
  }

  remove(key) {
    const bucket = this.buckets[this.indexFor(key, this.capacity)];
    for (let i = 0; i < bucket.length; i++) {
      if (bucket[i][0] === key) {
        bucket.splice(i, 1);
        this.size--;
        return true;
      }
    }
    return false;
  }

  grow() {
    const bigger = this.capacity * 2;
    const next = Array.from({ length: bigger }, () => []);
    for (const bucket of this.buckets) {
      for (const entry of bucket) {
        next[this.indexFor(entry[0], bigger)].push(entry);
      }
    }
    this.buckets = next;
    this.capacity = bigger;
  }
}

The hash multiplies the running value by 31 and adds the next character code, the same polynomial idea as the string hashes of the string algorithms chapter. The >>> 0 keeps the value an unsigned 32-bit integer, and the product stays far below 2⁵³, so the arithmetic is exact. For "cat" the hash is 98,262, which is bucket 6 of 8; for "act" it is bucket 2; and for "tac" it is bucket 6 again.

Dry run: three puts, then a collision and a lookup

The two clashing keys share bucket 6, and the get has to compare keys to tell them apart: the bucket only narrows the search. The resizes happen at the 7th insertion (size 7 is more than 0.75 × 8 = 6, so capacity goes 8 → 16) and the 13th (13 is more than 12, so 16 → 32). With 1,000 keys such as "user0" through "user999" the table ends at capacity 2,048 with a longest chain of 3.

When hashing is the wrong tool

• You need order — a hash map doesn't sort. If the question wants sorted output or range queries, you likely want a sorted structure (or a heap) instead.
• You need the closest match, not an exact one — hashing only answers "is this exact key present." Nearest-value questions want binary search on a sorted structure.
• Memory is the actual constraint — if the problem explicitly asks for O(1) space, a hash map is disqualified by definition.