Hash tables: hashing and collisions

A hash table is the structure behind Map, Set, JavaScript objects, Python dicts, database indexes and caches. It is also the single most useful tool in a coding interview, because it answers "have I seen this before?" and "what is the value for this key?" in constant time.

The problem it solves

You have a list of a million users and you need the one with a given email. Three options:

• Scan the array. O(n). A million comparisons per lookup.
• Keep it sorted and binary search. O(log n) per lookup, but every insert now costs O(n) to keep the order.
• Compute where the answer must be. O(1) for both. This is a hash table.

The idea: if you could turn the key into an array index, you could jump straight to it, the same way arr[42] is a single jump. A hash function does exactly that: it turns any key into a number, and a modulo turns the number into a valid index.

Structure

Three parts:

• A bucket array, the storage.
• A hash function mapping a key to an integer, the same integer every time for the same key.
• A collision strategy, for when two keys land in the same bucket (next section).

class HashTable {
  constructor(size = 32) {
    this._size    = size;
    this._buckets = Array.from({ length: size }, () => []);
  }

  _hash(key) {
    const s = String(key);
    let h = 0;
    for (let i = 0; i < s.length; i++) {
      h = (h * 31 + s.charCodeAt(i)) % this._size; // position-sensitive
    }
    return h;
  }
}

Given the same key, the hash function always returns the same index, so get jumps straight to the right bucket instead of scanning.

A good hash function has three properties: it is deterministic (same key, same number), fast, and uniform (keys spread evenly over the buckets). The multiply-by-31 above matters: a naive hash that just sums character codes gives "listen" and "silent" the same value, because addition ignores order. Multiplying makes each character's position count.

Collisions are not a bug, they are the plan

There are far more possible keys than buckets, so by the pigeonhole principle two different keys will eventually land in the same bucket. A hash table is not broken when that happens: the design has to expect it. The most common answer is separate chaining, where each bucket holds a small list of [key, value] pairs.

put(key, value) {
  const bucket = this._buckets[this._hash(key)];
  const pair   = bucket.find(([k]) => k === key);
  if (pair) pair[1] = value;         // update
  else bucket.push([key, value]);    // insert
}

get(key) {
  const bucket = this._buckets[this._hash(key)];
  return bucket.find(([k]) => k === key)?.[1];
}

Note that lookups compare the full key after landing in the bucket. The hash only narrows the search, it never proves equality.

The other main strategy is open addressing: no chains, and on a collision you probe other slots in the same array (the next slot, then the next, or by a step pattern) until you find a free one. It is cache-friendlier, but deletion is trickier because removing an entry can break a probe sequence, so implementations leave a "tombstone" marker behind.

Load factor and resizing

The load factor is entries divided by bucket count. Keep it low, and every chain stays short enough that "scan the bucket" is effectively constant work. Real implementations resize (usually doubling) once it crosses roughly 0.7 to 0.75.

Two consequences worth knowing:

• Resizing is O(n), because every key must be rehashed: the modulus changed, so almost every index changed. Spread over many inserts, the amortised cost stays O(1), which is why the complexity is quoted as "amortised".
• The worst case is O(n). If every key collides into one bucket, the table degrades to a list. A good hash function makes that vanishingly rare, but an attacker who can choose keys can craft collisions on a weak hash. That is a real denial-of-service attack, and the reason languages randomise their hash seeds.

The patterns that solve half of all interview questions

Most hash table problems are one of four moves. Learn to recognise them.

1. Seen before? (a set)

Store what you have visited, and check before you add. "First duplicate", "contains duplicate" and "first repeated character" all reduce to this.

function firstDuplicate(items) {
  const seen = new Set();
  for (const x of items) {
    if (seen.has(x)) return x;
    seen.add(x);
  }
  return null;
}

2. Count things (a frequency map)

Map<value, count> answers "how many times", "which is most common" and "are these two strings anagrams". It is also step one of top-k problems: count with a hash table, then pick the best k with a heap.

3. Find the complement (two sum)

