The idea: make open addressing fast and predictable
An open addressing hash table keeps every key in one flat array. A key goes to its home slot; if that slot is taken, it probes further. Plain linear probing is fast on average, but a few unlucky keys end up far from home, and deletes leave tombstones that slow every later search. Two modern designs fix this in different ways. Robin Hood hashing evens out how far keys are from home. Swiss tables add one small control byte per slot and check 16 of them with a single CPU instruction.
The page has two tables, picked with the table menu. Both use the same small hash, hash(k) = k × 40503 mod 65536, split the way Abseil splits it: H1 = hash >> 7 and H2 = hash & 0x7F (the low 7 bits). Real tables use a 64-bit hash; the idea is the same.
Probe sequence length
In linear probing a key with home slot h sits in slot h, h+1, h+2, … The distance from its home is its probe sequence length (PSL): a key at home has PSL 0. A successful search for a key reads PSL + 1 slots. In the Robin Hood table the page writes each key's PSL under it, and the home slot (h) below that. In Demo 1, keys 11, 20 and 29 all have home 8, so they land in slots 8, 9 and 10 with PSL 0, 1 and 2, and find(29) takes 3 probes.
Robin Hood insert: steal from the rich
Insert walks from home and counts its own distance d. At each full slot it compares d with the occupant's PSL. A key with a small PSL is "rich": it is close to home. If the occupant's PSL is smaller than d, the new key takes the slot, and the occupant is picked up and carries on walking with its own distance. The empty slot at the end goes to whoever is in hand.
In Demo 2, 30 (home 4), 12 (home 5) and 17 (home 3) are at home. Then 26 (home 3) arrives. Slot 3 holds 17 with PSL 0, which is not less than d = 0, so 26 walks on. At slot 4, d = 1 and 30 has PSL 0: 30 is richer, so 26 takes slot 4 and 30 continues. 30 does the same to 12 at slot 5, and 12 lands in empty slot 6. Every key ends with PSL 0 or 1. Plain linear probing, drawn underneath with the same keys, puts 26 in slot 6 with PSL 3.
The total distance does not change: swapping two keys moves distance from one to the other. So the mean PSL is the same as in linear probing. What drops is the variance and the maximum: at high load the longest probe stays short, which matters for tail latency.
A miss stops early
Robin Hood keeps a useful order: along a run of full slots, the PSL grows by at most 1 per slot. So a search for x that reaches a slot whose PSL is less than the distance walked can stop: if x were in the table, it would have taken that slot. In Demo 3, find(35) (home 3) stops at slot 5, where 30 has PSL 1 < d = 2: 3 probes. Plain linear probing must scan until it hits an empty slot, which takes 5.
Backward-shift delete: no tombstones
Deleting from linear probing can't just empty the slot: a later search would stop there and miss keys behind it. So plain probing leaves a tombstone (†), which searches skip over and which piles up until the next rebuild. Robin Hood can do better. After emptying the slot it looks at the next key: if its PSL is above 0, it moves back one slot and its PSL drops by 1. It repeats until it finds an empty slot or a key at home (PSL 0). In Demo 4, delete(17) shifts 26, 30 and 12 back one slot each, and all three end at home.
Swiss tables: H1, H2 and control bytes
A Swiss table (Google's Abseil flat_hash_map, 2017) keeps a separate array of control bytes, one per slot. Each byte says: EMPTY (0x80), DELETED (0xFE, a tombstone), or FULL, and then the byte is the key's 7-bit H2 (top bit 0). H1 picks where the search starts; H2 is a tiny fingerprint of the key.
The slots are read in groups of 16. A lookup loads the group's 16 control bytes into one 128-bit register and compares all of them with H2 at once (SSE2 _mm_cmpeq_epi8, then _mm_movemask_epi8 turns the result into a 16-bit mask). Only slots whose bit is 1 have their key compared. Then a second compare with EMPTY: if the group has any empty slot, the key can't be further on and the search stops. If the group is full, the search goes on to the next group of the probe sequence.
Two keys share a 7-bit H2 only 1 time in 128, so a lookup almost never compares a wrong key. When it does, the key compare catches it. In Demo 6, 282 has the same H2 (0x16) and the same group as 26, so find(282) gets one candidate, compares 26 ≠ 282, sees an EMPTY byte and stops: a miss with one key compare.
Full groups and tombstones
In Demo 7, 16 keys fill group 0. Key 42 also starts at group 0, finds no EMPTY byte there, moves to group 1 and is stored in slot 16. Now deleting 20 from group 0 can't write EMPTY: find(42) would then stop in group 0 and miss 42. So the byte becomes DELETED 0xFE. A search treats it like a full slot that never matches, and the next insert can reuse it. Deleting 42 from group 1, which still has empty slots, writes EMPTY: no search ever went past that group. Tombstones are cleared when the table is rebuilt: Abseil rehashes in place when they take too much room.
| Plain linear probing | Robin Hood | Swiss table | |
|---|---|---|---|
| Per-slot extra data | none | PSL (or the stored hash) | 1 control byte |
| Longest probe | grows fast with load | short, low variance | a few groups of 16 |
| Miss | scan to an empty slot | stops at PSL < d | stops at a group with an EMPTY byte |
| Delete | tombstone | backward shift | EMPTY, or DELETED in a full group |
| Max load | about 70% | about 90% | 7/8 (87.5%) |
| Used in | many simple tables | Rust std before 1.36, many C++ libraries | Abseil, Rust hashbrown (std since 1.36), Go 1.24 maps |
Real implementations differ in the details. Abseil and hashbrown start at slot H1 & mask and load any 16 control bytes from there, not aligned groups, and step between windows with a triangular probe. hashbrown uses 8-byte groups and plain integer tricks where SSE2 is missing. Go 1.24 rebuilt its built-in map as a Swiss table with groups of 8 slots, split across many small tables behind an extendible-hashing directory, so growing never copies a huge table at once.
See also Separate Chaining vs Linear Probing for clustering and tombstones in plain probing, and Cuckoo Hashing for another way to bound how far a lookup looks.
What the page leaves out
Real 64-bit hash functions with a per-table seed; growing the table (both tables here stop at 7/8 load instead); storing the hash instead of the PSL; Abseil's unaligned windows, the sentinel byte and the cloned control bytes at the end of the array; in-place rehash to drop tombstones; the ARM NEON and 8-byte portable group code paths; Go's directory of small tables; and iteration order, which Swiss tables randomize.