VFlash: Fast, Accurate Visual Planning via Flash Primitive Decoding
u_Unrolled
D1: CS & Systems Foundations · Dicts and Sets — Hashing and O(1) Lookups
Phase 1/Domain 1/Lesson 5

Dicts and Sets — Hashing and O(1) Lookups

15 min read·Foundational·Free lesson
Dicts and Sets — Hashing and O(1) Lookups

The incident. A data team deduplicates 2 million training examples before fine-tuning. The script keeps seen = [] and checks if text in seen: for each example. It is still running the next morning. Changing one line, seen = set(), makes it finish in under ten seconds. Same logic, same data, roughly 100,000× less work.

You already know: lists and the cost of x in items (Lists and tuples); tuples as keys.


1. Hashing: how a dict finds things instantly

The question. How can a dict find one key among millions without checking them one by one?

Start from nothing. A dict is a hash table. For each key, Python computes hash(key): a number derived from the key's value. That number picks a slot in an internal array. To look up a key, Python hashes it again and goes straight to that slot. No scanning, so lookup is O(1) on average, whether the dict holds 10 keys or 10 million.

Two different keys can land in the same slot (a collision); Python then probes a few other slots. With a good hash function and enough spare slots, that stays rare.

python
import time

n = 200_000
ids_list = list(range(n))
ids_set = set(ids_list)
lookups = range(n - 500, n)            # near the end: the worst case for a list

start = time.perf_counter()
found_list = sum(1 for x in lookups if x in ids_list)
t_list = time.perf_counter() - start

start = time.perf_counter()
found_set = sum(1 for x in lookups if x in ids_set)
t_set = time.perf_counter() - start

print(found_list, found_set)
print(f"list: {t_list:.4f}s   set: {t_set:.6f}s")
print("set is over 100x faster:", t_list / t_set > 100)

Both find all 500 ids. The list scans up to 200,000 items per lookup; the set does a hash and a jump.

a key goes through hash(), which picks one slot in the table directly, versus a list lookup scanning item by item.
Diagram— a key goes through hash(), which picks one slot in the table directly, versus a list lookup scanning item by item.

Key idea. "Have I seen this?", "what's the value for this id?" and "remove duplicates" are dict and set jobs. A list makes each of them O(n).

From production

A recommendation service filters out items the user already bought: [i for i in candidates if i not in purchased]. purchased is a list of 50,000 ids and there are 2,000 candidates per request.

p99 latency is 900 ms. What's the cheapest big win?

  1. Convert purchased to a set once per request: each check becomes O(1)
  2. Cache the HTTP response for an hour
  3. Sort candidates first
  4. Add more servers
Show the answer

A. Convert purchased to a set once per request: each check becomes O(1) — Each not in on a list scans up to 50,000 ids, so one request does up to 100 million comparisons. Building a set costs 50,000 steps once, then each check is a hash lookup.

2. What can be a key

The question. Why can't a list be a dict key?

Start from nothing. A key's hash must never change, or the dict would look in the wrong slot later. So keys must be hashable: in practice, immutable values like strings, numbers, tuples of those, and frozensets. Also, keys that are equal must have equal hashes, so 1, 1.0 and True are the same key:

python
cache = {}
cache[("asha", "small-model")] = "cached answer"    # tuple key: fine
try:
    cache[["asha", "small-model"]] = "nope"         # list key: refused
except TypeError as err:
    print("TypeError:", err)

d = {1: "int"}
d[1.0] = "float"
d[True] = "bool"
print(d)

prefs = {"theme": "dark"}
print(prefs.get("font", "default"), prefs.get("theme"))   # get never raises
print(list({"b": 1, "a": 2, "c": 3}))                     # insertion order is kept

The list key raises TypeError: unhashable type: 'list'. The three numeric keys collapse into one entry: {1: 'bool'}. Since Python 3.7, dicts keep insertion order, so list(...) gives ['b', 'a', 'c'].

the key 'user-42' hashed in two processes with different PYTHONHASHSEED values lands in two different buckets, while hashlib.sha256 gives the same bucket every run; beside it, 1, 1.0 and True collapsing into one dict key.
Diagram— the key 'user-42' hashed in two processes with different PYTHONHASHSEED values lands in two different buckets, while hashlib.sha256 gives the same bucket every run; beside it, 1, 1.0 and True collapsing into one dict key.

