Hash map

Overview

A hash map stores key-value pairs and supports insert, lookup, and delete in O(1) on average. A hash function converts the key into an integer, which picks a bucket in an internal array. Collisions (two keys in one bucket) are handled by chaining or probing.

Hash maps are the most common tool for turning an O(n^2) solution into O(n). Whenever you catch yourself searching for something you saw earlier, ask: can I remember it in a map?

When to use it

• You need to remember something about earlier elements: indexes, counts, prefix sums.
• Counting frequencies of characters, words, or numbers.
• Grouping items by a computed key (anagrams, same pattern).
• Caching / memoization of computed results.
• Building an index from an ID to an object.

Problem patterns it solves

Where it is used in real software

Key terms

Hash function

Maps a key to an integer. Must be deterministic; good ones spread keys uniformly.

Bucket

Slot in the internal array chosen by hash(key) mod capacity.

Collision

Two different keys map to the same bucket.

Load factor

entries / buckets. When it passes a threshold (0.75 in Java), the table resizes.

Rehashing

Allocating a larger array and reinserting every entry; amortized O(1) per insert.

What happens on put(key, value)

1. 1
   Hash the key

   Compute key.hashCode() (Java) or the engine's internal hash.

2. 2
   Pick the bucket

   index = hash mod capacity (Java uses hash & (capacity - 1) with a power-of-two capacity).

3. 3
   Search the bucket

   Compare keys with equals. If found, replace the value.

4. 4
   Insert

   Otherwise add a new entry to the bucket's chain.

5. 5
   Resize if needed

   If the load factor is exceeded, double the capacity and redistribute all entries.

Two Sum with a hash map

nums = [2, 7, 11, 15], target = 9

The map remembers every value already passed, so each element needs one O(1) lookup: O(n) total instead of checking all pairs in O(n^2).

Implementation

1// Use Map, not {}: any key type, reliable size, no prototype keys2function twoSum(nums, target) {3  const seen = new Map();4  for (let i = 0; i < nums.length; i++) {5    const need = target - nums[i];6    if (seen.has(need)) return [seen.get(need), i];7    seen.set(nums[i], i);8  }9  return [];10}11 12function groupAnagrams(words) {13  const groups = new Map();14  for (const word of words) {15    const counts = new Array(26).fill(0);16    for (const ch of word) counts[ch.charCodeAt(0) - 97]++;17    const key = counts.join("#"); // O(k) key instead of sorting O(k log k)18    if (!groups.has(key)) groups.set(key, []);19    groups.get(key).push(word);20  }21  return [...groups.values()];22}23 24// 1248. Count Number of Nice Subarrays (exactly k odd numbers)25function numberOfSubarrays(nums, k) {26  const countByOdds = new Map([[0, 1]]);27  let odds = 0, result = 0;28  for (const x of nums) {29    if (x % 2 === 1) odds++;30    result += countByOdds.get(odds - k) ?? 0;31    countByOdds.set(odds, (countByOdds.get(odds) ?? 0) + 1);32  }33  return result;34}35 36function longestConsecutive(nums) {37  const set = new Set(nums);38  let best = 0;39  for (const x of set) {40    if (set.has(x - 1)) continue; // only start at the beginning of a run41    let length = 1;42    while (set.has(x + length)) length++;43    best = Math.max(best, length);44  }45  return best;46}

Complexity and performance

Trade-offs

Variants and related techniques

Common mistakes

• Using a JS object {} as a map with arbitrary keys.

  Fix: Object keys become strings and inherit prototype properties like 'constructor'. Use Map.

• Mutable objects as keys.

  Fix: If a key's hash changes after insertion, it can never be found again. Use immutable keys.

• Overriding equals without hashCode in Java.

  Fix: Equal objects must have equal hash codes, or lookups fail.

• Comparing Integer values with == in Java.

  Fix: Boxed Integers above 127 are different objects; use .equals or unbox.

Interview questions

Practice problems