Hash map — trade space for time

A hash map turns "search for X" into "ask for X." Instead of scanning the array to find a value (O(n)), you store what you've seen in a table that jumps straight to the slot via a hash of the key — so lookups are O(1) on average. You spend memory to buy time; that's the whole trade. Two Sum is the canonical move: instead of checking every pair for a + b = k, walk the array once and ask "have I already seen k - current?" — and O(n²) collapses to O(n).

The on-ramp: why trade memory for instant lookup

Picture an unsorted array. To answer "is the value 42 in here?" you have no choice but to walk it element by element — that's a linear scan, O(n), where the work grows in lockstep with the size of the data. A hash map fixes this by paying for a second copy of the information, arranged so the answer is one jump away. The principle is general: you can almost always turn a repeated search into a single lookup by building a table first. The table costs extra memory (O(n) of it), but every future "have I seen this?" or "what's the value for this key?" then costs O(1) instead of O(n). When a problem makes you ask the same membership or lookup question over and over inside a loop, that repeated O(n) search is exactly the cost a hash map erases.

Every term, defined

• Hash map / dictionary / map — the same idea under three names. A structure holding key → value pairs with average O(1) insert, lookup, and delete. Python calls it dict; JavaScript has both Map and plain objects; Java calls it HashMap.
• Hash function — a deterministic bit of math that takes a key and produces a fixed-size integer (the "hash"). Deterministic means the same key always yields the same number, so you can find your way back to the same slot. A good hash spreads different keys evenly across slots.
• Bucket (slot) — one cell in the underlying array of storage. The hash of a key, reduced into the array's size range, picks which bucket the pair lives in.
• Collision — when two different keys hash to the same bucket. Maps must handle this; the common fix is chaining (each bucket holds a small list of pairs, and on lookup you scan that short list comparing keys).
• Load factor — the ratio entries / buckets. As it climbs, collisions get more likely and the chains get longer. When it crosses a threshold the map resizes (allocates more buckets and re-hashes everything), keeping chains short.
• Amortized O(1) — "averaged over many operations, O(1)." Most inserts are instant; the occasional resize is O(n), but it happens so rarely (only when the map roughly doubles) that the cost spread across all inserts averages back down to a constant. So calling inserts O(1) is honest even though a single one might be slow.
• Worst case O(n) — if a hash function is poor (or an adversary crafts keys), many keys can pile into one bucket. Then that bucket's chain is long, and a lookup must scan it linearly — degrading to O(n). Real-world hash functions make this vanishingly rare, which is why we quote O(1) for interviews while knowing the asterisk.
• Hashable / immutable keys — a key must be hashable: it must produce a stable hash that never changes while it sits in the map. Immutable values (numbers, strings, tuples in Python) qualify. Mutable ones (lists, dicts, sets) do not — if their contents changed, their hash would change and the map could no longer find them.
• Set vs map — a set is a hash map that stores only keys, no values; it answers "is X present?" in O(1). A map stores keys and an associated value. Use a set when you only care about membership; use a map when you also need to retrieve something attached to the key (like Two Sum needing the index).

How a hash map works under the hood

Three steps turn a key into a stored value. (1) Hash: feed the key to the hash function to get a big integer. (2) Bucket: reduce that integer into the array's size — typically hash % number_of_buckets — to pick which bucket holds this pair. (3) Handle collisions: if another key already lives in that bucket, both are kept in the bucket's short chain; on lookup, the map walks that chain comparing keys for true equality (the hash got you to the right bucket; equality confirms the exact key). Because a healthy map keeps chains tiny (low load factor), step 3 stays effectively constant — giving the average O(1) you rely on. The price for all this is the bucket array itself, which is why the structure costs O(n) memory.

Recognition signals and pitfalls, expanded

Reach for a hash map the moment a brute-force solution is doing a repeated search inside a loop — "for each element, look through the rest" is the tell-tale O(n²) smell, and a map usually collapses the inner search to O(1). Concretely, the trigger phrases above all reduce to the same shape: you need fast membership ("have I seen this?"), fast counting ("how many of each?"), or fast retrieval-by-key ("what's attached to this?"). If any of those repeats, build a table.

• Mutable keys. Don't use a list (or anything you'll later mutate) as a key — Python raises TypeError: unhashable type. Convert to an immutable form first: tuple(my_list), or for a multiset of letters, a sorted string or a frozen count.
• Relying on order. A hash map's iteration order is an implementation detail, not a guarantee you should lean on for logic. (Python 3.7+ dicts happen to preserve insertion order, but they are not sorted — if you need keys in sorted order, sort them explicitly.) Never assume the map hands keys back in a meaningful order.
• Self-pairing. In complement problems, insert the current element after checking for its partner, so it can't match itself using the same index twice.
• Missing-key handling. Reading an absent key throws in some setups; use dict.get(k, default) or collections.defaultdict for counting/grouping so you don't special-case the first occurrence.

def two_sum(nums, target):
    seen = {}                          # value -> index
    for i, v in enumerate(nums):
        need = target - v
        if need in seen:
            return [seen[need], i]
        seen[v] = i
    return []

function twoSum(nums: number[], target: number): number[] {
  const seen = new Map<number, number>();
  for (let i = 0; i < nums.length; i++) {
    const need = target - nums[i];
    if (seen.has(need)) return [seen.get(need)!, i];
    seen.set(nums[i], i);
  }
  return [];
}

The three sub-patterns

Most hash-map interview problems are one of three small recipes. Learn these and you'll recognize them on sight.

1 · Seen set — membership in one pass

When you only need to know "have I encountered this before?", store keys in a set (no values needed) and check membership before inserting. Detecting a first duplicate in an array:

def first_duplicate(nums):
    seen = set()
    for v in nums:
        if v in seen:        # O(1) membership test
            return v
        seen.add(v)
    return None

On [4, 1, 4, 2]: add 4, add 1, see 4 already in the set → return 4. One pass, O(n) time, O(n) space.

2 · Frequency count — tally each key

When you need "how many of each?", map each item to a running count. This powers anagram checks, "most common element," and majority-vote problems. collections.Counter does it in one line, but the manual version shows the shape:

def counts(items):
    freq = {}
    for x in items:
        freq[x] = freq.get(x, 0) + 1   # default 0 on first sight
    return freq

# counts("banana") -> {'b':1, 'a':3, 'n':2}
# Two strings are anagrams iff counts(s) == counts(t)

3 · Group by key — bucket items under a shared signature

When you need to collect items that share some property, derive a canonical key (one value all members of a group agree on) and append each item to that key's list. Grouping anagrams uses the sorted letters as the canonical key — "eat", "tea", "ate" all sort to "aet":

from collections import defaultdict

def group_anagrams(words):
    groups = defaultdict(list)
    for w in words:
        key = "".join(sorted(w))   # canonical key: sorted letters
        groups[key].append(w)
    return list(groups.values())

# ["eat","tea","tan","ate"] -> [["eat","tea","ate"], ["tan"]]

The trick in every group-by problem is choosing the canonical key well: it must be identical for everything that belongs together and hashable. Sorted strings, letter-count tuples, and normalized forms are common choices.

Now write it yourself — the editor below runs your JavaScript against real test cases in your browser, instantly. Same one-pass hash-map idea; the language is different but the pattern is identical.