S024 · Hashmaps & Sets — Hash Functions, Collisions

Module M03: Data Structures & Algorithms · Session 24 of 130 · Track: SW 🗺️

What you'll be able to do after this session

• Explain Hashmaps & Sets to a friend in one minute, out loud, no notes.
• Recognise it when you see it in real code / systems / papers.
• Complete the hands-on exercise at the end without looking up help.

Prerequisites

If you can't answer these in 30 seconds each, redo the linked session first:

• S023 — Arrays & Strings — Indexing, Slicing, Two-Pointer

Pre-read (skim before the session)

• 🎥 Intuition (5–15 min) · Hash Tables — the intuition (NeetCode) — why they're basically magic.
• 🎥 Deep dive (30–60 min) · Python dict internals in 10 minutes (mCoding) — how CPython actually implements dict.
• 🎥 Hands-on demo (10–20 min) · Hash Map — code walkthrough (NeetCode) — build a tiny one from scratch.
• 📖 Canonical article · Wikipedia — Hash table — collisions, probing, chaining explained cleanly.
• 📖 Book chapter / tutorial · Python docs — dict (built-in type) — API surface, insertion order guarantees, view objects.
• 📖 Engineering blog · LinkedIn — DataHub metadata graph — hash-keyed lookups at scale.

(a) Intuition · 5 min

The one-paragraph mental model. Why this concept exists, what problem it solves, and the analogy that makes it stick.

In one sentence: O(1) lookup is the trick behind 40% of interview problems.

If arrays are numbered mailboxes, a hashmap is the postal service. You hand over a key (a name, a URL, a user ID) and the system computes a number from it — the hash — that tells it which mailbox to open. Because computing the hash is O(1), and jumping to a mailbox is O(1), the whole "lookup by key" operation is O(1) on average. That's the entire point: turn "search" into "compute an address."

A set is a hashmap where you don't care about the values — you only ask "is this key present?" Same machinery, simpler interface.

Collisions are the wrinkle: two different keys might hash to the same mailbox. Real hashmaps handle this either by chaining (each mailbox holds a small list) or open addressing (probe the next mailbox). As long as the table has enough spare capacity (the load factor stays under ~0.7), collisions stay rare and lookups stay fast.

One-sentence gotcha to carry forever: A hashmap's O(1) is an average, not a guarantee — an adversary who can pick keys to force collisions can push you to O(n) per lookup. That's exactly the "hash flooding" DoS attack that broke Python, PHP, and Java web frameworks in 2011; the fix was randomising hash seeds at process start.

(b) Visual walkthrough · 15 min

Diagrams, worked examples, step-by-step visuals.

How d["alice"] = 42 actually stores the value:

Lookup d["alice"] does the exact same thing: hash, mod, jump, then check the key inside the bucket matches (in case of collision).

Worked example — building a tiny hashmap by hand:

Table size 8, hash function h(s) = sum(ord(c) for c in s).

Insert "cat": h = 99+97+116 = 312; 312 % 8 = 0 → bucket 0. Insert "dog": h = 100+111+103 = 314; 314 % 8 = 2 → bucket 2. Insert "tac": h = 312; 312 % 8 = 0 → collision! Bucket 0 already holds ("cat", ...). With chaining: bucket 0 becomes [("cat",...), ("tac",...)]. Lookup "tac" still walks the tiny chain and finds it.

If we keep inserting and the load factor exceeds ~0.7, the table doubles (a resize), all keys re-hash into the bigger table. That's why insertion is amortised O(1) — occasional resizes are amortised out over the many cheap inserts before them.

When to reach for which:

(c) Hands-on · 20 min

Code you type and run. Not pseudo-code — real, runnable, copy-pasteable.

# hashmap_playground.py
from collections import defaultdict, Counter
from time import perf_counter
import random
 
# ---- 1. O(1) lookup vs O(n) linear scan ----
n = 1_000_000
data = list(range(n))
random.shuffle(data)
s = set(data)
target = data[-1]  # worst case for a list scan
 
t0 = perf_counter(); ans = target in data; t1 = perf_counter()
t2 = perf_counter(); ans = target in s;    t3 = perf_counter()
print(f"'in list' ({n} items): {(t1-t0)*1000:7.2f} ms")
print(f"'in set'  ({n} items): {(t3-t2)*1e6:7.2f} us   <-- 10000x+ faster")
 
