Hash Maps and Sets

Decide what survives the scan

Suppose you scan [3, 3] from left to right, looking for two values whose sum is six. After reading the first 3, what must survive?

Remembering only membership by value is enough to answer yes or no. It is not enough to return the earlier index. Counting occurrences would preserve more information than this prompt needs. Storing the entire prefix would preserve far too much.

The useful memory is exact:

value -> one usable prior index

When the second 3 arrives, the algorithm asks for its complement, finds the stored index, and returns the pair. That small choice—what to retain after an item has passed—is the center of hash-map reasoning.

An array gives you facts by position. A hash table gives you facts by a key you design. The container is rarely the difficult part. The work is deciding:

• which inputs should count as the same key;
• whether the value is membership, a count, an index, a collection, or a computed result;
• when an entry becomes valid, stale, or safe to remove; and
• whether the saved work is worth the memory and key-construction cost.

Before writing code, finish this sentence:

I need to remember ___ by ___ so that later I can ___.

If any blank is vague, choosing dict, Map, HashMap, or set will only hide the missing decision.

Hashing does not define equality for you

A hash table uses a key’s hash to find a likely bucket and an equality rule to identify the entry within that bucket. Different keys may collide in one bucket; a correct implementation keeps them distinct by comparing keys.

This mechanism explains several obligations that otherwise look like language quirks. A key must not change in a way that changes its hash or equality while it is stored. A composite key should use an unambiguous structured form, such as a tuple, rather than a delimiter that might also occur in the data. A key derived from a long string or object still costs time to construct and compare.

Lookup, insertion, and deletion are ordinarily described as expected O(1). That is a statement about the table under its runtime’s hashing assumptions, not free work under every input. The full cost includes building and hashing the key, resolving collisions, and occasionally resizing the table. If the contract requires deterministic worst-case lookup, an ordered tree map may be the more honest O(log n) choice. Collision behavior deserves similar care when inputs are adversarial or security-sensitive.

Use the weakest fact that can answer the question

A set stores the smallest common fact: a key is present. That is enough for deduplication, intersections, visited states, and guards against repeated work. It is also deliberately lossy. A set does not preserve how many copies appeared, where they appeared, or which copy should win.

Consider the longest run of consecutive integer values in an unsorted input:

def longest_consecutive(nums):
    values = set(nums)
    best = 0

    for value in values:
        if value - 1 in values:
            continue

        length = 1
        while value + length in values:
            length += 1
        best = max(best, length)

    return best

The set removes duplicates because multiplicity cannot change the length of a run. More importantly, the predecessor check makes each run start only at its smallest value. Although the inner loop can take many steps for one start, each value belongs to one counted run, so the total work is expected O(n) and the additional space is O(n).

Change the output contract and the stored fact changes with it. “Does this value repeat?” needs membership. “Where did it first appear?” needs a map to an index. “How many times did it appear?” needs a map to a count. “Return all of its positions” needs a map to a collection of indexes. Reaching for a set before settling the output is a common way to discard the answer.

Visited sets have a timing decision as well. In a graph search, mark a state when scheduling it, not after processing it, if the worklist must contain no duplicates. The key must represent the whole state: (row, column) may be enough in one grid, while (row, column, keys_held) may be necessary in another.

Counts make multiplicity part of the invariant

A frequency map represents a multiset. The value answers how many copies have appeared, remain required, or are currently active.

def is_anagram(left, right):
    if len(left) != len(right):
        return False

    remaining = {}
    for char in left:
        remaining[char] = remaining.get(char, 0) + 1

    for char in right:
        if char not in remaining:
            return False
        remaining[char] -= 1
        if remaining[char] == 0:
            del remaining[char]

    return not remaining

A set would make "ab" and "aab" look alike. The map instead states an invariant: remaining contains exactly the characters from left that the scanned prefix of right has not consumed.

Deleting zero-count entries is meaningful here because emptiness represents completion. The same deletion matters in a sliding window when the number of stored keys is meant to equal the number of active distinct values. In other problems, retaining zeroes is harmless. The representation must agree with the statement you plan to make about it.

