Each key is read by a press that turns it into a number, and a dial keeps only the low bits of that number to choose a bin. Two keys will sooner or later choose the same bin. Watch the office settle it three ways: hang a chain of cards in front of the bin, or send the carriage on to try other bins, one step at a time or in growing strides.
How one key finds its bin, and what happens when the bin is taken. The boxes follow the last card through the office.
Every key in the table: its hash, the low bits the dial keeps, the bin it wanted, the bin it got, and how many looks it takes to find it again. Click a row to look that key up on the bench.
| Key | hashCode | Low bits | Home | Filed in | Probes | What happened |
|---|
On the left, the table as a programmer would draw it. On the right, the average number of looks a successful search costs as the table fills, for each method, from Knuth's analysis; the circle is what this table actually costs now.
The arithmetic. Keys are hashed with Java's String.hashCode, spread with h ^ (h >>> 16) and masked with m − 1, exactly as java.util.HashMap does. The probe sequences, the 0.75 load limit, the doubling and the probe counts are computed, not drawn; the curves are Knuth's formulas for keys hashed uniformly.
The eight fruit and the three absent ones, chosen so that collisions happen early, and the order they arrive in. The table starts at four bins and the bench has room for eight, so after one doubling it fills past 0.75 instead of growing again; that is where the long probe runs show. When it doubles, keys are placed again in the order they first arrived; real tables walk the old array instead.
Deletion, which open addressing needs tombstones for; Java's habit of turning a chain of eight or more into a small tree; Python's perturbed probing; Robin Hood, cuckoo and Swiss tables. And the cost of the hash itself, which for long keys can outweigh every probe.