# ---- 2. Classic use: dedupe + count ----
words = "the quick brown fox jumps over the lazy dog the fox is quick".split()
print("
unique:", set(words))
print("counts:", Counter(words).most_common(3))
 
# ---- 3. Group-by with defaultdict ----
people = [("engineering","alice"),("sales","bob"),("engineering","carol"),
          ("sales","dave"),("engineering","eve")]
by_dept = defaultdict(list)
for dept, name in people:
    by_dept[dept].append(name)
print("groups:", dict(by_dept))
 
# ---- 4. Two-sum in O(n) using a hashmap ----
def two_sum(nums, target):
    seen = {}
    for i, x in enumerate(nums):
        need = target - x
        if need in seen:
            return (seen[need], i)
        seen[x] = i
    return None
 
print("
two_sum([2,7,11,15], 9) =", two_sum([2,7,11,15], 9))
 
# ---- 5. Build a naive hashmap to feel the mechanics ----
class TinyHashMap:
    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 = TinyHashMap(size=4)
for w in ["cat","dog","tac","god","bird"]:
    m.put(w, len(w))
print("
Tiny hashmap buckets:")
for i, b in enumerate(m.buckets):
    print(f"  [{i}] {b}")

Checklist:

1. in list takes milliseconds, in set takes microseconds for 1M items.
2. Counter.most_common(3) includes ('the', 3).
3. by_dept groups engineering people together.
4. two_sum returns (0, 1).
5. TinyHashMap shows at least one bucket with 2+ entries (collision demonstration).

Try this modification: measure how much slower TinyHashMap gets when you insert 10,000 items into a table of size 8 (i.e., force load factor to 1250). Then implement a resize method that doubles the table when load factor exceeds 0.7, and re-measure.

(d) Production reality · 10 min

How this shows up in real systems, gotchas, war stories, common bugs.

Hashmaps are so fundamental that they underlie every modern system's fast paths — indexed database lookups, JVM object dispatch, session stores, Redis, feature caches, service routing tables. But the same properties that make them fast also create classic failure modes:

1. Hash flooding / algorithmic complexity attacks. In 2011 researchers showed you could send a web form with thousands of POST fields all crafted to hash to the same bucket, degrading the server's request parser from O(n) to O(n²) and taking down PHP/Java/Python web frameworks. Modern runtimes randomise hash seeds at startup (PYTHONHASHSEED) and use SipHash for strings. Take-away: never trust that a hashmap's inputs are random — if attackers control the keys, either use a randomised hash (Python, Rust do this by default) or a tree-based map with worst-case O(log n).

2. Mutable keys = corrupted state. If you use a mutable object as a dict key and then mutate it, the hash changes but the object is still in the old bucket. The dict now silently loses the entry — key in d returns False even though the object is physically there. This is why Python raises TypeError: unhashable type: 'list' upfront. In Java, HashMap<MyPojo, X> bugs where equals/hashCode are inconsistent are a top-10 source of production heisenbugs.

3. Load factor and resize storms. When a dict crosses its load-factor threshold it resizes — allocates a bigger table, re-hashes everything. That single insert can take O(n). In hot paths (metrics ingest, log parsers) this shows up as periodic latency spikes. Fixes: pre-size the dict if you know the count ({} with initial capacity in Java, or just build from a comprehension in Python), or use a data structure with incremental resize (Redis's dict does exactly this — resizes over many operations instead of one giant hiccup).

Cache design uses hashmaps + eviction. Every LRU cache is a hashmap paired with a doubly linked list. Netflix's EVCache, Meta's Memcached fleet, and Redis are all essentially "hashmap + policy for what to evict." The interface is trivial; the operational complexity — sharding, replication, key-space migration, hot key mitigation — is enormous.

(e) Quiz + exercise · 10 min

1. What is the average-case time complexity of d[key] in a hashmap, and what is the worst case?
2. Why can't you use a Python list as a dictionary key?
3. Explain "load factor" in one sentence and why crossing it triggers a resize.
4. What is a hash-flooding attack and how do modern runtimes defend against it?
5. Give one concrete data-engineering problem where a Counter is the right tool.

Stretch (connects to S023 — Arrays): Explain why x in arr is O(n) for a list but O(1) for a set. What is stored differently in memory, and what algorithm runs when you evaluate in for each?

Explain-out-loud test

If you can't teach these 3 things to a friend without notes, redo the session:

1. What is Hashmaps & Sets? (one sentence, no jargon)
2. When would you use it? (one concrete example)
3. When would you NOT use it? (one anti-pattern)

What comes next

• Next session (S025): Linked Lists — Singly, Doubly, When They Win
• Previous (S023): Arrays & Strings — Indexing, Slicing, Two-Pointer
• Hub: The 6-Month Learning Plan

Part of a 130-session evergreen learning series. Session structure: (a) intuition · (b) visual walkthrough · (c) hands-on · (d) production reality · (e) quiz + exercise. Duration: 60 minutes.