Hash Maps and Sets for Coding Interviews

Operations and what they cost

What each language actually documents differs, and it is worth saying the right thing for yours:

The Python, JavaScript and Java pages have the full lists.

How a hash map works

A hash map is an array of buckets. To store a key, you hash it to a number, take that number modulo the array's length, and put the entry in that bucket. To find a key, you do the same and look there. That is why the cost does not depend on how many entries there are, as long as buckets stay short.

Two keys can land in the same bucket, which is a collision. Chaining keeps a small list in each bucket and walks it. Open addressing tries other slots in the table in a fixed order. Either way, if every key lands together, a lookup walks all of them, which is the O(n) worst case.

To keep buckets short, the table grows. The load factor is entries divided by buckets, and past a limit the table is rebuilt larger and every key rehashed. Java's HashMap defaults to a load factor of .75 and grows to about twice the buckets, and calls that default a good tradeoff between time and space. CPython's dict is described as a resizable hash table. A single insert can therefore be expensive, which is what amortized means here.

What can be a key

The rule behind every language's answer is that equal keys must hash the same, and a key's hash must not change while it is in the map.

• Python: a key must be hashable. Most immutable built-ins are, and lists and dicts are not. A tuple is hashable only if everything in it is, so use a tuple or a string for a composite key.
• JavaScript: a Map accepts any value and compares keys with SameValueZero, so two different objects with the same contents are two keys. A plain object's keys must be strings or symbols, so numbers are converted.
• Java: the hashCode contract says that if two objects are equal, their hashCode must match. Override equals without hashCode and lookups quietly fail.

When to reach for it

• A brute force does a second loop to look something up. Replace the loop with a lookup.
• You are counting, grouping or deduplicating.
• You need to remember what you have already seen. If you only need yes or no, a set is enough; if you need to store something with it, use a map.
• You need a fast index over something else, such as a map from a key to a node in a list, as an LRU cache does.
• Not when you need order or ranges: there, consider a sorted structure.

Hash map interview questions

These are the conceptual questions that follow a hash map answer, and what a good reply covers. For coding questions, see the arrays and hashing pattern.

How it looks in Python, JavaScript and Java

In practice you use the built-in, so the first three do the same job in each language. The last is the from-scratch version an interviewer might ask for.

def word_counts(words):
    counts = {}
    for w in words:
        counts[w] = counts.get(w, 0) + 1
    return counts

function wordCounts(words) {
  const counts = new Map();
  for (const w of words) counts.set(w, (counts.get(w) ?? 0) + 1);
  return counts;
}

import java.util.*;

class Counting {
    static Map<String, Integer> wordCounts(List<String> words) {
        Map<String, Integer> counts = new HashMap<>();
        for (String w : words) counts.merge(w, 1, Integer::sum);
        return counts;
    }
}

class ChainedMap:
    """A hash map from scratch: an array of buckets, chaining on collision."""

    def __init__(self):
        self.buckets = [[] for _ in range(8)]
        self.size = 0

    def _bucket(self, key):
        return self.buckets[hash(key) % len(self.buckets)]

    def get(self, key, default=None):
        for k, v in self._bucket(key):
            if k == key:
                return v
        return default

    def put(self, key, value):
        bucket = self._bucket(key)
        for i, (k, _) in enumerate(bucket):
            if k == key:
                bucket[i] = (key, value)    # same key: replace
                return
        bucket.append((key, value))
        self.size += 1
        if self.size > len(self.buckets) * 3 // 4:
            self._grow()                    # keep the load factor down

    def _grow(self):
        entries = [pair for bucket in self.buckets for pair in bucket]
        self.buckets = [[] for _ in range(len(self.buckets) * 2)]
        for k, v in entries:
            self._bucket(k).append((k, v))  # the index depends on the length

How to explain the choice out loud

Common mistakes

• Saying O(1) with no qualifier, then having no answer when asked about the worst case.
• Using a mutable key, such as a Python list, or a Java key whose fields change after it goes in.
• Overriding equals in Java without hashCode, so equal objects land in different buckets.
• Relying on iteration order. It is not the same across languages, so check what yours documents before you depend on it.
• Reaching for a map when a set is enough, or a set when you also need the count.

Where to go next

• Pattern: arrays and hashing.
• Worked problems: Match a Product Variant from Selected Options, Deduplicate a Member's Skills and Select the Top Unseen Feed Posts.
• All the figures in one place: the Big O cheat sheet.
• Practice saying it: a coding mock interview.