Hashmaps & Sets — Hash Functions, Collisions

Review boundary and corrected contracts

The toy table validates power-of-two capacity, searches past tombstones before updating an existing key, and compares key identity before equality. It is a learning implementation, not CPython: tombstone accumulation can make it slow. Hashability means stable hashes and compatible equality, not universal immutability. Expected lookup cost, amortised resizing cost, key-computation cost and worst-case collisions are separate questions.

The examples below teach the stated input contracts; fragments and deliberately incorrect counterexamples are exercises, not production implementations. Complexity counts elementary operations unless a bit-cost or allocation caveat is stated. Practice times are suggestions, not measured performance or hiring guarantees.

Learning objective: Understand hashmaps deeply enough to reason about collisions, load factor, hash-flooding attacks, and Python dict internals — and to recognise when membership, counting or grouping can replace repeated scans, without losing required ordering or equality semantics.

Why this session exists

If you learn one data structure well, make it the hashmap. It is a common speed-up for repeated membership, count-by-key, grouping and complement lookup. Databases can also use merge or nested-loop joins; routing and caches can use trees or other indexes. Choose by the required operations rather than assuming every index is a hashmap. This session is the "how it actually works" version — including the two ways it can fall apart at scale.

You will be able to

• Explain a hash function, a bucket, and a collision to a friend in 60 seconds.

• Reach for dict or set instead of nested loops when a problem screams ‘lookup by key’.

• Recognise the classic patterns: two-sum, group-by-anagram, longest-consecutive, subarray-sum-equals-k.

• Separate expected constant probe cost from amortised resizing: a clean-table growth can move O(n) entries, while adversarial collisions can make a sequence quadratic.

• Recognise hash flooding and combine keyed/randomised string hashing with request-size, field-count and work limits.

Prerequisites

• S023 · Arrays & Strings — you'll compare hashmap solutions against two-pointer.
• S008 · Python Data Structures — dict, set, defaultdict, Counter.

Pre-read · skim before the session (30 min total)

Further reading: Python Docs · Dictionaries

Further reading: Python Dictionary Implementation

Further reading: CPython dictobject.c

(a) Intuition · 5 min

A hashmap is a magic coat check

Real: You hand a coat check attendant your coat. They compute a number from your name (‘Dinesh’ → 47), walk directly to slot 47, and hang the coat. Later you say ‘Dinesh’, they compute 47 again, walk to slot 47, and hand your coat back. No searching. Sometimes two names hash to slot 47. Then that slot holds a tiny list of (name, coat) pairs, and the attendant scans the short list to find yours. As long as collisions are rare, this is still effectively O(1).

 
    d["dinesh"] = "coat" computes hash("dinesh") % table_size and writes the pair into that bucket. d["dinesh"] repeats the hash, jumps to the bucket, and returns the value. Hash + probes + equality checks → expected O(1) table work for well-distributed, constant-cost keys; not necessarily one comparison.
    Extra work appears when many keys share a probe region or when the table grows before it fills. Resizing redistributes entries; CPython can reuse stored hashes rather than recomputing every key hash. Growth and collision handling are implementation policies, not a promise of fixed latency.
  

The three ideas that unlock hashmaps

What you're really learning

• Hash function — maps a hashable key to an integer. A key's hash must stay stable during its lifetime; equal keys must have equal hashes. Unequal keys may collide. Python string hashes are salted within a process, not a portable ID.

• Collision handling — chaining keeps entries in a bucket collection; open addressing probes slots in the table. Probing need not visit adjacent slots. CPython uses open addressing with a perturbation-based sequence.

• Load factor and growth — empty slots keep searches short. CPython's versioned implementation uses a two-thirds usable fraction, but growth factors and layout are not language guarantees. Our toy doubles its capacity before a prospective live count reaches two-thirds.

Hashability is a hash/equality contract, not a synonym for immutability

Lists and dicts are unhashable. A tuple is hashable only when its elements are hashable: (1, "x") works, but ([1],) does not. A user-defined mutable object can remain hashable under identity equality; mutating unrelated attributes does not change its identity. A value-equality class must keep every field involved in its hash and equality stable while used as a key. Otherwise lookup can fail or entries become inconsistent. Python does not magically detect every such mutation.

