topics / data-caching
Hashing & Collisions
A hash function turns a key into a bucket number, so you can jump straight to it instead of searching. Pile keys into a table, watch them collide, then break the hash on purpose.
Event log
Waiting for traffic…
Collision strategy
Chaining: colliding keys share the bucket as a list. A lookup walks the list, comparing keys one by one.
Hash function
FNV-1amixes every byte of the key, so even “apple” and “apply” land in unrelated buckets.
Table size
Once the load factor passes 0.75, the table doubles and every key is rehashed into it. Changing size by hand does the same.
Keys
A lookup follows the same path as an insert and counts every key it compares on the way.
Break it
Switches to “first letter” and inserts 20 keys that mostly start with s, c or m. Watch one bucket take nearly all of them.
Turns auto-resize off and keeps inserting well past 0.75. Then turn auto-resize back on and watch every key move.