Hash Tables: Sets and Dictionaries Under the Hood
20 min · Advanced
Need help? Ask a tutor on WhatsApp (opens in a new tab)Python dictionaries and sets are among the fastest and most heavily optimized hash table implementations in computer science. Understanding how CPython stores indices and entries reveals why lookups are average O(1) and why dictionaries preserve insertion order.
The Modern Compact Dictionary Layout
Compact dictionary is the CPython layout with a small sparse index table pointing into a dense list of entries kept in insertion order.
Prior to Python 3.6, dictionaries used a sparse array of 24-byte entries. Python 3.6 introduced the compact dictionary architecture pioneered by Raymond Hettinger.
indicesarray: A sparse array of small integers (int8, int16, etc.) mapping hash buckets to indices.entriesarray: A dense, compact array of(hash, key_ptr, value_ptr)appended in insertion order.- This architecture saves 20-25% memory and makes insertion order preservation a natural side-effect!
Hash Lookup and Collision Resolution
Hash is an integer computed from a value by hash(). Equal values must give equal hashes, and the number picks the starting bucket.
To look up d[key]: Python computes h = hash(key). The initial bucket is bucket = h & (table_size - 1).
key = "order-42"table_size = 8bucket = hash(key) & (table_size - 1)
print(hash(key) == hash("order-42"))print(0 <= bucket < table_size)Example 1 · Insertion order and hashes
d = {}d["apple"] = 10d["banana"] = 20d["cherry"] = 30
print("Keys in insertion order:", list(d.keys()))print("Hash of 'apple':", type(hash("apple")))Keys in insertion order: ['apple', 'banana', 'cherry'] Hash of 'apple': <class 'int'>
What this code does
- Dense entries array appends keys in chronological insertion order.
hash()returns an integer used to index the sparse bucket table.
Example 2 · Equal keys share one slot
prices = {1: "int"}prices[1.0] = "float"prices[True] = "bool"print(prices)print(hash(1) == hash(1.0) == hash(True)){1: 'bool'}
TrueWhat this code does
- 1, 1.0 and True are equal and have the same hash, so they are one key.
- The key stays 1, but the value is replaced by the latest assignment.
If the bucket is already taken by a different key (a collision), Python uses open addressing. For a match it checks the stored hash, then identity (is), then equality (==).
Perturbation Probing Algorithm
Open addressing resolves a collision by trying other slots inside the same table, not by hanging a list off the bucket.
Instead of linear probing (i + 1), which causes clustering, CPython uses a pseudorandom perturbation recurrence formula:
j = (5 * j + 1 + perturb) & mask; perturb >>= 5.
- Scrambles the probe sequence across the hash table.
- Incorporates high-order bits of the hash into probe indices.
- Quickly resolves collisions even for poorly distributed hashes.
Load Factor and Dynamic Resizing
Load factor is the share of table slots in use. CPython resizes at about 2/3 to keep probe chains short.
A hash table slows down when it is too full. CPython grows the table once about 2/3 of its slots are used, so there are always empty slots to end a probe.
import sys
d = {}last = sys.getsizeof(d)for n in range(1, 40): d[n] = n size = sys.getsizeof(d) if size != last: print(f"resize at {n} keys: {size} bytes") last = sizeExample 3 · Counting resizes
import sys
d = {}last = sys.getsizeof(d)resizes = 0for n in range(100): d[n] = n size = sys.getsizeof(d) if size != last: resizes += 1 last = sizeprint("Resizes for 100 keys:", resizes)Resizes for 100 keys: 6
What this code does
- Only a handful of resizes happen for 100 inserts, because capacity grows by multiples.
- The count depends on the Python version, so treat it as a sample.
Each resize rebuilds the indices table, which keeps average lookups at O(1). The sizes printed depend on the Python version.
Sets: the same engine without values
Set is an unordered collection of unique, hashable items with average O(1) membership tests, built on a hash table.
A set keeps only keys. That makes duplicate removal and membership tests fast, because each item is found through its hash.
blocked_ids = {101, 205, 309}print(205 in blocked_ids)print(999 in blocked_ids)
unique = set([3, 1, 3, 2, 1])print(len(unique))Example 4 · Unique customer emails
emails = ["a@x.com", "b@x.com", "a@x.com", "c@x.com", "b@x.com"]unique = set(emails)print(len(unique))print("c@x.com" in unique)print(sorted(unique))3 True ['a@x.com', 'b@x.com', 'c@x.com']
What this code does
set(emails)drops duplicates in one O(N) pass.sortedgives a stable order for display, since sets have none.
Building a set from N items costs O(N). Each later in test is O(1) on average, where a list would scan in O(N).
Next step
Check your understanding
11 quick questions