Hash table
In short: A hash table (dict in Python) finds a key by its hash: the hash says which slot in the table to look in, so lookup and insertion are O(1) on average.
Problem
The price cache slows down
The product page reads its price from a cache: an SKU → price table that the program keeps in memory. Someone wrote their own PriceTable, with a hash function that is "fast": only the first letter of the SKU.
cache = PriceTable(lambda key: ord(key[0]))With 20 products in the test it flies. With the real catalog the page crawls, and the profiler points at get. With 1000 products, each written and read once, the table makes 1,000,000 key comparisons: a thousand per product. A hash table should make one or two.
Every SKU starts with "S". What is happening inside?
The idea
Buckets, hash and the bucket number
In the lesson "Hash codes and hash functions" you saw the table from the outside. Inside it is three things:
- an array of buckets;
- a hash function that turns the key into an integer;
- the bucket number = hash % number of buckets. So every key has exactly one place where you look for it.
Two keys with the same bucket number are a collision. Here collisions live in a chain: every bucket is the start of a linked list of key → value pairs.
keys = [1007, 2043, 3010, 4051]buckets = 8for key in keys: h = hash(key) index = h % buckets print(f"{key} -> {h} -> bucket {index}")Step by step, in words
- Four keys (order numbers) and eight empty buckets, numbered 0 to 7.
- hash(1007) is the number itself, 1007. The remainder when divided by 8 is 7: that is the bucket.
- 2043 gives bucket 3.
- 3010 gives bucket 2.
- 4051 is also in bucket 3: a collision. Here it is drawn as a chain, as in Java. A dict in CPython looks for another free place instead.
- Looking up 4051: the same number, the same bucket 3. == with 2043: no. With 4051: yes.
get computes the bucket and walks only its chain. If the chains are short, that is O(1), however many keys there are.
See it
Your own table
The hash function for an SKU is the same as Java's hashCode of a string: 31 · h + char for every character. At the end the sign is dropped, so the number is not negative:
def sku_hash(key): h = 0 for c in key: h = (31 * h + ord(c)) & 0xFFFFFFFF return h & 0x7FFFFFFF& 0xFFFFFFFF keeps it in 32 bits at every step, like overflow does in Java. That way the hash is the same as in the other languages.A pair is a node with a key, a price and an arrow to the next one in the chain:
class Entry: def __init__(self, key, price, next_entry): self.key = key self.price = price self.next = next_entryThe table gets its hash function from outside, so you can compare two of them. compares counts the key comparisons:
class PriceTable: def __init__(self, hash_fn): self.hash = hash_fn self.buckets = [None] * 4 self.size = 0 self.compares = 0
def index(self, key): return self.hash(key) % len(self.buckets)
def put(self, key, price): i = self.index(key) e = self.buckets[i] while e is not None: self.compares += 1 if e.key == key: e.price = price return e = e.next self.buckets[i] = Entry(key, price, self.buckets[i]) self.size += 1 if self.size > len(self.buckets) * 3 // 4: self.resize()
def resize(self): fresh = [None] * (len(self.buckets) * 2) for head in self.buckets: e = head while e is not None: i = self.hash(e.key) % len(fresh) fresh[i] = Entry(e.key, e.price, fresh[i]) e = e.next self.buckets = fresh
def get(self, key): e = self.buckets[self.index(key)] while e is not None: self.compares += 1 if e.key == key: return e.price e = e.next return Noneputwalks the chain of the bucket. If the key is there, it changes the price. If not, it puts a new pair at the front of the chain: that needs no walk.getwalks the same chain and stops at the key.
Try it
Fill in
The bucket number:
return self.hash(key) % You divide by the number of buckets. The remainder is from 0 to number of buckets − 1, exactly the indexes of the array.
The idea
Load factor and growing
The more pairs, the longer the chains. The ratio pairs / buckets is called the load factor. Here, once it goes above 3/4, the table makes twice as many buckets.
The buckets are not copied one to one. The bucket number is hash % number of buckets, and that number has changed. So resize walks every pair and computes its bucket again: this is rehashing. Doubling from 4 to 8, a key from bucket b goes to b or to b + 4, and the chains split.
def index(self, key): return self.hash(key) % len(self.buckets)
def put(self, key, price): i = self.index(key) e = self.buckets[i] while e is not None: self.compares += 1 if e.key == key: e.price = price return e = e.next self.buckets[i] = Entry(key, price, self.buckets[i]) self.size += 1 if self.size > len(self.buckets) * 3 // 4: self.resize()
def resize(self): fresh = [None] * (len(self.buckets) * 2) for head in self.buckets: e = head while e is not None: i = self.hash(e.key) % len(fresh) fresh[i] = Entry(e.key, e.price, fresh[i]) e = e.next self.buckets = freshStep by step, in words
- A price cache with 4 buckets. The bucket of a key is its hash % 4.
- SKU-1003: 1091696434 % 4 = 2. SKU-1001: % 4 = 0. Empty buckets: no comparisons.
- SKU-1007 also lands in bucket 2: a collision. put compares it with SKU-1003 (not the same key) and puts it at the front of the chain.
- SKU-1005 joins SKU-1001 in bucket 0. Now there are 4 pairs, more than 3/4 of 4 buckets: the chains are getting long.
- resize makes 8 buckets. Every key is counted again with % 8: it stays at its number or moves 4 up.
- The new table: every chain is one pair long, so a get makes one comparison. Resizing costs n, but it happens rarely.
cache = PriceTable(sku_hash)cache.put("SKU-1003", 24.9)cache.put("SKU-1001", 12.5)cache.put("SKU-1007", 8.99)cache.print_buckets()print("---")cache.put("SKU-1005", 45.5)cache.print_buckets()0: SKU-10011:2: SKU-1007 SKU-10033:---0: SKU-10011:2: SKU-10033:4: SKU-10055:6: SKU-10077:Growing costs as much as the number of pairs. But it happens rarely: at 4, 8, 16… pairs, like the growing array in amortized complexity. On average put stays O(1).
Try it
How many buckets?
The table starts with 4 buckets. Seven products go in one after another:
cache = PriceTable(sku_hash)caps = []for n in range(2001, 2008): cache.put(f"SKU-{n}", 10) caps.append(len(cache.buckets))print(" ".join(str(c) for c in caps))The limit is 3/4 of the buckets. With 4 buckets it is 3: the fourth product goes over it and the buckets become 8. With 8 the limit is 6: the seventh goes over it and they become 16.
The idea
A bad hash: the table becomes a list
Back to the cache. The "first letter" hash gives 83 (the code of "S") for every SKU. 83 % 4, 83 % 8, 83 % 1024: with any number of buckets the number is the same. All pairs are in one chain, and the table is a linked list where every put and every get walks through all of them.
Growing does not help: it splits chains only when the keys have different hashes. A hash function must depend on the whole key and scatter close keys (SKU-10000, SKU-10001) far from each other.
def compares(cache, n): for i in range(n): cache.put(f"SKU-{10000 + i}", 1 + i) for i in range(n): cache.get(f"SKU-{10000 + i}") return cache.comparesprint(f"first letter: {compares(PriceTable(lambda key: ord(key[0])), 1000)}")print(f"whole SKU: {compares(PriceTable(sku_hash), 1000)}")first letter: 1000000whole SKU: 2593Run both tables in the browser:
- Hash of the whole SKU
O(n) - Hash of the first letter
O(n²)
| Algorithm | n = 10 | n = 1,000 | n = 100,000 |
|---|---|---|---|
| Hash of the whole SKU | 10 | 2,593 | 211,990 |
| Hash of the first letter | 100 | 1,000,000 | ≈ 10,000,000,000 |
With 1000 products the lazy hash makes 1,000,000 comparisons, and the hash of the whole SKU makes 2593: under three per product. The lazy one is O(n) per operation and O(n²) in total: n products, each written and read once, make exactly n² comparisons.
More precisely, if you are curious
Open addressing (linear probing). Instead of chains, every pair lives in the array itself. If slot hash % n is taken, you try the next one, then the one after, until you find a free slot or the key. get follows the same path and stops at an empty slot. The upside is that everything is in one array and the processor reads it in order. The downsides: taken slots gather into clusters and every cluster grows faster and faster, so the table must stay emptier (it grows already at about half or 2/3). Removing cannot just clear the slot, because that would cut the path to the keys after it: it leaves a "deleted" mark.
What the languages do:
- Java
HashMap: chains. The number of buckets is a power of 2 (16 at first), load factor 0.75. The high bits are mixed into the hash (h ^ (h >>> 16)), because with a power-of-2 mask only the low bits would count otherwise. A chain with more than 8 pairs becomes a red-black tree if there are at least 64 buckets (otherwise the table grows first). So even with many collisions a lookup is O(log n), not O(n). - C#
Dictionary<TKey, TValue>: also chains, but in arrays:_bucketsholds the number of the first pair, and the pairs in_entrieshave anextindex. The number of buckets is a prime (3, 7, 17, 37, 89…), and it grows when the array of pairs is full. There is no tree like in Java. Against deliberate collisions it relies on string hashes that differ on every run. - Python
dict: open addressing, but not linear probing: the next slot is computed by a formula that also uses the high bits of the hash. The table is a power of 2 and grows once it is more than 2/3 full. The pairs live in a separate dense array in insertion order, and the table holds only indexes into it. That is whydictkeeps insertion order (guaranteed since Python 3.7). - JavaScript
Map: the specification requires iteration in insertion order and lookups that are on average better than linear, but does not say how. V8 uses an ordered hash table: buckets with chains, and the pairs live in an array in insertion order. JavaScript gives no hash of your own for objects: an object key is compared by reference.
Try it
Find the bug
Someone rewrote resize. The four products go in, but two of them are later "missing":
def resize(self): fresh = [None] * (len(self.buckets) * 2) for head in self.buckets: e = head while e is not None: i = self.hash(e.key) % len(self.buckets) fresh[i] = Entry(e.key, e.price, fresh[i]) e = e.next self.buckets = freshcache = PriceTable(sku_hash)cache.put("SKU-1003", 24.9)cache.put("SKU-1001", 12.5)cache.put("SKU-1007", 8.99)cache.put("SKU-1005", 45.5)p = cache.get("SKU-1003")print(f"SKU-1003: {'none' if p is None else p}")p = cache.get("SKU-1001")print(f"SKU-1001: {'none' if p is None else p}")p = cache.get("SKU-1007")print(f"SKU-1007: {'none' if p is None else p}")p = cache.get("SKU-1005")print(f"SKU-1005: {'none' if p is None else p}")SKU-1003: 24.9SKU-1001: 12.5SKU-1007: noneSKU-1005: noneWhich line has the bug?
Pick the line with the bug.
The bucket is computed with the old number of buckets (4), and get later looks with the new one (8). A key with hash % 8 = 4 sits in bucket 0, but is looked for in bucket 4, which is empty. The new bucket must use the length of the new array: % len(fresh).
Exercise
A product stops being sold
Solve this one in your own editor.
Removing from the cache. Add a method remove(key) to PriceTable that removes the pair and returns whether there was one. Be careful: the pair may be first in the chain (then the bucket points to the next one) or in the middle (then the previous pair points to the next one). Put SKU-1001, SKU-1005, SKU-1009 and SKU-1012 with prices €10.5, €11.5, €12.5 and €13.5; after growing to 8 buckets three of them are in bucket 0, and SKU-1009 is in the middle of the chain. Remove SKU-1009 and read all four:
SKU-1001: 10.5SKU-1005: 11.5SKU-1009: noneSKU-1012: 13.5products: 3More tasks
- Linear probing. Write a
ProbeTablewithout chains: when a slot is taken, try the next one. Grow when the table is half full. How many comparisons does it make with 1000 SKUs? - Shrinking. After a sale the cache is left with 10 products and 4096 buckets. When would you shrink the table?
- A better lazy hash. The hash "sum of the character codes" looks at the whole key. Try it with SKU-10000 to SKU-10999. Why are there still many collisions? (Hint: SKU-10019 and SKU-10091.)
Test