Hash Tables

A hash table maps keys to values in O(1) average time for insertions, lookups, and deletions. It is the single most useful data structure in coding interviews — when you see the words "find", "count", "group", or "duplicate", a hash table is almost always part of the optimal solution.

JavaScript gives you two clean built-ins: Map and Set.

Map and Set — The JS Primitives

// ── Map: key → value ──────────────────────────────────────────────
const map = new Map();

map.set('apple', 3);
map.set('banana', 5);
map.set('apple', 4); // overwrites previous value

console.log(map.get('apple'));   // 4
console.log(map.has('banana'));  // true
console.log(map.has('grape'));   // false
console.log(map.size);           // 2

map.delete('banana');
console.log(map.size);           // 1

// Iteration
for (const [key, val] of map) {
  console.log(key, val);
}

// ── Set: unique values ─────────────────────────────────────────────
const set = new Set([1, 2, 3, 2, 1]);
console.log(set.size);           // 3
console.log(set.has(2));         // true

set.add(4);
set.delete(1);
console.log([...set]);           // [2, 3, 4]

// Deduplication trick
const arr = [1, 2, 2, 3, 3, 3];
const unique = [...new Set(arr)]; // [1, 2, 3]

Internal Structure: Buckets and Hashing

Internally a hash table maintains an array of buckets. When you call map.set(key, value):

A hash function converts key into an integer.
The integer is mapped to a bucket index: index = hash(key) % numBuckets.
The (key, value) pair is stored in that bucket.

On map.get(key) the same hash function runs again, jumping directly to the right bucket — no scanning. Two different keys that land in the same bucket is a collision; JavaScript's Map handles this with separate chaining (each bucket is a linked list or small array of entries).

As long as the load factor (number of entries / number of buckets) stays low, collisions are rare and all operations stay O(1) amortized. When the load factor exceeds a threshold the table is rehashed — a new larger array is allocated and all entries are re-inserted.

Note

Average O(1) is guaranteed only when the hash function distributes keys uniformly. JavaScript's built-in Map uses a well-tested implementation — you get O(1) for free. When you implement a hash table yourself (rare in interviews), pick a prime modulus and a polynomial rolling hash.

Map vs Plain Object vs Array

Structure	Key type	Ordered?	Best for
Map	Any value (object, number, string)	Insertion order	General-purpose key→value
Object {}	String / Symbol only	Mostly insertion order	Fixed, known string keys
Array (freq)	Integer index 0–25	Yes	Fixed alphabet (lowercase a-z)
Set	Any value	Insertion order	Membership / deduplication

Tip

Use a 26-element array for lowercase-only problems (fastest), a plain object for known string keys, and Map when keys are dynamic or non-string.

Pattern 1 — Two Sum

The canonical hash table problem. Instead of checking every pair O(n²), store each value in a Map as you scan. For each element, check if its complement is already in the Map.

// LeetCode 1 — Two Sum
function twoSum(nums, target) {
  const seen = new Map(); // value → index

  for (let i = 0; i < nums.length; i++) {
    const complement = target - nums[i];
    if (seen.has(complement)) {
      return [seen.get(complement), i];
    }
    seen.set(nums[i], i);
  }
  return [];
}

console.log(twoSum([2, 7, 11, 15], 9)); // [0, 1]
console.log(twoSum([3, 2, 4],      6)); // [1, 2]
console.log(twoSum([3, 3],         6)); // [0, 1]

Pattern 2 — Contains Duplicate

// LeetCode 217 — Contains Duplicate
function containsDuplicate(nums) {
  const seen = new Set();
  for (const n of nums) {
    if (seen.has(n)) return true;
    seen.add(n);
  }
  return false;
}

// Shorter one-liner
const containsDuplicateShort = nums => new Set(nums).size !== nums.length;

console.log(containsDuplicate([1,2,3,1])); // true
console.log(containsDuplicate([1,2,3,4])); // false

Pattern 3 — Group Anagrams

// LeetCode 49 — Group Anagrams
function groupAnagrams(strs) {
  const map = new Map();
  for (const s of strs) {
    const key = s.split('').sort().join('');
    if (!map.has(key)) map.set(key, []);
    map.get(key).push(s);
  }
  return [...map.values()];
}

console.log(groupAnagrams(['eat','tea','tan','ate','nat','bat']));
// [['eat','tea','ate'], ['tan','nat'], ['bat']]

Pattern 4 — Longest Consecutive Sequence

Find the longest streak of consecutive integers (LeetCode 128). The naive sort-then-scan is O(n log n). With a Set you can do it in O(n):

For each number, only start counting from it if num - 1 is NOT in the Set (i.e. it is the beginning of a streak). Then extend as far as the Set contains the next value.

function longestConsecutive(nums) {
  const numSet = new Set(nums);
  let best = 0;

  for (const n of numSet) {
    // Only start from the beginning of a streak
    if (numSet.has(n - 1)) continue;

    let current = n;
    let length = 1;
    while (numSet.has(current + 1)) {
      current++;
      length++;
    }
    best = Math.max(best, length);
  }
  return best;
}

console.log(longestConsecutive([100,4,200,1,3,2])); // 4  (1,2,3,4)
console.log(longestConsecutive([0,3,7,2,5,8,4,6,0,1])); // 9

Note

We iterate each number at most twice — once in the outer for loop, once inside the while. Total O(n). The trick of skipping non-starters keeps the inner loop from running for every element.

Pattern 5 — Frequency Counting Template

Frequency counting comes up so often it is worth memorising as a template:

// Generic frequency counting template
function solveWithFrequency(arr) {
  // Step 1 — build frequency map
  const freq = new Map();
  for (const item of arr) {
    freq.set(item, (freq.get(item) ?? 0) + 1);
  }

  // Step 2 — query the map
  // e.g. find element with highest frequency
  let maxFreq = 0, result = null;
  for (const [item, count] of freq) {
    if (count > maxFreq) {
      maxFreq = count;
      result = item;
    }
  }
  return result;
}

// Example: LeetCode 169 — Majority Element (appears > n/2 times)
function majorityElement(nums) {
  const freq = new Map();
  const threshold = nums.length / 2;
  for (const n of nums) {
    const count = (freq.get(n) ?? 0) + 1;
    if (count > threshold) return n;
    freq.set(n, count);
  }
}

console.log(majorityElement([3,2,3]));   // 3
console.log(majorityElement([2,2,1,1,1,2,2])); // 2

Complexity Reference

Operation	Average	Worst case
set / add	O(1)	O(n) — rehash
get / has	O(1)	O(n) — all keys collide
delete	O(1)	O(n)
iteration	O(n)	O(n)
size	O(1)	O(1)

Warning

The worst case O(n) per operation occurs when all keys hash to the same bucket. This is extremely rare with a good hash function but can be deliberately triggered — a concern for security-sensitive code, not interviews.

Practice Problems

LeetCode 1 — Two Sum
LeetCode 217 — Contains Duplicate
LeetCode 49 — Group Anagrams
LeetCode 128 — Longest Consecutive Sequence
LeetCode 169 — Majority Element
LeetCode 347 — Top K Frequent Elements
LeetCode 560 — Subarray Sum Equals K (Map + prefix sum)
LeetCode 146 — LRU Cache (Map for O(1) ordered access)