class Box:
    pass                         # default identity equality/hash
box = Box()
d = {box: "kept"}
box.label = "mutable attribute"
assert d[box] == "kept"
assert hash((1, "x")) == hash((1, "x"))
try:
    hash(([1],))
except TypeError:
    print("a tuple containing a list is unhashable")
assert len({1: "int", True: "bool", 1.0: "float"}) == 1

The final line is not a collision bug: 1 == True == 1.0 and their hashes agree, so these are one dict key. Use an explicit type tag if your application must distinguish them. Python's glossary states the contract.

Timeline — hashmaps become the default

Hashing predates Python; associative arrays made key-based lookup a routine language feature. The useful modern milestones are narrower than a single-inventor story:

• CPython's compact-table work made insertion-order iteration an implementation property in 3.6; Python 3.7 made it a language guarantee. That is insertion order, not sorting, and not a guarantee that different producers insert in the same order.
• PEP 456 specifies SipHash-based protection for string/bytes hashing in Python 3.4. Hash randomisation existed before that PEP; the PEP is not the start date of all hash randomisation.
• Open addressing, chaining, Robin Hood and cuckoo hashing are design alternatives, not a chronological sequence in which each replaces the previous one. Source/version and workload determine the actual choice.

Optional archived videos

These original resource pointers are retained as optional viewing, not verified primary evidence or a substitute for the explanations here: hash-table intuition, modern dict implementation talk, and Two Sum walkthrough. Playback, exact attribution and durations were not verified in this review. Laurent Luce's older implementation article is background; use the pinned source notes for current implementation claims.

(b) From a key to a bucket · 15 min

One insert, step by step

Follow a new key through an open-addressed table: the hash picks a starting bucket, but a collision can send the insert elsewhere. The numbers, post-insert growth check and adjacent-slot probes below are illustrative, not CPython's exact hash output/probing or the toy code's pre-insert growth order. Watch the two sources of extra work: finding an empty slot and growing the table.

The collision branch searches for one free slot; the resize branch redistributes all existing entries. Those are different costs, even though both are hidden behind a single assignment. The example keeps colliding keys in the same array; chaining instead keeps a collection of entries at each bucket.

Chaining vs open addressing

Chaining: each bucket holds a collection of entries. Linked lists are one choice; treeified buckets are another. A chain can become linear under collisions, and nodes can cost allocations and pointer chasing.

Open addressing: entries are found by probing the table. Layout and probe policy matter: linear probing is simple but clusters; CPython uses perturbation. Keep spare slots. A load threshold near two-thirds belongs to particular implementations, not all open-addressed maps.

Robin Hood hashing: when inserting, a key with a longer probe distance may displace one with a shorter distance, reducing probe-distance variation. This does not give a universal constant worst-case probe bound. Modern Rust HashMap documents a SwissTable-based design, not Robin Hood as its current default.

Cuckoo hashing: in the ideal two-table scheme, a key has two candidate locations. Lookup checks both; insertion may evict a resident to its alternate location and can cycle, requiring a rebuild. Two-probe worst-case lookup assumes the structure maintains that invariant and hash/equality work is constant; it is not a worst-case constant insertion guarantee. No Redis HyperLogLog implementation claim is needed to understand this design.

The classic hashmap patterns

At the application level, the useful question is what to remember under each key. Membership needs only a set; counting, grouping, and complement lookup attach different values to the same lookup mechanism.

‘Have I seen X before?’ → set

Desc: expected O(1) table work for add/membership under well-distributed, constant-cost hashes and equality. Use for deduplication, cycle detection, ‘is this in the whitelist?’.

‘Count by key’ → Counter / defaultdict(int)

Desc: counts[key] += 1. Use for frequency tables, mode, word counts, top-K.

‘Group by key’ → defaultdict(list)

Desc: groups[key].append(item). Use for group-by-anagram, group-by-day, bucketing.

‘Complement lookup’ → dict

Desc: ‘Have I seen target − x before?’ → the two-sum family. Store what you've seen; ask if the mate is there.