Alphabet assumptions belong in that statement too. A fixed 26-element count array can be excellent when the prompt grants lowercase English letters. It is not a general replacement for a map when the input may contain arbitrary Unicode text or when normalization changes what counts as equal.

Complements reverse the direction of search

A nested search asks, for every item, whether a suitable partner exists somewhere else. A complement map asks a narrower question: has an earlier item already supplied the exact fact this item needs?

def two_sum(nums, target):
    index_by_value = {}

    for index, value in enumerate(nums):
        needed = target - value
        if needed in index_by_value:
            return [index_by_value[needed], index]
        index_by_value[value] = index

    return None

Checking before insertion prevents one element from pairing with itself. The input [3, 3] with target 6 still succeeds because the second occurrence finds the first. The map stores indexes rather than booleans because the output asks for positions.

If the prompt asks for the number of index pairs, one prior position is no longer enough. The value must be a count:

answer = 0
count_by_value = empty map

for value in data:
    answer += count_by_value.get(target - value, 0)
    count_by_value[value] += 1

The same reasoning explains prefix-sum counting. At running sum s, every earlier prefix equal to s - k begins a contiguous range summing to k. Membership would answer whether one such range exists; a prefix-to-count map answers how many exist. The initial entry {0: 1} represents the empty prefix and allows a range to begin at index zero.

This is the useful transfer: complements need not be values that add to a target. They can be prior prefixes, missing states, or any earlier fact that completes a relation you can write precisely.

A canonical key is an executable definition of “same”

Grouping and deduplication begin with an equivalence relation. Two records belong together under which exact rule? Once that rule is clear, a canonical key gives every equivalent input the same immutable representation.

For lowercase English words, a 26-count tuple is a canonical representation of an anagram class:

def group_anagrams(words):
    groups = {}

    for word in words:
        counts = [0] * 26
        for char in word:
            counts[ord(char) - ord("a")] += 1

        key = tuple(counts)
        groups.setdefault(key, []).append(word)

    return list(groups.values())

The list becomes a tuple because the key must be immutable. The 26 positions are justified only by the input contract. With a broader alphabet, sorting the characters gives a simpler key at O(m log m) per word of length m, while a sparse character-count representation avoids pretending the alphabet is small.

Canonicalization is a policy, not generic cleanup. A prompt may define email identity by ignoring dots and a plus suffix in the local part while comparing domains case-insensitively. That permits those exact transformations; it does not permit lowercasing the local part unless the rule says so. File paths, telephone numbers, Unicode strings, timestamps, and user identifiers carry similar domain-specific boundaries.

Over-normalization merges distinct inputs. Under-normalization leaves equivalent inputs apart. A good diagnostic pair differs in one feature whose meaning is in doubt: case, punctuation, time zone, field order, Unicode form, or a supposedly irrelevant record attribute. The expected grouping forces the equality rule into the open.

Composite keys should be structured. (user_id, hour_bucket) cannot be confused by the contents of either field; a string such as user_id + ":" + hour_bucket can be, unless escaping rules are part of the contract. Hashing a mutable object by identity is also different from hashing its current value. Choose deliberately.

An index buys repeated lookup

An index is a map built because the workload will ask the same kind of question many times. If n records receive q lookups by id, scanning for every query costs O(nq). Building id -> record once costs O(n) expected time and space, followed by expected O(1) per lookup.

That exchange is useful only after defining duplicates and change. Does a duplicate id make the input invalid, should the first or latest record win, or should one key map to a list? If records can change, what updates or invalidates the index? A fast stale answer is still wrong.

Parent-child reconstruction shows why this is more than a convenience. Given records with id and parent_id, first build node_by_id; then make a second pass that attaches each node to its parent. Without the index, repeated parent search becomes nested scanning. With it, missing parents, duplicate ids, and multiple roots become visible input-contract decisions rather than accidental behavior.

Do not build an index merely because you can. For one query over small data, a scan may be clearer and use less memory. If the required output is already sorted, sorting once may serve both lookup and presentation. The number and shape of later queries decide whether preprocessing earns its cost.