Two production traps with hashing. hash() is designed for dict slots inside one running process. For strings, Python salts it with a random seed per process, which protects servers against attackers who craft colliding keys. So the same string hashes differently after a restart, on another worker, or on another machine. Teams get burned when they use hash(user_id) % 100 to assign users to A/B test groups or to pick a shard. The second trap is changing a dict while looping over it.

python
import hashlib, os, subprocess, sys

# hash() of a string is salted per process (PYTHONHASHSEED), so it differs between runs
code = "print(hash('user-42') % 100)"
for seed in ("1", "2"):
    out = subprocess.run([sys.executable, "-c", code], env={**os.environ, "PYTHONHASHSEED": seed},
                         capture_output=True, text=True).stdout.strip()
    print(f"PYTHONHASHSEED={seed}: bucket {out}")

def stable_bucket(user_id, buckets=100):
    digest = hashlib.sha256(user_id.encode()).hexdigest()   # same bytes in, same digest out, forever
    return int(digest, 16) % buckets

print("sha256 bucket:", stable_bucket("user-42"), stable_bucket("user-42"))

prefs = {"theme": "dark", "beta": None, "font": "mono"}
try:
    for k in prefs:
        if prefs[k] is None:
            del prefs[k]                 # changing size while iterating
except RuntimeError as e:
    print("RuntimeError:", e)
prefs = {k: v for k, v in prefs.items() if v is not None}   # build a new dict instead
print(prefs)
  • With two different seeds, the same user lands in buckets 10 and 71 here (the exact numbers depend on the Python version). An experiment bucketed this way would move users between groups on every deploy. hashlib.sha256 gives the same bucket (79) every time, on every machine.
  • Deleting keys while iterating raises RuntimeError: dictionary changed size during iteration. Build a new dict with a comprehension instead (or loop over list(prefs), a snapshot of the keys).

In production. Dicts are everywhere in AI code. Parsed JSON request bodies and API responses are dicts. A tokenizer's vocabulary is a dict from token string to integer ID, so vocab["hello"] is a hash lookup on every token. Experiment-assignment, feature-flag and sharding systems use stable hashes (cryptographic hashes or MurmurHash) of user IDs for exactly the reason shown above. Two more defaults worth having: use .get(key, default) for optional fields in external JSON, and let KeyError surface for fields your code genuinely requires.

From production

An experiment assigns users with group = 'B' if hash(user_id) % 2 else 'A'. Dashboards show users switching groups between days, and the metrics are noisy.

What's the cause and fix?

  1. Users clear their cookies; nothing to fix in code
  2. Modulo 2 is biased; use modulo 100
  3. String hashes are salted per process, so restarts and different workers give different groups; use a stable hash like hashlib.sha256 of the user_id
  4. Dicts are unordered; sort the users first
Show the answer

C. String hashes are salted per process, so restarts and different workers give different groups; use a stable hash like hashlib.sha256 of the user_id — hash() for str/bytes is randomized per process (PYTHONHASHSEED). It's for in-memory dict slots, not for persistent assignment. A cryptographic or other stable hash of the ID gives the same group on every machine and every day.

3. The counting and grouping toolkit

The question. What's the cleanest way to count or group things?

Start from nothing. Two classes from collections remove most boilerplate:

  • Counter counts hashable things and can give you the most common ones.
  • defaultdict(list) creates an empty list the first time you touch a missing key, so grouping needs no if key not in d check.
python
from collections import Counter, defaultdict

log = [
    ("api", 200), ("api", 500), ("auth", 401), ("api", 200),
    ("search", 500), ("api", 500), ("auth", 200), ("search", 503),
]

status_counts = Counter(code for _, code in log)
print(status_counts.most_common(2))

errors_by_service = defaultdict(list)
for service, code in log:
    if code >= 500:
        errors_by_service[service].append(code)
print(dict(errors_by_service))

totals = {}
for service, _ in log:
    totals[service] = totals.get(service, 0) + 1      # the manual way
print(totals)

This prints [(200, 3), (500, 3)] (ties keep first-seen order), then {'api': [500, 500], 'search': [500, 503]}, then {'api': 4, 'auth': 2, 'search': 2}.