‘Memoisation’ → dict cache

Desc: cache[(args)] = result. The building block of dynamic programming (S033) and any expensive pure function.

When NOT to use a hashmap

Cases where a hashmap is the wrong tool

Name: You need order by key

Desc: Use a sorted structure (SortedList, tree map, or sort the dict.items()). Python dicts preserve INSERTION order, not sorted order.

Name: You need range queries (‘keys between 100 and 200’)

Desc: Hashmap has no locality. Use a sorted container or an ordered search tree. A heap gives an extremum, not efficient arbitrary range lookup.

Name: Keys are dense small integers 0..N

Desc: A list/array indexed by the integer often avoids hash overhead. Compare occupancy and memory: a sparse huge domain can still favour a dict.

Name: You need cryptographic guarantees

Desc: Python hash() is not a cryptographic digest or stable serialized identifier. Use a suitable cryptographic primitive: SHA-256 for an unkeyed digest, HMAC for authentication, and a password-specific KDF for passwords. A bare digest does not authenticate data.

If a nested loop repeatedly searches for a key, consider indexing once

Some nested loops are already linear in aggregate; others must enumerate quadratically many pairs. A dict helps only when the inner work is reducible to keyed state without losing necessary duplicates, ordering or multiplicity.

Hash cost, probe cost and collision controls

Expected O(1) describes table probes for well-distributed keys; amortised O(1) separately spreads occasional growth over many inserts. A worst-case lookup is O(n) equality checks, and n colliding insertions can take O(n²) total checks. These bounds assume constant-cost hash/equality; long strings, tuples and large integers add key work.

CPython caches a string object's hash after its first computation. Hashing a fresh long string includes first-hash work; timing its creation also measures allocation/copying. Rehashing the same object does not prove fresh-string hashing constant. Do not infer a fixed speedup from a microbenchmark.

# Deliberate collisions, bounded input: correctness must survive.
class CollisionKey:
    def __init__(self, value):
        self.value = value
    def __hash__(self):
        return 7
    def __eq__(self, other):
        return isinstance(other, CollisionKey) and self.value == other.value
 
keys = [CollisionKey(i) for i in range(12)]
d = {key: key.value for key in keys}
assert d[CollisionKey(9)] == 9       # equal distinct object
assert len(d) == 12                 # collisions do not merge unequal keys

This tests equality/collision semantics, not latency or resistance to a real attack. Custom __hash__ methods can force collisions despite string-hash randomisation.

Question: Why do open-addressed tables keep empty slots, and why might a particular implementation grow near two-thirds occupancy rather than waiting for 100%?

Premise: A hash table maps a key to a slot via hash(key) % capacity. Two distinct keys can land in the same slot — a collision.

Because: the key space is unbounded and the slot count is finite; collisions are guaranteed by pigeonhole

Premise: CPython resolves collisions by probing table indices until it finds the matching key or an unused slot. Its compact representation separates indices from entries and can have split key/value storage; "one array of key/value pairs" is a useful toy, not an exact layout claim.

Model: if each unsuccessful probe independently hits an occupied slot with probability a, the expected probes until an empty slot are 1/(1−a): 2 at a=0.5, about 3 at 2/3, and 10 at 0.9. This idealised uniform-probing model motivates slack; real probes are dependent and linear probing clusters, so it is not an exact cost formula for CPython or MiniHashMap.

There is no mathematically universal optimum at two-thirds. The threshold balances memory, collision behaviour and implementation costs. Tombstones also consume search space without increasing live-key count.

CPython implementation details and resize thresholds vary by version. Python exposes no general dict reserve-capacity API. Measure latency-sensitive operations and avoid depending on a particular internal load-factor rule.

Name: Coat-check with numbered pegs

Picture: A hash table is a wall of numbered pegs. hash(key) computes a starting peg number, with a cost that depends on the key. You hang it there. To retrieve, you recompute the number and walk straight to that peg — you never search the wall.If the peg is taken, you walk right until you find a free one. That is the whole data structure. Resizing and probing preserve reachability; stable hash/equality preserves a key's identity as a lookup target.

