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.
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.
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?
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:
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'].
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.
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
10and71here (the exact numbers depend on the Python version). An experiment bucketed this way would move users between groups on every deploy.hashlib.sha256gives 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 overlist(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 letKeyErrorsurface 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?
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:
Countercounts 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 noif key not in dcheck.
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}.
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:
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.
Counteranddefaultdictshow 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 SQLGROUP BYor a dataframegroupby. 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?
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:
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 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:
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 scores0.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 tunekand the threshold on their own data. train & testfinds 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?
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
- Why is
x in some_setO(1) on average whilex in some_listis O(n)? - Why must dict keys be hashable?
- What does
defaultdict(list)save you from writing? - How do you dedupe a list while keeping its order?
- Why is
hash(user_id) % 100a bad way to assign users to experiment groups? - How would you check whether any test prompts also appear in the training set, and how would you catch near-duplicates?
Answers
- The set hashes x and jumps to one slot; the list compares x with items one by one.
- 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.
- The "if the key isn't there yet, create an empty list" check before appending.
list(dict.fromkeys(items)).- 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. 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
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.