Hash Maps and Sets: The Core Idea

Think of the coat check at a theatre. You hand over your coat and get ticket 47. At the end of the night the attendant does not walk along the rails looking at every coat. They go straight to hook 47. The ticket number is the address of the coat.

A hash map works the same way. It turns a key into a slot number, so finding something takes one step, however many things are stored. That single property removes a whole class of slow code: any loop that re-scans earlier data to answer "is it here, and where?"

Put a number on it. Does [3, 8, 1, 8] contain a repeat? Without memory, you compare each value with every value before it: 0 + 1 + 2 + 3 = 6 comparisons for 4 values, and about n²/2 for n values. With a notebook of the values you have seen, each value needs one look into the notebook: 4 looks for 4 values. At n = 100,000 that is the difference between 5 billion comparisons and 100,000 lookups.

How to recognise it

Four kinds of question almost always want a hash map or a set.

1. "Have I seen this before?" Duplicates, repeats, visited nodes. Anywhere you would otherwise re-scan the elements to your left.
2. "How many of each?" The most frequent value, whether two strings use the same letters, which item appears an odd number of times.
3. "Where was it, or how far back?" Two Sum, the nearest earlier repeat, the last position of a character.
4. "Which of these belong together?" Group the anagrams, bucket values by remainder, group strings with the same shape.

The strongest single signal is structural, not verbal. If your brute force has a nested loop and the inner loop is searching for one specific thing, a hash map usually removes the inner loop. The Two Pointers section removes nested loops that compare pairs of elements; hash maps remove nested loops that look things up.

The constraints confirm it. When n can reach 10⁵, an O(n²) solution does about 5 × 10⁹ steps, which is far too slow in any language. The problem setter expects O(n) or O(n log n). If the input is unsorted, and sorting would destroy what you must return (such as original positions), a hash map is usually the O(n) route.

It is the wrong tool in three cases. If the array is already sorted and you need O(1) extra space, two pointers do the job with no memory. If the question is about the sum or count of a contiguous range, that is the Prefix Sums section (which does use a hash map, but as a helper). And if the keys come from a small, dense range — 26 lowercase letters, or values from 1 to n — a plain array indexed by the value is faster and smaller than any hash map.

How it works

Here is the mechanism on real values. Suppose the table has 8 buckets and, to keep the arithmetic simple, the hash of a short string is the sum of its character codes. Insert "cat", "dog" and "act".

To look up "dog", compute its hash (three additions), take it mod 8, go to bucket 2 and read what is there. Nothing was searched. The key computes its own address.

Bucket 0 now holds two keys, so the table must still compare keys inside a bucket. One common fix is chaining: each bucket holds a short list, and a lookup compares keys only within that list. Java's HashMap works this way. Python's dict uses open addressing instead — on a collision it probes other slots in a fixed order — but the cost story is the same.

A good hash function spreads keys evenly, so each bucket holds about one key and a lookup costs a small, constant amount of work. That is why we say average O(1). But nothing prevents every key from landing in one bucket. Then the table behaves like a list and each lookup costs O(n). That is the worst case.