• Cost = hash(key) + probes + equality checks. Expected probe count may be constant; hash/equality cost depends on key type/size and caching.

• Hash and equality behaviour must remain stable. Mutability of unrelated attributes is compatible with identity-hashed objects.

• A set provides membership without associated values. It shares the hashability contract, but its internal layout and resizing need not match dict.

• Insertion order is a Python dict language guarantee since 3.7, not an accident. Sets provide no insertion- or sorted-order guarantee; avoid predictions about future language versions.

Trigger: Fire this model the moment you see: an O(n²) nested loop that could be an O(n) dict join · unhashable type · a "random" iteration order changing between runs · a group-by written by hand · a de-dup pass · a lookup inside a hot loop that is somehow slow (check your key size) · a Spark shuffle skewing to one partition (same maths, different scale).

Decision: You need to check membership repeatedly against a collection of N items. Keep it as a list, or build a set?

Name: Scan a list

Gain: zero build cost, zero extra memory, works with unhashable elements, and preserves order and duplicates

Cost: a membership test may scan O(N) entries; K tests have O(N·K) worst-case comparisons, assuming constant-cost equality

Pick: N is tiny (a handful of items) or you test membership only once or twice — building a set costs a full pass, so for a one-off query the build is often unnecessary

Name: Build a set / dict

Gain: expected constant-cost table probes; building once and doing K lookups is expected O(N + K) with bounded-cost hash/equality, versus O(N·K) repeated scans

Cost: expected O(N) build work and O(U) table space for U unique keys; actual bytes depend on implementation and occupancy. A set discards multiplicity and provides no order guarantee. A dict preserves insertion order, not sorted order.

Pick: you will test more than a handful of times against the same collection — measure the crossover if it matters; it depends on hit positions, key costs, reuse and memory

Name: Sort once, then binary search

Gain: O(N log N) once then O(log N) per test, with contiguous memory and no hashing; supports range queries a set cannot answer

Cost: O(log N) comparisons per lookup, requires a total order, and inserting into a sorted array can cost O(N); batched rebuilds are another option

Pick: you also need nearest / range / ordered-iteration semantics, or memory is tight enough that the set's overhead matters

Verdict: build a set once for repeated unordered membership on hashable values; use a dict if you need associated state or insertion order. Keep a list for small or one-off scans and unhashable values. Use sorted storage for range/nearest queries. A hash table does not intrinsically destroy all order—Python dict iteration is ordered—but hashing alone does not provide sorted-key range queries.

(c) Hands-on · 25 min

Save as hashmaps.py. Zero dependencies beyond stdlib.

"""hashmaps.py — the canonical hashmap patterns + a mini hashmap from scratch.
 
Run:  python hashmaps.py
"""
from __future__ import annotations
from collections import defaultdict, Counter
 
 
# ------------------------------------------------------------------
# 1) Two Sum — the ‘complement lookup’ pattern
# ------------------------------------------------------------------
def two_sum(nums: list[int], target: int) -> tuple[int, int] | None:
    """Return distinct indices summing to target, or None. Expected O(n) table work."""
    seen: dict[int, int] = {}                # value -> index
    for i, x in enumerate(nums):
        need = target - x
        if need in seen:                     # expected constant table work
            return seen[need], i
        seen[x] = i
    return None
 
 
# ------------------------------------------------------------------
# 2) Group Anagrams — the ‘group by key’ pattern
# ------------------------------------------------------------------
def group_anagrams(words: list[str]) -> list[list[str]]:
    """Group words that are anagrams of each other. Key = sorted characters."""
    groups: dict[tuple[str, ...], list[str]] = defaultdict(list)
    for w in words:
        key = tuple(sorted(w))
        groups[key].append(w)
    return list(groups.values())
 
 
# ------------------------------------------------------------------
# 3) Top-K frequent — the ‘count by key’ pattern
# ------------------------------------------------------------------
def top_k_frequent(nums: list[int], k: int) -> list[int]:
    counts = Counter(nums)
    return [val for val, _ in counts.most_common(k)]
 
 
