Hashing, Sets & Recursion

1 · The hashing idea basic

Picture the coat check at a big theatre. A thousand people hand over coats; at the end of the night everyone needs their own coat back, fast. The slow way is to pile them up and search — pull out coat after coat until you find the right one (that's a linear scan, O(n), and the queue would stretch out the door). The clever way is the numbered ticket: your coat goes on peg 237, your stub says 237, and the attendant walks straight to peg 237. No searching. That numbered-ticket trick is exactly what hashing does — and it's why looking a value up in a Python dict feels instant no matter how much you've stored.

Here's the tension it resolves. Back in D1 you learned that jumping to array[i] is O(1) — free at any size — but only if you already know the index i. Real keys aren't indices: you want to look things up by a tool name like "weather", a document ID, a word. So the whole problem becomes: how do I turn an arbitrary key into an array index? That translator is the hash function. It takes a key — a string, a number, a tuple — and grinds it into an integer. Then you take that integer mod the array size (hash(key) % size) to squeeze it into a valid slot number. Store the value at that slot; to fetch it later, hash the same key again, get the same slot, walk straight there. Because both the hash and the array jump are constant-time, the lookup is O(1) on average — no scanning, ever.

The one place beginners get the mental model wrong: they imagine the hash function "remembers" where it put things, like a little database. It remembers nothing. It's a pure, stateless calculation — feed it the same key and it always spits out the same number, which is precisely why you can find your value again: you don't look it up, you recompute its address. That also explains a rule that otherwise seems arbitrary — keys must be immutable. If a key could change after you stored it, re-hashing it later would compute a different slot, and your value would be stranded at the old address, unfindable. Hold that thought; the lab and the warning box right below make it concrete, and it's the seed of every collision headache in §3.

pythonhash("checkout-api")      # some big int (varies per run for strings)
hash(42)                 # 42 — small ints hash to themselves
hash((1, 2))             # tuples are hashable (immutable)
# hash([1, 2])          -> TypeError: unhashable type: 'list'  (mutable!)

# slot = hash(key) % table_size  -> where to store/find the value
size = 8
for key in ["a", "b", "c"]:
    print(key, "-> slot", hash(key) % size)

2 · A hash table from scratch (chaining) intermediate → advanced

Reading about hashing and building one are different experiences — and the second is where it finally clicks. You've used dict a thousand times without a clue what's inside; in the next 25 lines you'll write the whole machine yourself, and afterwards Python's dict will never feel like magic again. There's a deep payoff to doing this by hand: you'll see exactly where the O(1) comes from, and exactly what makes it decay.

The first thing any real hash table must confront is the awkward fact you'll meet head-on in §3: two different keys will sometimes land in the same slot. That's a collision, and it's not rare or avoidable — it's guaranteed. So a hash table isn't really "a hash function plus an array"; it's "a hash function plus an array plus a plan for collisions." The plan we build here is the simplest one, and it has a lovely physical analogy: the coat pegs in a school cloakroom, where each numbered peg can hold several coats on one hook. In hashing terms that's separate chaining — each array slot holds not a single value but a small list (a "bucket") of (key, value) pairs. When two keys collide, you don't panic and you don't overwrite; you just hang the newcomer on the same peg. To look a key up, you jump to its slot and scan that one short bucket.

Why is that still fast? Because if your hash spreads keys evenly and you don't overstuff the table, each bucket stays tiny — one or two entries — so "scan the bucket" is basically constant work. The average case is O(1). The gotcha to keep in the back of your mind is the worst case: if every key happens to hash to the same slot (a terrible hash function, or an attacker feeding you adversarial keys), all your entries pile onto one peg and lookup degrades to a full linear scan — O(n). That's why the class below also tracks a load factor and resizes when buckets get crowded, doubling the array and re-hashing everything to spread the load back out. Watch for that resize logic as you read — it's the same amortized-doubling trick you saw with Python's list in D1, and it's what keeps the "average O(1)" promise honest as the table grows.

pythonclass HashMap:
    def __init__(self, size=8):
        self._buckets = [[] for _ in range(size)]   # list of buckets
        self._n = 0                                    # item count

    def _slot(self, key):
        return hash(key) % len(self._buckets)

    def put(self, key, value):
        bucket = self._buckets[self._slot(key)]
        for i, (k, _) in enumerate(bucket):
            if k == key:
                bucket[i] = (key, value)      # update existing
                return
        bucket.append((key, value))           # new key
        self._n += 1
        if self._n / len(self._buckets) > 0.75:  # load factor threshold
            self._resize()

    def get(self, key, default=None):
        for k, v in self._buckets[self._slot(key)]:
            if k == key:
                return v
        return default

    def _resize(self):
        old = [pair for b in self._buckets for pair in b]
        self._buckets = [[] for _ in range(len(self._buckets) * 2)]
        self._n = 0
        for k, v in old:                       # rehash everything into the bigger table
            self.put(k, v)

m = HashMap()
m.put("weather", get_weather := "fn")
m.put("scale", "fn2")
print(m.get("weather"))                     # 'fn'

3 · Collisions — the heart of the matter advanced

Here's the fact that surprises everyone the first time: collisions aren't an edge case you might hit — they're mathematically unavoidable, and you'll hit them almost immediately. There's a famous, spooky-feeling version of this called the "birthday paradox": in a room of just 23 people, it's more likely than not that two share a birthday. The same counting logic applies to hash slots. You don't need anywhere near "as many keys as slots" before two keys collide — you need shockingly few. So a hash table that only worked when nothing ever collided would be useless in practice. Collisions are the normal weather, not a storm.

The unbeatable reason is the pigeonhole principle: if you have more pigeons than pigeonholes, at least one hole must hold two pigeons. A hash function maps a practically infinite universe of possible keys (every string you could ever type) down onto a finite array of slots — so it must map some different keys to the same slot. No hash function, however clever, escapes this. That reframes the whole subject: the interesting question was never "how do I avoid collisions?" (you can't) but "how do I handle collisions gracefully when they happen?" Every hash table in existence is defined by its answer to that one question — its collision-resolution strategy.

You've already met one answer: chaining, the list-per-slot approach from §2. Its cost profile is the table below, and the shape is worth internalising because it's the shape of all hashing. The common misconception to shed here is treating "O(1) average" and "O(n) worst case" as a contradiction — they're not; they describe different situations. With a decent hash function and a load factor kept in check (buckets short), the average lookup touches a handful of entries and behaves as O(1). The worst case — every single key colliding into one bucket — collapses to a linear O(n) scan, but it's a pathological scenario you engineer against (good hash, resizing) rather than one you meet by accident. The very next section shows the other major strategy, open addressing, which handles the same collisions with no bucket lists at all.

4 · Open addressing (linear probing) expert essential

Think about parking in a busy lot where the rule is "park in your assigned spot." You drive to spot 12 — but someone's already there. You don't build a second deck on top of spot 12 (that's what chaining does with its bucket lists); you simply roll forward to spot 13, then 14, until you find an open space, and you remember "I'm somewhere near 12." That roll-forward-until-you-find-a-gap is open addressing, and it's a fundamentally different answer to the collision question than chaining: instead of hanging overflow off to the side, it keeps everything inside the one array.

Mechanically, when a key's home slot is occupied you probe — check the next slot, then the next, wrapping around the end back to the front — until you land on an empty slot. The simplest probe sequence, "just try slot+1, slot+2, …", is linear probing, and that's what the diagram and lab below implement. Why bother, when chaining already works? Two words: cache locality. A chained table scatters its bucket lists all over memory, so following a bucket means chasing pointers to far-flung addresses — slow for the CPU, which loves reading contiguous memory. Open addressing keeps entries packed side by side in one array, so probing a few neighbours is blisteringly fast on real hardware. This is exactly why CPython's actual dict uses open addressing (with a cleverer, "perturbed" probe sequence rather than plain +1) — it was tuned for speed on real machines over decades.

The trap that catches people, and it's a subtle one: deletion. Suppose weather is at slot 2 and scale probed past it to land at slot 4. If you delete weather and just blank out slot 2, then later search for scale — you hash to 2, find it empty, and conclude "not here," even though scale is sitting right there at slot 4. Blanking the slot broke the probe chain. The fix is a tombstone: a special marker meaning "something was deleted here, keep probing past me." Searches walk through tombstones; inserts may reuse them. It's a small detail with outsized consequences — forget it and your table silently loses entries. Keep an eye out for the _EMPTY sentinel in the code below; a production version would need a distinct tombstone marker alongside it.

python_EMPTY = object()          # sentinel for a never-used slot

class OpenAddrMap:
    def __init__(self, size=8):
        self._keys = [_EMPTY] * size
        self._vals = [None] * size
        self._n = 0

    def put(self, key, value):
        i = hash(key) % len(self._keys)
        while self._keys[i] is not _EMPTY and self._keys[i] != key:
            i = (i + 1) % len(self._keys)   # probe the next slot (wraps around)
        if self._keys[i] is _EMPTY:
            self._n += 1
        self._keys[i], self._vals[i] = key, value

    def get(self, key, default=None):
        i = hash(key) % len(self._keys)
        while self._keys[i] is not _EMPTY:
            if self._keys[i] == key:
                return self._vals[i]
            i = (i + 1) % len(self._keys)
        return default

5 · dict and set internals & guarantees intermediate

You've been driving these two every day without opening the hood — and now you can. Every time you wrote if x in seen against a set, or config["timeout"] against a dict, and it came back instantly, you were cashing in the hashing machinery from the last four sections. This is the satisfying moment where the from-scratch work pays off: Python's set and dict aren't special built-in magic — they're the exact hash tables you just built, hand-tuned in C. Knowing that turns "I use dicts" into "I know when a dict will and won't stay fast."

The mental model is simple. A set is a hash table that stores only keys, no values — so it answers exactly two questions superbly: "have I seen this?" (membership) and "give me each unique thing once" (dedup), both O(1) on average. A dict is the same table but each key carries a value alongside it, giving you O(1) keyed lookup. The everyday reflex worth building: the instant your code does "have I already seen this?" or "look this up by name," you want a set or dict, not a list. A list forces a scan (O(n)) for those questions; the hash table makes them free.

Two guarantees are worth pinning down because they trip people up. First, ordering: since Python 3.7 a dict officially preserves insertion order — iterate it and you get keys back in the order you added them. That's a deliberate feature of a compact-array design layered over the hash table, so you can rely on it. A set, by contrast, makes no order promise — never write code that assumes set iteration order, because it can shift between runs or versions. Second — and this is the common mistake — people assume "average O(1)" means "always fast." It doesn't: the same worst-case collision story from §3 still lurks underneath, and (as you saw) a dict resizes as it grows, so an occasional insert quietly pays an O(n) rehash. For virtually all real code these are non-issues, but knowing they exist is the difference between using the tool and understanding it. The lab makes the powers concrete: dedup, membership, set algebra, and keyed access, all backed by the hashing you now understand from the inside.

python# set: O(1) membership + dedup
seen = set()
seen.add("docA"); seen.add("docA")
print(len(seen))                     # 1 — duplicates collapse
print("docA" in seen)              # True — O(1), not a scan

# set algebra — each is O(len) not O(n*m)
a, b = {1,2,3}, {2,3,4}
print(a & b, a | b, a - b)           # {2,3} {1,2,3,4} {1}

# dict: O(1) keyed access, ordered by insertion
dispatch = {"weather": "fn", "scale": "fn2"}
print(dispatch["scale"])            # 'fn2' — straight to the slot

6 · The four hashing patterns intermediate → advanced

Sit in on enough coding interviews and you notice something almost funny: a huge share of the "medium" problems are the same four hashing moves wearing different costumes. The candidate who's seen the moves solves them in five minutes; the one who hasn't reinvents them under pressure and runs out of time. These four patterns aren't obscure tricks — they're the everyday tools that turn a slow, obvious solution into a fast one, and once you can name them you'll spot them in the wild constantly.

They all share one engine, which is worth stating outright because it's the whole point: a set or dict lets you replace "search through everything again" with an instant O(1) lookup. Any time your first-draft solution has a loop inside a loop — "for each item, go look through the rest" — that's a red flag for O(n²), and the fix is almost always to remember what you've already seen in a hash table so the inner search vanishes. Here are the four costumes that engine wears: (1) dedup — a set answers "seen this before?" so you keep only firsts; (2) frequency counting — a dict (or Counter) tallies occurrences in one pass; (3) grouping — a defaultdict(list) files items under a shared key; and (4) complement lookup — the "two-sum" move, where you store what you've seen so the partner you need is an O(1) question away.

The mistake to avoid is treating these as four unrelated recipes to memorise. They're one instinct — "can a hash map remember something so I don't have to search for it?" — pointed at four common shapes. Learn the instinct and the four fall out for free; memorise the four and you'll freeze the moment a problem looks slightly different. As you read the lab, notice that every single pattern is really the same question asked about a different thing: have I seen it (dedup), how often (count), what does it belong with (group), or is its partner here (complement).

pythonfrom collections import Counter, defaultdict

nums = [3, 1, 3, 3, 2, 1]

# 1. Dedup while preserving order (set for membership, list for order)
seen, unique = set(), []
for x in nums:
    if x not in seen:
        seen.add(x); unique.append(x)     # [3, 1, 2]

# 2. Frequency count — O(n)
freq = Counter(nums)                      # {3: 3, 1: 2, 2: 1}
print(freq.most_common(1))              # [(3, 3)]

# 3. Group items by a key
words = ["apple", "avocado", "banana"]
by_letter = defaultdict(list)
for w in words:
    by_letter[w[0]].append(w)          # {'a': [...], 'b': [...]}

# 4. Two-sum in O(n) — the hash-map version of D1's two-pointer
def two_sum(nums, target):
    pos = {}                              # value -> index seen so far
    for i, x in enumerate(nums):
        if target - x in pos:            # complement already seen? O(1)
            return (pos[target - x], i)
        pos[x] = i
    return None

7 · Recursion — a function that calls itself basic → intermediate

You've done recursion in real life, even if you'd never call it that. Imagine you're standing in a long cinema queue and want to know your position, but you can only see the person directly in front of you. So you tap their shoulder and ask, "what number are you?" They don't know either — so they ask the person in front of them, and so on, until the question reaches the very front of the line. That first person can answer directly: "I'm number 1." Then the answer travels back: each person adds one and passes it back to whoever asked. That is recursion, exactly: a problem you can't solve directly, so you delegate to a smaller version of the same problem, and combine the answer that comes back.

Every recursive function has precisely two parts, and you should hunt for both every time. The base case is the front of the queue — the trivial input you can answer with no further asking (person number 1; factorial(1) = 1; an empty list). The recursive case is the shoulder-tap — you reduce the problem to a strictly smaller subproblem and call yourself, then do a little work with the result. "Strictly smaller" is the load-bearing word: each call must move measurably closer to the base case, or the questions ripple down the queue forever. There's a beautiful equivalence hiding here that this whole track leans on: recursion and the stack from D2 are two views of the same thing. Each unfinished call is a frame stacked on Python's call stack, waiting; the base case stops the pile growing; then frames pop off one by one as answers combine back up. The diagram below draws that push-down/pop-up staircase.

The mistake that bites every beginner exactly once is the missing (or unreachable) base case. Forget it, or write a recursive step that doesn't actually shrink the input, and the calls stack up without end — Python protects you by capping the stack (around 1000 frames by default) and raising RecursionError rather than crashing your machine, but the bug is yours. So the discipline is a two-question checklist for every recursion you write: "What's my base case — and does every recursive call definitely get closer to it?" Get those two right and the function is correct; the rest is just deciding what small piece of work to do on the way back up. Recursion truly shines on branching, tree-shaped data — nested lists, file trees, the parse trees and graphs you'll meet in D4–D6 — where a loop would be clumsy but "solve me for each smaller part" is the natural fit.

pythondef factorial(n):
    if n <= 1:                # base case — stops the recursion
        return 1
    return n * factorial(n - 1)   # smaller subproblem

# Recursion shines on nested/tree-shaped data — flatten arbitrary nesting:
def flatten(items):
    for x in items:
        if isinstance(x, list):
            yield from flatten(x)   # recurse into sub-lists
        else:
            yield x
print(list(flatten([1, [2, [3, 4]], 5])))   # [1, 2, 3, 4, 5]

8 · Memoization → dynamic programming advanced

Here's a failure you can feel. Write the textbook one-line recursive Fibonacci, run fib(35), and watch your terminal just… sit there for seconds. Bump it to fib(45) and you could go make coffee. Nothing is broken — the code is correct — yet it's uselessly slow. This is one of the most instructive performance cliffs in all of programming, because the fix is a single idea that turns a program that would run past the heat-death of the universe into one that finishes instantly. That idea is the bridge from recursion to dynamic programming, and Fibonacci is the perfect place to watch it happen.

The reason naive Fibonacci is catastrophic is repeated work, and it's worth seeing precisely why. fib(5) calls fib(4) and fib(3); but fib(4) also calls fib(3) — so fib(3) gets computed twice, and each of those recomputes fib(2), and so on. The call tree branches in two at every level and is riddled with the same subproblems solved over and over, so the total work roughly doubles with each added n — that's O(2ⁿ), exponential, the "falls off a cliff" class from D1. The analogy: it's like re-reading a book from page one every time you need to recall a fact, instead of jotting the fact on a sticky note the first time. The waste isn't in computing the answers — it's in computing the same answers again and again.

Memoization is the sticky note. The first time you compute fib(k), you store the result in a hash map keyed by k; every later request for fib(k) is then an O(1) lookup instead of a whole subtree of recomputation. Because each distinct subproblem is now solved exactly once, the cost collapses from O(2ⁿ) to O(n) — the same code, one cache, an astronomically different runtime. And that little move is the essence of dynamic programming: DP is nothing more mystical than "recursion with overlapping subproblems, where you remember each answer so you never recompute it." The one thing beginners overlook is that memoization only helps when subproblems actually repeat — caching a recursion whose calls are all distinct buys you nothing but memory. Fibonacci overflows with repeats, which is why it's the classic. The diagram contrasts the wasteful tree with the cached chain, and the lab shows three versions — naive, memoized, and a bottom-up form that drops the recursion entirely to reach O(n) time in O(1) space.

pythonfrom functools import lru_cache

# 1. Naive — O(2^n). fib(35) already crawls.
def fib_slow(n):
    return n if n < 2 else fib_slow(n-1) + fib_slow(n-2)

# 2. Memoized — a hash map remembers each fib(k). O(n).
@lru_cache(maxsize=None)
def fib_memo(n):
    return n if n < 2 else fib_memo(n-1) + fib_memo(n-2)

# 3. Bottom-up DP — no recursion, O(n) time, O(1) space
def fib_dp(n):
    a, b = 0, 1
    for _ in range(n):
        a, b = b, a + b
    return a

print(fib_memo(100))    # instant; fib_slow(100) would never finish

9 · Backtracking expert advanced

You already know backtracking — you did it the last time you were lost in a maze or a corn field. You walk down a path; it dead-ends; so you walk back to the last fork and try a different branch; that dead-ends too, back you go again. You never teleport to a fresh start — you rewind one step and try the next unexplored option. That "try it, and if it doesn't pan out, undo and try the next" discipline is the entire idea of backtracking, and it's the tool for a whole family of problems that otherwise look impossibly open-ended: generate all arrangements, or find a valid configuration among a combinatorial explosion of possibilities.

Concretely, backtracking is a depth-first walk over a tree of choices. At each step you make one choice (place this queen, take this element, fill this Sudoku cell), then recurse to decide the next choice on top of it; if you reach a complete solution you record it, and if you hit a dead end — or finish exploring a branch — you undo the last choice and try the next sibling. That rhythm is so reliable it's worth burning into memory as a three-beat skeleton: choose → explore → un-choose. It's really just the recursion from §7 with one addition — you actively rewind your shared state on the way back up, so the next branch starts from a clean slate. This is how you generate permutations and subsets (the labs below), and how the classic constraint puzzles — N-queens, Sudoku, word search — are solved.

The single most common bug, and it's always the same one: forgetting the un-choose. It's seductive to write "choose, then recurse" and stop — the choosing and exploring feel like the substance, and the undo feels like tidying up you can skip. But without it your shared path or used markers stay dirtied by the branch you just finished, so the next branch explores from a corrupted state and your output turns to garbage. The un-choose isn't cleanup — it's the load-bearing beam. (In the permutations lab, try deleting the path.pop(); used[i] = False line and watch the whole thing break; that one line is the backtracking.) A close second: on many problems you can prune — abandon a branch the moment it's provably hopeless (a queen already attacked, a partial sum already too big) instead of exploring it to the bitter end, which is what makes backtracking tractable on puzzles that would otherwise be astronomically large.

pythondef permutations(items):
    result = []
    used = [False] * len(items)
    path = []

    def backtrack():
        if len(path) == len(items):        # a complete arrangement
            result.append(path[:])          # copy the current path
            return
        for i in range(len(items)):
            if used[i]:
                continue
            used[i] = True; path.append(items[i])    # choose
            backtrack()                                 # explore
            path.pop(); used[i] = False              # un-choose (backtrack)

    backtrack()
    return result

print(permutations(["a", "b", "c"]))   # 6 orderings

Exercises advanced

🎯 Interview practice interview

The interview questions this topic gets asked — worked, with code. For the full pattern catalog see D8 · Big Tech DSA patterns.

pythondef two_sum(nums, target):
    seen = {}
    for i, x in enumerate(nums):
        if target - x in seen:
            return (seen[target - x], i)
        seen[x] = i
    return None

pythondef subsets(nums):
    res, path = [], []
    def bt(start):
        res.append(path[:])
        for i in range(start, len(nums)):
            path.append(nums[i])
            bt(i + 1)
            path.pop()
    bt(0)
    return res

Checkpoint advanced

from collections import Counter

def most_frequent(s):                  # O(n) time, O(k) space
    counts = Counter(s)                # dict: char -> count, built in one pass
    return counts.most_common(1)[0]

print(most_frequent("mississippi"))    # ('s', 4)  (ties -> first seen)

from collections import defaultdict

def group_anagrams(words):             # n words, k = max length
    groups = defaultdict(list)
    for w in words:
        key = "".join(sorted(w))       # anagrams share a sorted signature
        groups[key].append(w)
    return list(groups.values())

print(group_anagrams(["eat", "tea", "tan", "ate", "nat", "bat"]))
# [['eat','tea','ate'], ['tan','nat'], ['bat']]

class HashMap:                         # avg O(1) put/get; worst O(n) if all collide
    def __init__(self, size=8):
        self.size = size
        self.buckets = [[] for _ in range(size)]
    def _idx(self, key):
        return hash(key) % self.size
    def put(self, key, value):
        bucket = self.buckets[self._idx(key)]
        for i, (k, _) in enumerate(bucket):
            if k == key:
                bucket[i] = (key, value); return
        bucket.append((key, value))
    def get(self, key, default=None):
        for k, v in self.buckets[self._idx(key)]:
            if k == key:
                return v
        return default

m = HashMap()
m.put("a", 1); m.put("b", 2); m.put("a", 9)
print(m.get("a"), m.get("b"), m.get("z", -1))   # 9 2 -1

def longest_consecutive(nums):         # O(n) time, O(n) space
    s = set(nums)
    best = 0
    for x in s:
        if x - 1 not in s:             # only start counting at a run's beginning
            length = 1
            while x + length in s:
                length += 1
            best = max(best, length)
    return best

print(longest_consecutive([100, 4, 200, 1, 3, 2]))   # 4  (1,2,3,4)

from functools import lru_cache

@lru_cache(maxsize=None)
def fib_memo(n):                       # O(n) time/space after memo
    return n if n < 2 else fib_memo(n - 1) + fib_memo(n - 2)

def fib_dp(n):                         # O(n) time, O(1) space (bottom-up)
    a, b = 0, 1
    for _ in range(n):
        a, b = b, a + b
    return a

print(fib_memo(30), fib_dp(30))        # 832040 832040

def subsets(nums):                     # 2^n subsets, each built in O(n)
    result = []
    def backtrack(start, path):
        result.append(path[:])         # record the current subset
        for i in range(start, len(nums)):
            path.append(nums[i])       # choose
            backtrack(i + 1, path)     # explore
            path.pop()                 # un-choose (the backtrack)
    backtrack(0, [])
    return result

print(subsets([1, 2, 3]))
# [[], [1], [1,2], [1,2,3], [1,3], [2], [2,3], [3]]

Knowledge check check yourself