Expert · Module 23 · Lesson 3 of 4
Cache-friendly hash tables
Open addressing keeps a whole probe run inside one array, often inside one cache line. See what clustering, group probing, tombstones and load factor do to that run.
By the end you can
- Trace a linear-probing run and count the cache lines it touches
- Explain how probing by groups compares many slots with one load
- Predict how load factor and deletions lengthen probe sequences
Builds on Collisions: when two keys want the same slot, Resizing and load factor, Caches: why neighbors are fast.
01 · A question first
Two hash tables hold the same entries. One stores them in one array and probes neighbors; the other chains to separately allocated nodes. Both are O(1) expected, yet the chained one can be several times slower on the same machine. What is the array layout buying?
Make a guess before you read on.
02 · The idea
Members only
Unlock the full lesson
This lesson is part of the membership. Join to read it in full, along with every other premium deep dive.
What's inside
- One array, no pointers
- What the trace counted
- Clustering, and why runs get long
- Robin Hood equalizes the run
- Probing a group at a time
- Deletion is where open addressing gets subtle
- Resizing without losing the locality
- Where this shows up
03 · Practice
Something wrong with this lesson? Report a problem