Two things keep the worst case rare in practice. Resizing: when the table gets about two-thirds full (CPython's rule), the implementation allocates a bigger array and re-inserts everything. That one step is O(n), but it happens so rarely that the cost averaged over all inserts stays O(1) — this is called amortised O(1). Randomisation: modern runtimes add a random per-process seed to string hashing, so an attacker cannot prepare thousands of keys that all collide.

One cost people forget: hashing a string of length L means reading all L characters. So each operation on a string key is O(L), not O(1). On problems with long keys, say so — interviewers notice.

The four shapes

Nearly every hash-map problem is one of four shapes. Naming the shape decides the two things that are the solution: what the key is, and what the value is.

The grouping map is the one that needs design thought, because choosing the key is the problem. Two words are anagrams exactly when their sorted letters match, so the sorted letters are a valid key. A key that puts two different groups together gives a wrong answer. A key that splits one group into two also gives a wrong answer.

Inside other patterns

At medium and hard level, the hash map often works as a helper inside another pattern. Its job is always the same: answer a question about earlier positions in one step, so the scan never goes backwards.

• With prefix sums. Keep a running total and a map from "total seen so far" to "how many times". Counting subarrays that sum to k becomes one lookup per element. The Prefix Sums section owns this family.
• With a sliding window. Keep a map of the characters inside the window (their counts, or their last positions). The window can then be repaired in O(1) instead of rebuilt. The Sliding Windows section owns this family.

The templates

Four short templates cover the four shapes. Learn them as shapes, not as solutions to one problem.

Seen-set. Is any value repeated?

1def contains_duplicate(numbers: list[int]) -> bool:2    """Return True if any value appears at least twice."""3    seen: set[int] = set()4    for value in numbers:5        if value in seen:          # check first...6            return True7        seen.add(value)            # ...then record8    return False

The set holds exactly the values to the left of the current one. The order of the two steps matters: check, then add. If you add first, every value finds itself.

Frequency counter. Do two strings use exactly the same letters?

1def is_anagram(first: str, second: str) -> bool:2    """Return True if the two strings use exactly the same letters."""3    if len(first) != len(second):4        return False5    counts: dict[str, int] = {}6    for character in first:7        counts[character] = counts.get(character, 0) + 18    for character in second:9        if counts.get(character, 0) == 0:10            return False                 # second has a letter first ran out of11        counts[character] -= 112        if counts[character] == 0:13            del counts[character]        # keep only unmatched letters14    return not counts

counts.get(character, 0) reads a count without inserting anything. Deleting a key when its count reaches zero means "all counts are zero" becomes "the map is empty", which is an O(1) check. In real code, collections.Counter(first) == Counter(second) does the same in one line — but write it by hand once, so you can produce it in any language.

Index map. The Two Sum shape: for each value, is its partner already stored, and where?

1def two_sum(numbers: list[int], target: int) -> list[int]:2    """Return indices [i, j] with numbers[i] + numbers[j] == target."""3    index_of: dict[int, int] = {}          # value -> index where we saw it4    for index, value in enumerate(numbers):5        needed = target - value6        if needed in index_of:             # check BEFORE inserting7            return [index_of[needed], index]8        index_of[value] = index9    return []

Grouping map. Compute a key from each item and collect items that share it.

1from collections import defaultdict23def group_by_sorted_letters(words: list[str]) -> list[list[str]]:4    """Group words whose letters are the same, in any order."""5    groups: defaultdict[str, list[str]] = defaultdict(list)6    for word in words:7        groups["".join(sorted(word))].append(word)   # the derived key8    return list(groups.values())

defaultdict(list) creates an empty list the first time a key is used, so there is no "is this key new?" branch.

A few library details worth knowing. Python's dict keeps insertion order (guaranteed since Python 3.7); set has no order guarantee at all. Java's HashMap has no order; LinkedHashMap keeps insertion order. C++'s unordered_map is the hash map, while map is a balanced tree with O(log n) operations and sorted iteration. If you need sorted order, a hash map is the wrong container in every one of these languages.

Complexity

Every template above does one pass and one or two O(1) map operations per element, so each is O(n) time on average. The map or set can hold up to n entries, so each is O(n) extra space.

There are two refinements to quote. When the keys come from a fixed alphabet, the map holds at most that many keys: the anagram counter is O(1) space for 26 letters, not O(n). And when keys are strings of length L, multiply by L: grouping n words costs O(n · L log L) with sorted keys, because sorting each word is the expensive part.

The honest worst case is O(n) per operation, which turns an O(n) algorithm into O(n²). If the interviewer asks, say: "average O(n), worst case O(n²) if every key collides. That needs an adversarial input or a bad hash function. If I had to guarantee the bound, a balanced search tree gives O(log n) per operation with no bad case, at the cost of being slower on average."

Where it goes wrong

1. Inserting before checking. In the seen-set, adding a value and then asking "is it in the set?" is always true. In the index map, it returns [i, i] — the element paired with itself. Both are silent wrong answers, not crashes.

2. Mutable keys. A key must be hashable, which in practice means immutable. In Python, groups[sorted(word)] raises TypeError: unhashable type: 'list'; use tuple(sorted(word)) or "".join(sorted(word)). In languages that allow mutable keys it is worse: change an object after using it as a key and its hash changes, so the entry sits in a bucket no lookup will ever reach. No error is raised.

3. Trusting iteration order. Sets have no order guarantee. Python dicts keep insertion order, but insertion order is not sorted order. Code that relies on either passes your test and fails the grader's.

4. Memory, when an array would do. A Python dict entry costs roughly 100 bytes once the key and value objects are counted. Ten million distinct integer keys is about a gigabyte. If the keys are a dense, bounded range (26 letters, values 1 to n), use a plain array indexed by the value. If the keys are every substring of a string, there are about n²/2 of them — 50 million for a 10,000-character string — and the intended solution is almost certainly a window or a trie.

5. The adversarial worst case. Deliberately colliding keys have been used to stall real web servers. That is why runtimes randomise string hashes. You rarely need to defend against it in an interview; you do need to be able to explain it.