VFlash: Fast, Accurate Visual Planning via Flash Primitive Decoding
u_Unrolled
DSA for AI/ML · Module 02: Hashing

Lesson 2.1 of 12 in this moduleFree

Hash Maps and Sets from First Principles

Why `x in my_set` is O(1) on average while `x in my_list` is O(n): build a hash table from scratch, with buckets, collisions and resizing, then learn what it costs (memory, worst cases, hashable keys) and when a sorted array, a plain array or a Bloom filter fits better.

about 10 min 6 Python examples 2 quick checks

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.

python
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.

four keys hashed into 8 buckets; cat and ant collide in bucket 3 and are chained there, so a lookup hashes the key, jumps to its bucket and compares only the keys stored in it.
Diagram— four keys hashed into 8 buckets; cat and ant collide in bucket 3 and are chained there, so a lookup hashes the key, jumps to its bucket and compares only the keys stored in it.

Here is a working hash map in about 30 lines, using chaining:

python
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.

the cost of 16 inserts into a doubling table; most inserts cost 1, inserts 2, 3, 5 and 9 also copy 1, 2, 4 and 8 items, and the total is 31, under 3 per insert.
Chart— the cost of 16 inserts into a doubling table; most inserts cost 1, inserts 2, 3, 5 and 9 also copy 1, 2, 4 and 8 items, and the total is 31, under 3 per insert.
python
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

python
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)?

  1. Because Python is slow
  2. 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
  3. Because sets are sorted internally
  4. It is always 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
python
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

a decision map: scan the list for one lookup, binary search on sorted data without extra memory, a set or dict for many lookups, a plain array for small integer keys, and a Bloom filter for huge sets that tolerate false positives.
Diagram— a decision map: scan the list for one lookup, binary search on sorted data without extra memory, a set or dict for many lookups, a plain array for small integer keys, and a Bloom filter for huge sets that tolerate false positives.
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.

python
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?

  1. A set (or dict token → id): O(n) to build once, then O(1) average per query
  2. Scan a list each time
  3. Sort the queries
  4. A Bloom filter, because it's always better
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

  1. What does a hash function do, and why is a modulo needed?
  2. What is a collision, and how does chaining handle it?
  3. What is the load factor, and why does doubling make inserts O(1) amortised?
  4. Why is the O(1) only an average?
  5. Why can't a list be a dict key, and why are 1 and 1.0 the same key?
  6. When would you choose a plain array, binary search or a Bloom filter over a set?
Answers
  1. Turns a key into an integer; the modulo maps it into the table's range of bucket positions.
  2. Two keys in the same bucket; the bucket holds a small list of pairs, and lookups compare keys within it.
  3. 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).
  4. If many keys hash to the same bucket (bad luck or an attack), a lookup compares against all of them: O(n).
  5. Lists are mutable, so their hash could change while stored; and equal values must share a hash, so 1 == 1.0 share one key.
  6. 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.