"Which two numbers add up to the target?" The brute force checks every pair, O(n²). With a hash table, for each number you ask "have I already seen target - x?" in O(1), so the whole problem is one pass.

function twoSum(nums, target) {
  const indexOf = new Map(); // value -> index where we saw it
  for (let i = 0; i < nums.length; i++) {
    const need = target - nums[i];
    if (indexOf.has(need)) return [indexOf.get(need), i];
    indexOf.set(nums[i], i);
  }
  return null;
}

The same shape solves "subarray sum equals k" with prefix sums, "longest consecutive sequence", and any "have I seen the partner of this value?" question.

3. Group by a canonical key

When several inputs should be treated as the same thing, compute a canonical key that is identical for all of them, and use it to bucket the inputs. Anagrams are the textbook case: sorting a word's letters gives every anagram the same key.

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()];
}

The same idea groups by any derived key: the day of a timestamp, the domain of an email, the normalised form of a name, the shape of a graph edge.

Object, Map, dict, and the one you build yourself

Every mainstream language ships at least one hash table for free, and the built-ins are not interchangeable.

All of them are, underneath, the structure above: a hash function mapping keys to buckets, with a collision strategy and resizing. Two practical rules follow. Use Map (not a plain object) when keys come from user input, to avoid __proto__ and inherited-key bugs. And use Set instead of an object with true values when you only need membership.

A subtle trap: objects and arrays are hashed by identity, not by content. map.get([1, 2]) will never find a value stored under a different [1, 2] array. If you need content-based keys, serialise to a string (JSON.stringify, or "1,2") and use that as the key.

Where hash tables are used in real systems

Hash tables you already use

• `Map`, `Set`, `WeakMap` in JavaScript, and dict, set and Counter in Python.
• Every JavaScript object. Property lookup is, conceptually, a hash lookup (engines optimise it further with hidden classes).
• Redis. A key-value store whose core is a big hash table, with HSET for hash-valued keys.
• `GROUP BY` and hash joins in SQL. Databases group rows and match join keys with hash tables.
• React's `key` prop reconciliation maps keys to previous elements to decide what to move, add or remove.
• Git. Objects are addressed by the hash of their content.

When not to use a hash table

• You need ordering. "Give me the smallest key", "all keys between A and B" and "the next key after X" are not hash operations. Use a sorted structure (a balanced tree, or a sorted array with binary search).
• The dataset is tiny. For a handful of entries, a linear scan of an array is as fast and simpler.
• Keys have no stable equality. Floating-point keys, or mutable objects that change after insertion, will silently lose entries.
• Memory is tight. Buckets, load-factor slack and per-entry overhead cost more than a packed array.
• You need worst-case guarantees. Real-time systems that cannot tolerate a resize pause or a pathological collision chain often prefer trees.

What interviewers ask

• "How does a hash table work?" Hash function to an index, collision handling, resizing. Say all three.
• "What happens on a collision, and how do you handle it?" Separate chaining or open addressing, with the trade-offs.
• "Why is it O(1) and when is it not?" Average case with a low load factor and a good hash. Worst case O(n).
• "What is the load factor and why resize?" To keep chains short, at the cost of an O(n) rehash that amortises away.
• "Map versus Object?" Key types, ordering, inherited keys, size, performance with frequent deletes.
• "Two sum, first duplicate, group anagrams, longest consecutive sequence." The four patterns above.
• "Design an LRU cache." A hash map plus a doubly linked list, and why neither alone is enough.

The mistake to avoid

Choosing a hash function that ignores order (summing character codes), or using a mutable object as a key and then changing it. In the first case, anagrams and any permutation of the same characters all collide, so your "O(1)" table quietly becomes a set of long chains. In the second, the entry is stored under the old hash and the new value can never find it again. Keys should be immutable and the hash should depend on every part of them, in order.

Whenever you catch yourself writing a nested loop to compare items with each other, ask whether a hash table can remember the answer instead. Turning "search the whole list" into "look it up by key" is the single most common optimisation in interview problems, and it is a hash table every time.