# ------------------------------------------------------------------
# 4) Longest Consecutive Sequence — the ‘set as membership oracle’ pattern
# ------------------------------------------------------------------
def longest_consecutive(nums: list[int]) -> int:
    """Longest run of consecutive integers. Expected O(n) table work."""
    pool = set(nums)
    best = 0
    for x in pool:
        # Only start counting from the LEFT end of a run.
        if x - 1 in pool:
            continue
        length = 1
        while x + length in pool:
            length += 1
        best = max(best, length)
    return best
 
 
# ------------------------------------------------------------------
# 5) Subarray Sum Equals K — the ‘prefix-sum + hashmap’ pattern
# ------------------------------------------------------------------
def subarray_sum_equals_k(nums: list[int], k: int) -> int:
    """Count nonempty contiguous subarrays whose sum == k. Expected O(n).
 
    Trick: if prefix_sum[j] − prefix_sum[i-1] == k, that's a valid subarray.
    So we count, at each j, how many previous prefix sums equal prefix_sum[j] − k.
    """
    count = 0
    prefix = 0
    seen: dict[int, int] = {0: 1}            # sum 0 has occurred once (empty prefix)
    for x in nums:
        prefix += x
        count += seen.get(prefix - k, 0)     # query BEFORE recording this prefix
        seen[prefix] = seen.get(prefix, 0) + 1
    return count
 
 
# ------------------------------------------------------------------
# 6) A toy hashmap — see the machinery
# ------------------------------------------------------------------
class MiniHashMap:
    """Learning table: linear probing, stable hashable keys; no ordered iteration API."""
    _EMPTY = object()
    _TOMBSTONE = object()
 
    def __init__(self, capacity: int = 8) -> None:
        if type(capacity) is not int:
            raise TypeError("capacity must be an integer, not bool")
        if capacity < 2 or capacity & (capacity - 1):
            raise ValueError("capacity must be a power of two >= 2")
        self._cap = capacity
        self._size = 0
        self._keys = [self._EMPTY] * capacity
        self._vals = [None] * capacity
 
    def _probe(self, key):
        """Yield indices to probe for `key`."""
        h = hash(key) & (self._cap - 1)      # cheap mod when cap is a power of 2
        for step in range(self._cap):
            yield (h + step) & (self._cap - 1)
 
    def __setitem__(self, key, value):
        if (self._size + 1) * 3 >= self._cap * 2:
            self._resize()
        tombstone = None
        for idx in self._probe(key):
            slot = self._keys[idx]
            if slot is self._TOMBSTONE:
                if tombstone is None:
                    tombstone = idx
                continue
            if slot is self._EMPTY:
                dst = idx if tombstone is None else tombstone
                self._keys[dst], self._vals[dst] = key, value
                self._size += 1
                return
            if slot is key or slot == key:
                self._vals[idx] = value
                return
        if tombstone is not None:
            self._keys[tombstone], self._vals[tombstone] = key, value
            self._size += 1
            return
        raise RuntimeError("hash table unexpectedly full")
 
    def __getitem__(self, key):
        for idx in self._probe(key):
            slot = self._keys[idx]
            if slot is self._EMPTY:
                raise KeyError(key)
            if slot is not self._TOMBSTONE and (slot is key or slot == key):
                return self._vals[idx]
        raise KeyError(key)
 
    def _resize(self):
        old_keys, old_vals = self._keys, self._vals
        self._cap *= 2
        self._keys = [self._EMPTY] * self._cap
        self._vals = [None] * self._cap
        self._size = 0
        for k, v in zip(old_keys, old_vals):
            if k is not self._EMPTY and k is not self._TOMBSTONE:
                self[k] = v
 
 
if __name__ == "__main__":
    print("two_sum [2,7,11,15] target=9 :", two_sum([2, 7, 11, 15], 9))
    print("group_anagrams:", group_anagrams(["eat", "tea", "tan", "ate", "nat", "bat"]))
    print("top_k [1,1,1,2,2,3] k=2 :", top_k_frequent([1, 1, 1, 2, 2, 3], 2))
    print("longest_consecutive [100,4,200,1,3,2] :", longest_consecutive([100, 4, 200, 1, 3, 2]))
    print("subarray_sum k=2 [1,1,1] :", subarray_sum_equals_k([1, 1, 1], 2))
 
    m = MiniHashMap()
    for w in "the quick brown fox jumps over the lazy dog".split():
        m[w] = m.__getitem__(w) + 1 if w in ("the",) and w in m._keys else 1
    print("MiniHashMap 'the' :", m["the"])
    print("MiniHashMap 'fox' :", m["fox"])