eight (service, status) log rows flowing in one pass into a Counter of status codes (200: 3, 500: 3, 401: 1, 503: 1) and a defaultdict(list) grouping 5xx codes by service (api: [500, 500], search: [500, 503]).
Diagram— eight (service, status) log rows flowing in one pass into a Counter of status codes (200: 3, 500: 3, 401: 1, 503: 1) and a defaultdict(list) grouping 5xx codes by service (api: [500, 500], search: [500, 503]).

A real-world example: the first step of a tokenizer. Byte-pair encoding (BPE), the tokenizer family behind GPT-style models, learns its vocabulary by counting. Start with every word split into single characters. Count every adjacent pair across the corpus. Merge the most frequent pair into a new symbol, then repeat. Step one is a Counter:

python
from collections import Counter

corpus = ["low", "lower", "lowest", "newer", "newest", "wider"]
words = [list(w) for w in corpus]                     # start from single characters

pairs = Counter()
for w in words:
    for a, b in zip(w, w[1:]):                        # adjacent symbol pairs
        pairs[a + b] += 1
print(pairs.most_common(4))

The top pairs are ('we', 4), then ('lo', 3), ('ow', 3) and ('er', 3). "we" appears in lower, lowest, newer and newest, so BPE's first merge would make we a single symbol. Real tokenizers run this loop tens of thousands of times over gigabytes of text. The data structure doing the work is still a hash map of pair counts. (NLP foundations, in the Deep Learning path, builds the full algorithm.)

In production. Counter and defaultdict show up wherever you aggregate: error counts per endpoint in an incident, token counts per customer for billing, label distributions before training (is the dataset 95% one class?), and n-gram counts in text pipelines. At larger scale the same idea moves into SQL GROUP BY or a dataframe groupby. You'll find it much easier to read those once you've written the dict version yourself.

From production

An on-call engineer needs 'the 5 users who hit the most errors in the last hour' from a list of (user_id, status) events.

Which is the most direct correct approach?

  1. Build a list of unique users with a loop and if u not in users
  2. Sort the list of events and take the first 5
  3. Counter(u for u, s in events if s >= 500).most_common(5)
  4. A set of user ids, then take any 5
Show the answer

C. Counter(u for u, s in events if s >= 500).most_common(5) — Counter counts per key in one pass (O(n)) and most_common returns the top k. Sorting raw events doesn't count them; a set loses the counts entirely.

4. Sets: membership and set algebra

The question. How do you compare two collections ("which are new? which are missing?")?

Start from nothing. A set is a dict with keys and no values: unique items, O(1) membership. Its operators answer comparison questions in one line:

python
yesterday = {"asha", "ravi", "meera", "john"}
today = {"asha", "meera", "zoya", "li"}

print(sorted(today - yesterday))     # new today
print(sorted(yesterday - today))     # didn't come back
print(sorted(today & yesterday))     # came both days
print(len(today | yesterday))        # anyone, either day
print(sorted(today ^ yesterday))     # exactly one of the days

emails = ["a@x.com", "b@x.com", "a@x.com", "c@x.com", "b@x.com"]
print(list(dict.fromkeys(emails)))   # dedupe, keeping the original order

set(emails) would also dedupe but loses order; dict.fromkeys keeps first-seen order because dicts remember insertion order.

a Venn diagram of yesterday's users (ravi, john | asha, meera) and today's (asha, meera | zoya, li), with each operator's result: - gives new or churned users, & gives both days, | gives 6 users, ^ gives 4.
Diagram— a Venn diagram of yesterday's users (ravi, john | asha, meera) and today's (asha, meera | zoya, li), with each operator's result: - gives new or churned users, & gives both days, | gives 6 users, ^ gives 4.

A real-world example: duplicates and leakage in training data. Two set jobs come up in every ML project. First, test examples must not appear in the training data, or the evaluation measures memory instead of skill. Second, near-duplicates (the same article with a word changed) should be found and removed. Exact matching misses them. Comparing sets of overlapping word sequences (shingles) catches them:

python
def shingles(text, k=3):
    words = text.lower().split()
    return {" ".join(words[i:i + k]) for i in range(len(words) - k + 1)}

def jaccard(a, b):
    return len(a & b) / len(a | b)

doc1 = "The transformer uses attention to mix information across all tokens in the sequence"
doc2 = "The transformer uses attention to mix information across every token in the sequence"
doc3 = "Gradient descent updates each weight in the direction that lowers the loss"

