The question this module answers: have I seen this before, and what did I store with it? A set remembers keys; a dict (hash map) remembers keys and values. Both answer in O(1) on average, at the cost of O(n) memory.
ML context. Hash maps are everywhere in ML systems:
- A tokenizer's vocabulary: token string → integer id.
- Feature dictionaries: category → index for one-hot or embedding lookup.
- Frequency counts: word counts, label counts, n-gram counts.
- Caches: input → computed embedding, so repeated requests are free.
- The hashing trick: hash features straight into a fixed-size vector, with no dictionary at all.
Understanding how a hash map works tells you when it's fast, when it isn't, and what it costs.
1. The problem: lookups in a list are O(n)
Given n user ids and q queries "is this id known?", the obvious approach scans the list for each query.
def count_known_scan(known_ids, queries):
return sum(1 for q in queries if q in known_ids) # `in` on a list scans: O(n)
known = list(range(0, 2000, 2)) # 1,000 even ids
queries = list(range(2000))
assert count_known_scan(known, queries) == 1000
print("list scan: O(n) per query, O(n · q) in total")
O(n · q): at n = q = 10⁵, that's 10¹⁰ comparisons. The fix must make each lookup independent of n.
2. First principles: turn a key into a position
Arrays give O(1) access by position: a[i] is one multiply-and-add (lesson 1.1). So if we could turn any key
into a position, we'd get O(1) lookups.
- If keys are small integers, the key is the position:
seen[id] = True. Perfect, but only for a small range. - For anything else (strings, tuples, huge integers), compute a hash: a function that turns the key into a large integer, then take it modulo the table size to choose a bucket.
Two different keys can land in the same bucket: a collision. So each bucket holds a short list of (key, value)
pairs, and a lookup compares the key only against the few pairs in its bucket.
Here is a working hash map in about 30 lines, using chaining:
class HashMap:
def __init__(self, capacity=8):
self.buckets = [[] for _ in range(capacity)]
self.size = 0
def _bucket(self, key):
return self.buckets[hash(key) % len(self.buckets)] # key → position
def get(self, key, default=None):
for k, v in self._bucket(key): # only this bucket's pairs
if k == key:
return v
return default
def put(self, key, value):
bucket = self._bucket(key)
for i, (k, _) in enumerate(bucket):
if k == key:
bucket[i] = (key, value) # overwrite
return
bucket.append((key, value))
self.size += 1
if self.size > 0.75 * len(self.buckets): # keep buckets short
self._resize(2 * len(self.buckets))
def _resize(self, capacity):
old = [pair for bucket in self.buckets for pair in bucket]
self.buckets = [[] for _ in range(capacity)]
for k, v in old: # every key moves: O(n)
self.buckets[hash(k) % capacity].append((k, v))
counts = HashMap()
for word in "the cat sat on the mat the end".split():
counts.put(word, counts.get(word, 0) + 1)
assert counts.get("the") == 3 and counts.get("cat") == 1 and counts.get("dog") is None
assert counts.size == 6 and len(counts.buckets) == 8
for i in range(100):
counts.put(i, i * i)
assert counts.get(99) == 9801 and len(counts.buckets) == 256
print("hand-built hash map works; buckets grew to", len(counts.buckets))
Python's dict and set use a cleverer layout (open addressing: on a collision, probe other slots in the same
array instead of chaining), but the principle is identical: hash → position → compare a few keys.
3. Why O(1) average: load factor and resizing
A lookup's cost is the length of its bucket. If n keys are spread evenly over m buckets, the average bucket length is
the load factor n / m. Keep it below a constant (0.75 above) by doubling the table when it gets full, and
each lookup compares O(1) keys on average.
Resizing costs O(n), since every key moves. But it happens rarely: after doubling, the next resize needs n more
inserts. Spread the cost over those inserts and each one pays O(1) extra: O(1) amortised, the same argument as
Python's list append.
def total_insert_cost(n):
capacity, size, cost = 1, 0, 0
for _ in range(n):
if size == capacity:
cost += size # copy everything into a table twice the size
capacity *= 2
cost += 1 # the insert itself
size += 1
return cost
for n in [16, 1000, 10**6]:
c = total_insert_cost(n)
assert c < 3 * n
print(f"n = {n:>8}: total cost {c:>8}, {c / n:.2f} per insert")
4. Using it: the list scan becomes a set lookup
import time
known = list(range(0, 200_000, 2))
queries = list(range(20_000))
t0 = time.perf_counter()
a = sum(1 for q in queries if q in known) # O(n) per query
t_list = time.perf_counter() - t0
known_set = set(known) # O(n) once
t0 = time.perf_counter()
b = sum(1 for q in queries if q in known_set) # O(1) average per query
t_set = time.perf_counter() - t0
assert a == b == 10_000
print(f"list: {t_list * 1e3:.0f} ms, set: {t_set * 1e3:.2f} ms")
assert t_set < t_list
From O(n · q) to O(n + q): build once, then constant work per query.
Quick check
Why is a hash set lookup O(1) on average but not guaranteed O(1)?
Show the answer
B. The key's hash picks a bucket directly, and resizing keeps buckets short on average; but if many keys collide into one bucket, a lookup must compare against all of them — The average depends on hashes spreading keys evenly; adversarial or degenerate hashes can put many keys in one bucket.
5. What hashing costs, and the rules
| Cost or rule | What it means | Consequence |
|---|---|---|
| Memory | Buckets, hashes and spare capacity: often 2–4× the raw data | 10⁸ keys may not fit; consider alternatives |
| Average, not worst case | Many colliding keys → O(n) per lookup | Untrusted keys can be attacked; Python randomises string hashes per process |
| Keys must be hashable | The hash must never change while stored | Use tuples and strings, not lists; never mutate a key |
| Equal keys must hash equally | a == b ⇒ hash(a) == hash(b) |
1, 1.0 and True are the same dict key |
| No order guarantee for lookups | Python dicts keep insertion order, but you can't range-query | "All keys between 10 and 20" needs a sorted structure |
d = {}
d[1] = "int"
d[1.0] = "float" # 1 == 1.0, so this overwrites the same key
assert d == {1: "float"}
try:
{[1, 2]: "list key"}
except TypeError as e:
print("lists can't be keys:", e)
key = (3, "cat") # tuples of hashable values are fine
assert {key: 1}[(3, "cat")] == 1
print("hashability rules hold")
6. When the constraints change
| If the constraint becomes… | Best structure | Lookup | Memory |
|---|---|---|---|
| One lookup, unsorted data | Scan the list | O(n) | O(1) extra |
| Many lookups | set / dict |
O(1) average | O(n) |
| Keys are integers in a small range R | Plain list / NumPy array indexed by key | O(1) worst case | O(R) |
| Data sorted, no extra memory | Binary search (module 5) | O(log n) | O(1) |
| Need range queries or order | Sorted array or balanced tree | O(log n) | O(n) |
| Billions of keys, "maybe" answers OK | Bloom filter | O(k) hashes | ~10 bits per key |
| Unbounded features, fixed memory (ML) | Hashing trick into a fixed-size vector | O(1) | O(buckets) |
The hashing trick (ML)
With millions of possible categorical values (user ids, n-grams), a vocabulary dictionary can be huge. The hashing trick skips the dictionary: hash each feature straight into one of D positions. Collisions are accepted as a small amount of noise in exchange for fixed memory and no lookup table.
import zlib
def hashed_features(tokens, dim=16):
vec = [0] * dim
for t in tokens:
h = zlib.crc32(t.encode()) # stable across runs (unlike hash() for str)
vec[h % dim] += 1
return vec
v = hashed_features(["new", "york", "new", "pizza"])
assert sum(v) == 4 and len(v) == 16
assert hashed_features(["new"]) == hashed_features(["new"]) # deterministic
print("hashed feature vector:", v)
Note the zlib.crc32: Python's built-in hash() for strings is randomised per process, so it must not be used
for features you save and reload. That's a real production bug.
Quick check
You need 'is this token in the vocabulary?' for 10⁵ tokens, queried millions of times. What fits best?
Show the answer
A. A set (or dict token → id): O(n) to build once, then O(1) average per query — Many lookups over a set that fits in memory is the textbook case for hashing; a Bloom filter only helps when memory is the bottleneck and false positives are acceptable.
7. Saying it out loud
"A list lookup is O(n) because it scans. A hash table turns the key into a bucket position with a hash function, so a lookup compares only the few keys in that bucket. Doubling the table keeps buckets short, so lookups are O(1) on average and inserts are O(1) amortised. The price is O(n) extra memory, hashable keys, and a bad worst case if many keys collide."
Check yourself
- What does a hash function do, and why is a modulo needed?
- What is a collision, and how does chaining handle it?
- What is the load factor, and why does doubling make inserts O(1) amortised?
- Why is the O(1) only an average?
- Why can't a list be a dict key, and why are
1and1.0the same key? - When would you choose a plain array, binary search or a Bloom filter over a set?
Answers
- Turns a key into an integer; the modulo maps it into the table's range of bucket positions.
- Two keys in the same bucket; the bucket holds a small list of pairs, and lookups compare keys within it.
- Keys per bucket on average (n / m). Each resize costs O(n) but happens after O(n) cheap inserts, so the extra cost per insert is O(1).
- If many keys hash to the same bucket (bad luck or an attack), a lookup compares against all of them: O(n).
- Lists are mutable, so their hash could change while stored; and equal values must share a hash, so
1 == 1.0share one key. - Plain array: small integer keys (O(1) worst case). Binary search: sorted data with no extra memory. Bloom filter: huge sets where "probably yes" is acceptable.