Anatomy of the script

What each block teaches

Name: two_sum

Desc: The canonical complement-lookup pattern. Note: we store AFTER checking, so a value never matches itself.

Name: group_anagrams

Desc: Group-by pattern with a derived key (sorted chars). tuple() because lists aren't hashable.

Name: top_k_frequent

Desc: Counter counts n inputs in expected O(n) table work. With u distinct values and 1 < k < u, heap selection typically costs O(u log k); returning all u uses sorting, O(u log u). Ties follow first encounter order. k <= 0 returns an empty list; k > u returns all distinct values.

Name: longest_consecutive

Desc: Only start from the left end of each distinct run. Each unique integer is scanned once inside a run and once in the outer loop, so there are O(n) table operations; expected O(n) time assumes bounded-cost, well-distributed hashing.

Name: subarray_sum_equals_k

Desc: At prefix P, query the number of earlier prefixes P-k before recording P. This excludes empty subarrays, including when k=0. Negative values are supported; there is no nonnegative-window assumption. Expected O(n) table work, O(n) stored counts.

Name: MiniHashMap._probe

Desc: Linear probing with power-of-2 capacity: hash mask instead of mod. Fast, but bad hashes cause clustering — real CPython uses a perturbation scheme.

Name: MiniHashMap._resize

Desc: Before a prospective insertion reaches two-thirds live occupancy, double and reinsert live keys. With good hashes and a clean table, geometric growth amortises that work. This toy also resizes on some updates, does not shrink, and never compacts tombstones except during growth; deletion-heavy workloads can scan the whole capacity even with few live keys.

What to observe when you run it

ClassName: ml-4 list-decimal space-y-1

two_sum: (0, 1). subarray_sum: 2 (subarrays [1,1] appearing at indices 0-1 and 1-2). group_anagrams returns groups of sizes 3, 2, 1 in first-key-encounter order: [eat, tea, ate], [tan, nat], [bat]. Words inside each group retain input order; input strings/lists are not mutated. longest_consecutive returns 4 (the run 1,2,3,4). MiniHashMap: ‘the’ → 2 and ‘fox’ → 1. The demo increments only the repeated word "the"; it is not a general counting loop.

Contracts, equality and a deletion trace

two_sum returns the first pair discovered by increasing right index, with the latest stored matching left index; it does not enumerate all pairs. Checking before insertion prevents reuse of the same position. group_anagrams sorts Unicode code points, without case-folding or normalisation: canonically equivalent spellings may need preprocessing. For word lengths mᵢ, sorting costs O(Σ mᵢ log(mᵢ+1)); key creation/hashing adds O(Σ mᵢ), with expected probe behaviour assumed for the grouping table. Group lists are newly allocated but retain references to the original immutable strings.

The toy map accepts stable, hashable keys with ordinary boolean equality. Keys whose equality mutates the table, raises errors or is inconsistent are outside this teaching contract. Its private sentinel objects must not be used as keys. Like built-in dict, an identical key object is found before equality is considered: this matters for nan, which is not equal to itself. Values are stored by reference, not copied; changing a stored mutable value is visible through every alias.

For deterministic collision testing use integer keys 0, 8 and 16 in capacity 8: they begin at bucket 0. After deleting 0, a lookup for 8 must skip the tombstone. Updating 8 must search past that tombstone instead of inserting a duplicate. Deleting an absent key raises KeyError; a fully probed tombstone chain also terminates because _probe yields at most capacity positions.

Goal: Add a delete method to MiniHashMap using the tombstone technique

Hint: Deletion in open addressing can't just clear the slot — that would break the probe chain for later keys. Instead, mark the slot as TOMBSTONE. Lookups skip tombstones but keep probing. Inserts can reuse tombstone slots.

