Module 9
Hashing & hash maps
The beta engine answers store.series("MSFT") and cache.get("MSFT", "SPY") in constant time, no matter how many tickers or pairs it holds. The machinery behind that is hashing: turn the key into a number, turn the number into an array index, and jump straight there — no searching. This module walks the whole pipeline, because every map in the service (and most maps in all software) stands on it.
Step 1 — every object can produce an int fingerprint. String.hashCode() is a polynomial over the characters: h = s[0]·31ⁿ⁻¹ + s[1]·31ⁿ⁻² + … + s[n−1], computed left to right as h = 31·h + c. Same characters, same number — every time.
Step 2 — the number picks a bucket. A HashMap keeps an array of N buckets, N always a power of two. It first spreads the hash — h ^ (h >>> 16), folding the high bits into the low ones — then masks: index = (N − 1) & h. For a power of two, that bit-mask is exactly “h mod N” done in one cycle. One multiply-free mask, and you're standing at the right bucket.
Step 3 — collisions are normal, equals settles them. There are only 2³² fingerprints for infinitely many keys, so different keys sometimes share a bucket. Each bucket holds a short chain of entries; lookup walks it, comparing stored hashes first and calling equals only on hash matches. If a chain grows past 8, the bucket converts to a red-black tree (worst case O(log n) instead of O(n)); when the map passes ~75% full it doubles the array and redistributes every entry.
Step 4 — the contract. Lookup is hash first, equals second — so equal keys must produce equal hashes, or the map searches the wrong bucket and swears a present key is absent. This is exactly why the engine uses records for keys: equals and hashCode are generated from the same component list and can never disagree.
🎛 Hash map lab
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
Click any stored key to run a lookup against it. Orange buckets hold a collision chain (a real HashMap would treeify a chain past 8).
size
0
load factor
0.00
collision buckets
0
longest chain
0
Real Java arithmetic: String.hashCode(h = 31·h + c, 32-bit), the record-style combine (31·hash(ticker) + hash(baseline)), HashMap's bit-spread and power-of-two mask. The sabotage toggle replaces the string hash with the first character code — the map still works (equals rescues correctness), it just degrades toward a linked list. Educational tool — not investment advice.
Worked example — where does MSFT/SPY land?
Hash the ticker, character by character (M=77, S=83, F=70, T=84):
h = 0 h = 31·0 + 77 = 77 // M h = 31·77 + 83 = 2470 // S h = 31·2470 + 70 = 76640 // F h = 31·76640+ 84 = 2375924 // T → "MSFT".hashCode() = 2375924
Same recipe gives "SPY".hashCode() = 82332. The record key combines its components the same way:
PairKey("MSFT","SPY") → 31 · 2375924 + 82332 = 73735976 (conceptually)
spread : 73735976 ^ (73735976 >>> 16) // fold high bits down
index : spread & (16 − 1) // 16 buckets → keep low 4 bitsTwo lookups and a mask — the pair's aligned series is found without comparing against a single other key. The lab above runs this exact arithmetic live for any pair you insert, shows the binary low bits, and lets you shrink the table or sabotage the hash to watch collisions pile up.
In the beta service
The pair cache's key is a two-component record — value-based equality and hashing, generated by the compiler, immune to the delimiter collision a concatenated string would invite:
// PairCache.java — value-based key: record equals/hashCode compare the
// two fields directly, so no string encoding exists to collide (a
// concatenated "T|B" key would conflate {"A|B","C"} with {"A","B|C"})
private record PairKey(String ticker, String baseline) {
}And the cache itself is a LinkedHashMap — plain HashMap hashing for O(1) lookups, plus a doubly-linked list threaded through the entries. In access order, that list is the LRU eviction order Module 5 covered: hashing finds the entry instantly; the links remember who was used least recently. Two data structures, one object.
Upstream, PriceStoremaps normalized ticker strings to series. That's why Module 1's compact constructor upper-cases tickers before the record exists — "msft" and "MSFT" must be the same key by the time hashing sees them. Normalize at the boundary, and every map downstream simply works.
Things to try
- • Insert all five preset pairs at 16 buckets, then shrink to 4 — watch the same keys redistribute and chains form.
- • Flip on the sabotaged hash (first letter only) — SPY/MSFT and similar keys now pile into the same buckets. Same map, same keys, ruined distribution.
- • Insert the same pair twice — the second insert is a hit, not a duplicate: hashing found the bucket, equals matched the key.
- • Push the load factor past 0.75 and read the resize note — that's the moment a real HashMap doubles its table.
- • Look a key up and count the equals calls — one per chained entry in the bucket, and no more.