A cache key must describe the whole subproblem

Memoization is another index, but its values are computed answers rather than input records. It works only when equal keys truly mean equal subproblems.

def word_break(text, words):
    dictionary = set(words)
    memo = {}

    def can_break(start):
        if start == len(text):
            return True
        if start in memo:
            return memo[start]

        for end in range(start + 1, len(text) + 1):
            if text[start:end] in dictionary and can_break(end):
                memo[start] = True
                return True

        memo[start] = False
        return False

    return can_break(0)

Here start is a complete key because text and dictionary remain fixed during the search. If a remaining budget, previous choice, or resource state could change the answer, that value would also belong in the key. If the computation reads time, random state, or mutable globals, repeated keys may not mean repeated answers at all.

Memoization trades recomputation for memory proportional to the reachable state space. In this Python version, substring creation and hashing also contribute to the running time; counting only the number of memo entries would understate the work. For a long-lived production cache, the chapter’s small map acquires further obligations: bounded growth, expiration, invalidation, and safe handling of concurrent updates.

Test the boundary of the remembered fact

Hash-based bugs reveal themselves where the chosen representation stops distinguishing cases. A few tests should attack that boundary directly:

• Give a membership solution duplicates when counts or positions might matter.
• Use [3, 3] against complement code to expose same-index reuse.
• Let an active count fall to zero and then rise again.
• Reach the same recursive index with different remaining state.
• Supply two raw values that should canonicalize together, and two tempting values that must remain distinct.
• Repeat an index key and decide whether overwrite, rejection, or collection is the contract.
• Use a large or adversarial key to challenge an unqualified O(1) claim.

The tests follow from the stored fact. They are more diagnostic than a generic collection of empty, normal, and large inputs because each one asks whether the representation has preserved exactly the information the algorithm later uses.

Know when memory is the wrong exchange

Hash structures often replace repeated work with retained state: nested search becomes a seen map, repeated window counts become one maintained frequency map, many scans become an index, and repeated recursion becomes a memo table. The attractive time bound can obscure the cost introduced.

Prefer a different approach when that cost dominates. Sorting may offer deterministic O(n log n) behavior, ordered output, and sometimes little additional memory when mutation is allowed. A balanced tree preserves ordered traversal and worst-case O(log n) lookup. A direct scan may be best for one small query. A compact bitset or fixed array may beat a general hash table when the key domain is small and known. An external or disk-backed index may be necessary when retained state does not fit in memory.

Iteration order deserves an explicit decision too. Even in a language that preserves insertion order, relying on that property is correct only when it matches the output contract. Otherwise preserve order separately or sort the result. The fact that a runtime happens to emit a pleasing order is not an algorithm.

Practice by changing the contract

Take one familiar problem and alter only the information the output requires. For two sum, compare existence, one index pair, all unique value pairs, the number of index pairs, and a stream in which old values expire. The surface problem barely changes, but the stored value and its lifetime do.

Then change equality. Group lowercase anagrams with a count tuple; broaden the alphabet; require original group order; process words too large to sort cheaply. Each change should force you to defend a different key or output structure.

Finally, change the workload. Reconstruct parents once, then accept record updates. Memoize word break, then add a limited word budget. Deduplicate a finite list, then deduplicate an unbounded stream. If the old map survives unchanged, explain why; if it does not, name the missing state, invalidation rule, or memory bound before changing the code.

Hash maps and sets are useful because they let an algorithm carry chosen facts forward. Their danger is the same: the choice can silently erase multiplicity, position, order, identity, or state. Name the fact, key, equality rule, and lifetime before choosing the container. The next chapter keeps that discipline but changes the question from what should be remembered to what must leave first—by reference, stack order, queue order, or deque boundary.

Related reading

• Chapter 31: Complexity and Constraint Analysis
• Chapter 33: Correctness Before Cleverness
• Chapter 39: Arrays and Strings
• Chapter 41: Linked Structures, Stacks, Queues, and Deques