Add this method to MiniHashMap:

def __delitem__(self, key):
    for idx in self._probe(key):
        slot = self._keys[idx]
        if slot is self._EMPTY:
            raise KeyError(key)
        if slot is not self._TOMBSTONE and (slot is key or slot == key):
            self._keys[idx] = self._TOMBSTONE
            self._vals[idx] = None
            self._size -= 1
            return
    raise KeyError(key)

Test:

MiniHashMap.__delitem__ = __delitem__  # attach the exercise method
m = MiniHashMap()
m[0] = "a"; m[8] = "b"; del m[0]   # deliberate collision at capacity 8
m[8] = "updated"                    # update beyond tombstone, not a new key
assert m._size == 1 and m[8] == "updated"
try:
    m[0]
except KeyError:
    print("0 correctly gone")
m[16] = "c"                         # reuse the earlier tombstone
assert m._size == 2 and m[8] == "updated" and m[16] == "c"

(d) Production reality · 15 min

Hash flooding: count work and bound input

For n distinct keys with one hash, insertion i may compare with i−1 stored keys. The sum 0+1+…+(n−1) is n(n−1)/2 comparisons: O(n²) for the whole build, not per insertion. Keyed string hashing makes precomputed attacks harder; it is not a substitute for caps on request bytes, field counts and computation. PEP 456 documents the security motivation and earlier weaknesses. Do not disable randomisation to create a persistent ID; use a declared byte encoding and stable digest instead. A fixed hash seed is a reproducibility tool, not stronger attack resistance.

Cache locality is a measurement question

A hash-based lookup may jump between cache lines. A compact sorted array may scan or binary-search fewer bytes but do more comparisons. Compare the same keys, key construction, hit/miss ratio and working-set size before choosing. Merely rearranging fields in a tuple does not guarantee nearby users land in nearby buckets: a good hash deliberately mixes fields. The earlier unsourced Gmail speedup anecdote is not evidence; the mechanism to investigate is memory access and key computation, not a promised 100× fix.

Feature order needs a schema, not just an ordered dict

Two dictionaries can preserve insertion order perfectly and still produce incompatible feature vectors:

left = {"age": 30, "income": 80}
right = {"income": 80, "age": 30}
assert list(left.values()) != list(right.values())
schema = ("age", "income")
assert [left[k] for k in schema] == [right[k] for k in schema] == [30, 80]

Updating an existing key does not move it; deleting and reinserting moves it to the end. Use one versioned feature schema across training and serving and decide what to do about missing or extra keys. Alphabetical sorting is valid only if the model was trained with that same ordering. Python ≥3.7 alone cannot establish cross-process feature alignment.

Where this shows up in the rest of the plan

Hashmaps connect this lesson to memoisation (a cache keyed by state), hash joins (build/probe with join multiplicity retained), key-based caches and rate-limit counters. Not every DP uses a dict: dense tables are often arrays. Redis provides multiple data structures, not only a network hashmap. Vocabulary maps can assign token IDs, but tokenisation also depends on merge/segmentation rules. Distributed key placement adds ownership, replication and failure semantics that a local dict does not model. These are topic connections, not claims that the legacy session numbers still identify the right lesson.

(e) Recall + stretch · 10 min

Self-check (answer follows each question).

Recall — click to reveal

Q: What are the two properties a good hash function must have?

A: For a Python key, the governing correctness rules are stable hashing and equal keys having equal hashes. For performance, good distribution for the workload and cheap computation matter. Unequal keys can share a hash; no hash avoids all collisions over an unbounded domain. Salted string hashes need only stay consistent within the process.

Q: What's the difference between chaining and open addressing?

A: Chaining stores a collection of entries per bucket; open addressing probes slots in the table. The probe sequence need not be adjacent. CPython uses open addressing; Java HashMap can treeify collision bins, so not every bucket is always a linked list.

Q: Why is dict insert ‘amortised O(1)’, not strict O(1)?

