The Four Hash Patterns

One cabinet, four daily chores

The mailroom clerk's cabinet isn't just for filing and finding packages — the same setup solves a handful of everyday chores that show up constantly in problems. Nearly every hash-table problem is really just the clerk running one of four routines. Naming them turns "somehow use a dict" into a decision you can make in ten seconds — and the five problems ahead are one or two of these verbs each.

Maps vs. Sets: the same cabinet, minus the messages

Sometimes you don't care what's inside an envelope — you just want to know who has come through the mailroom. For that, the clerk uses the exact same cabinet, the exact same word-trick, the exact same hooks — they just hang simple name tags instead of full packages. That's a hash set: it stores only keys, membership without payload, built from the identical chaining-or-probing machinery the last two lessons covered. Any chore below that says "map" but only ever stores a placeholder value really wants a set instead; Python set / JS Set are that exact structure with entries of just key. The first chore is the purest example.

1. Seen — membership

Chore one: the guest list. You want to know if you've already seen a particular visitor today. Instead of walking around asking everyone, the clerk writes a visitor's name on a tag the moment they arrive and files it in the cabinet. Next time that name comes up, the clerk runs the word-trick, checks that slot, and instantly knows whether they've been here before — no asking around required.

The set as a memory: have I encountered this before?

def has_duplicate(nums: list[int]) -> bool:
    seen = set()
    for x in nums:
        if x in seen:
            return True
        seen.add(x)
    return False

The general shape: a scan that would need to re-search its own past instead records its past. O(n²) re-scanning becomes O(n) remembering.

2. Count — frequency

Chore two: the ballot tally. You want to count how many votes each candidate received. The clerk files a single card for each candidate in their designated slot; every time a new vote comes in, they jump straight to that slot and add a tick mark.

The map as a tally: key → how many times. Module 5's 26-slot count array, generalized to any hashable key with no alphabet contract:

from collections import Counter, defaultdict

counts = Counter(words)              # idiomatic
counts2: dict[str, int] = defaultdict(int)
for w in words:
    counts2[w] += 1                  # explicit

3. Index — value → location

Chore three: the coat check. Normally a coat-check ticket tells you where your coat is by its number. But imagine the reverse problem: someone loses their ticket and asks "where's my yellow coat?" Instead of walking past hundreds of hanging coats, the clerk keeps a card filed under "Yellow Coat" that lists the exact hanger number it's on.

The map as a reverse array: value → where it lives. An array answers index → value in O(1); the index map answers the opposite direction in O(1), at O(n) build cost. Two Sum runs on this verb, with a twist you'll find yourself.

4. Group — key → bucket of members

Chore four: the sorting office. You have a pile of packages and want to group them by destination city. The clerk runs the word-trick on the city name ("Boston") to find a slot, and throws every package bound for Boston onto that slot's hook.

The map as a sorting office: compute a canonical key for each item; items sharing a key land in the same list.

from collections import defaultdict

def group_by_length(words: list[str]) -> list[list[str]]:
    groups: dict[int, list[str]] = defaultdict(list)
    for w in words:
        groups[len(w)].append(w)     # canonical key: length
    return list(groups.values())

The entire art is choosing the key so that "same key" means exactly "belongs together." Group Anagrams will make you design one.

Choosing in the wild

Two cautions. First, keys must be hashable/immutable — the previous lesson covered why (a changed key computes a different slot and becomes unreachable) and the specific JS object-reference trap that bites the Group pattern hardest: Map compares object keys by reference, so grouping by structural equality needs a canonical string key, not the raw object. Second, the mailroom cabinet is unbeatable for "find this one package fast," but useless for "give me every package in alphabetical order" — for that you'd need a completely different kind of organizer, one that keeps items on a branching, ordered shelf instead of unordered slots. The hash map's O(1) is average, unordered — if you need sorted keys or range queries, you want a tree (Module 18), and knowing the difference is part of knowing hash tables.