s1, s2, s3 = shingles(doc1), shingles(doc2), shingles(doc3)
print(f"doc1 vs doc2: {jaccard(s1, s2):.2f}")
print(f"doc1 vs doc3: {jaccard(s1, s3):.2f}")

train = {"what is attention?", "define overfitting", "explain dropout"}
test = {"explain dropout", "what is a gradient?"}
print("leaked into test:", sorted(train & test))
  • Jaccard similarity is the size of the intersection divided by the size of the union. doc1 and doc2 differ by two words and score 0.47, while the unrelated doc3 scores 0.00. Changing two words breaks every 3-word shingle that touches them, which is why even a light edit drops the score to about half. Dedup pipelines tune k and the threshold on their own data.
  • train & test finds the leaked example, ['explain dropout'], in one line.

In production. Comparing every pair of documents is O(n²), which is impossible at web scale. Pretraining pipelines use MinHash to approximate Jaccard similarity with short signatures, plus locality-sensitive hashing to find candidate pairs. Lee et al., "Deduplicating Training Data Makes Language Models Better" (ACL 2022), found that removing near-duplicates reduced memorized output and train–test overlap. The building blocks are exactly what this section showed: sets, intersections and hashes.

Quick check

You must dedupe a list of 1M prompts but keep their original order. Which is right?

  1. sorted(set(prompts))
  2. [p for p in prompts if prompts.count(p) == 1]
  3. list(set(prompts))
  4. list(dict.fromkeys(prompts))
Show the answer

D. list(dict.fromkeys(prompts)) — dict.fromkeys keeps first-seen order and is O(n). set() loses order, sorted() imposes a different one, and the count() version is O(n²) and also drops every duplicated prompt entirely.


Check yourself

  1. Why is x in some_set O(1) on average while x in some_list is O(n)?
  2. Why must dict keys be hashable?
  3. What does defaultdict(list) save you from writing?
  4. How do you dedupe a list while keeping its order?
  5. Why is hash(user_id) % 100 a bad way to assign users to experiment groups?
  6. How would you check whether any test prompts also appear in the training set, and how would you catch near-duplicates?
Answers
  1. The set hashes x and jumps to one slot; the list compares x with items one by one.
  2. The dict stores a key in the slot chosen by its hash. If the key could change, its hash would change and the dict would look in the wrong slot.
  3. The "if the key isn't there yet, create an empty list" check before appending.
  4. list(dict.fromkeys(items)).
  5. String hashes are randomized per process, so the bucket changes across restarts and machines. Use a stable hash of the bytes, such as hashlib.sha256.
  6. set(train) & set(test) for exact matches. For near-duplicates, compare shingle sets with Jaccard similarity (MinHash at scale).

Exercise

You have server log lines like "2026-11-14T10:02:11 ERROR E1027 timeout". Return the 3 most common error codes and, for each one, the first time it was seen. Use one pass over the logs.

Solution
python
from collections import Counter

logs = [
    "2026-11-14T10:00:01 INFO  -     ok",
    "2026-11-14T10:02:11 ERROR E1027 timeout",
    "2026-11-14T10:02:15 ERROR E2001 bad gateway",
    "2026-11-14T10:03:40 ERROR E1027 timeout",
    "2026-11-14T10:04:02 ERROR E3300 oom",
    "2026-11-14T10:05:19 ERROR E1027 timeout",
    "2026-11-14T10:06:30 ERROR E2001 bad gateway",
]

counts, first_seen = Counter(), {}
for line in logs:
    time_str, level, code, *_ = line.split()
    if level != "ERROR":
        continue
    counts[code] += 1
    first_seen.setdefault(code, time_str)      # only stores the first time

for code, n in counts.most_common(3):
    print(code, n, "first at", first_seen[code])

setdefault writes the value only if the key is missing, so the first timestamp sticks. Both structures are dicts, so each line costs O(1) and the whole job is a single O(n) pass.


This unlocks:

  • Strings and Unicode — dict keys are usually strings, and two strings that look identical may not be equal.
  • Iterators and generators — streaming millions of records through counters like these without loading them all.
  • Data structures and algorithms for AI — hash maps underpin caches, deduplication and vocabularies.