Hash Map & Set (JS Map and Set)

ComplexityCopy Anchor Link

Space is O(n).

A hash map stores key-value pairs and finds a value from its key in O(1) on average. A set stores unique values and answers "is this in here?" in O(1). In JavaScript these are Map and Set. The theory (hash functions, collisions) is in the Hash Table topic.

Map or plain objectCopy Anchor Link

Key equalityCopy Anchor Link

Map and Set compare keys with SameValueZero. Primitives compare by value, objects and arrays compare by reference.

new Set([[1, 2], [1, 2]]).size; // 2, two different arrays
new Set([NaN, NaN]).size;       // 1, NaN equals NaN here

To key by a pair, build a string key: `${r},${c}`.

Patterns it unlocksCopy Anchor Link

• Frequency count: map.set(x, (map.get(x) ?? 0) + 1).
• Seen set: detect duplicates or visited nodes in one pass.
• Complement lookup: Two Sum.
• Group by key: anagrams (sorted word as key), buckets.
• Cache: memoization, LRU (a Map keeps insertion order).
• Index: value to position for O(1) jumps.

Common mistakesCopy Anchor Link

• Using an array includes in a loop when a Set would make it O(n) instead of O(n²).
• Using an object as a map with user-supplied keys such as __proto__.
• Expecting two equal-looking arrays to be the same key.
• Mutating a Map or Set while iterating over it.

CodeCopy Anchor Link

export const frequencies = items => {
  const freq = new Map();
  for (const x of items) freq.set(x, (freq.get(x) ?? 0) + 1);
  return freq;
};

export const hasDuplicate = nums => new Set(nums).size !== nums.length;

export const twoSum = (nums, target) => {
  const index = new Map(); // value -> position
  for (let i = 0; i < nums.length; i++) {
    if (index.has(target - nums[i])) return [index.get(target - nums[i]), i];
    index.set(nums[i], i);
  }
  return null;
};

export const groupAnagrams = words => {
  const groups = new Map();
  for (const w of words) {
    const key = [...w].sort().join('');
    groups.set(key, [...(groups.get(key) ?? []), w]);
  }
  return [...groups.values()];
};

export const intersection = (a, b) => {
  const inA = new Set(a);
  return [...new Set(b.filter(x => inA.has(x)))];
};