A: Geometric growth occasionally moves O(n) entries under good hashing; across an insertion sequence the sum of growth work is O(n), hence amortised O(1) per insert. Expected probe cost is a separate assumption about collisions and key cost. Adversarial collisions can defeat constant expected performance; the toy map also has tombstone-accumulation limits.

Q: Why can't you use a list as a dict key?

A: Python lists are unhashable and hash([1, 2]) raises TypeError; there is no actual changing list hash to demonstrate. A tuple works only if all its elements are hashable. Mutable identity-equality objects may still be hashable; the real rule is stable hash/equality, not blanket immutability.

Q: Give the 3-line ‘complement lookup’ template.

A: Check before recording to avoid matching an item with itself; the expanded, executable template is:

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

Q: What is a hash-flooding attack?

A: An attacker supplies many colliding keys so one lookup/insertion can scan O(n) candidates and building n entries can take O(n²) comparisons. Keyed/randomised string hashing frustrates predictable collisions; input and work limits remain necessary. Custom constant hashes and non-string key types are not all protected by the string seed.

Q: Why is Python's built-in hash() unsafe to persist to disk or across processes?

A: It is not a portable stable-ID contract. String/bytes hashes are salted and normally differ across processes; some other types, such as small integers, are not randomised in that way. Encode data canonically and use a stable digest such as SHA-256 when that is the requirement. A digest alone is not authentication.

Q: You need to look up entries by a range of keys (‘keys 100–200’). Why is a hashmap wrong?

A: A hash index does not maintain sorted-key search structure; consecutive numeric keys might land nearby, but that is not a range-query contract. Use sorted storage or an ordered index for efficient key ranges; sorting all dict items for each query would add work.

Q: Explain the prefix-sum + hashmap trick for subarray_sum_equals_k in one sentence.

A: For current prefix P, count earlier prefixes equal to P−k, then record P: each pair identifies a nonempty subarray, in expected constant table work per step for bounded-cost keys.

Q: Stretch — design a hashmap where lookups are guaranteed O(1) in the WORST case, not amortised.

A: In the ideal two-table cuckoo scheme each key occupies one of two candidate slots, so a lookup checks at most two slots, assuming constant-time hash/equality. Insertion may trigger a chain of evictions or a rebuild when it cycles. The lookup bound comes from the maintained location invariant, not from a guarantee about insertion latency. Real variants with stashes/overflow need their own bounds; do not infer a Redis HyperLogLog implementation from the analogy.

Explain-out-loud test

Teach these three, one minute each, no notes:

1. What is a hash function and why does it turn lookups from O(n) to O(1)?
2. What's a collision, and how do open-addressing hashmaps deal with it?
3. Give one concrete case where a hashmap is the WRONG data structure.

Explain-out-loud answer guide

1. A hash maps a stable key to a starting location. Good distribution limits expected probes, while hash/equality cost and collision worst cases still matter.
2. Two unequal keys can choose the same bucket. Open addressing follows a probe sequence and compares keys; deletion uses tombstones so a later key remains reachable.
3. For keys in a numeric range, use sorted storage or an ordered index. A dict preserves insertion order but does not supply sorted-key locality or range search.

What comes next

Next: S025 · Linked Lists — Singly, Doubly, When They Win

Hub: The 6-Month Learning Plan

Part of a 130-session evergreen learning series. Session structure: intuition → visual → hands-on → production war stories → recall. Duration: 90 minutes.

Corrective source notes

Implementation details also use CPython v3.14.0 string hashing, Counter source, heap selection, and OpenJDK 25 HashMap. These pin the caching, top-k and tree-bin qualifications rather than universalising them.

• Python 3.14 glossary: hashable — stable hashes, equality and hashable containers.
• Python 3.14 built-in types — equal numeric keys, insertion order and unordered sets.
• CPython v3.14.0 dict implementation — versioned probing, dummy slots and usable fraction, not language API promises.
• Counter — counts and first-encounter tie order.
• PEP 456 and hashlib — separate hash-flooding resistance from digest/password/authentication requirements.

Sources checked 2026-10-10. Code tests are bounded and do not certify adversarial throughput.

These citations support the named claims, not blanket certification of the lesson. Worked proofs are derived in the text; execution scope and finite-test limits are recorded separately.