Probe displacement at load 0.85, 435 keys in 512 slots

Probe displacement at load 0.85, 435 keys in 512 slots

How far each key sits from the slot it hashed to, under plain linear probing and under Robin Hood. The means are identical — 2.384 both times, and they cannot differ, because the total displacement is decided by the hash and Robin Hood only decides who bears it. The worst case falls from 48 probes to 12, and the variance from 36.94 to 7.16. A table reported by its average lookup cost would show no difference at all between these two.

Drawn at 700 × 400, wide on the page. Everything above is what displacement-spread returns with no arguments; the caption is the generator's own, computed from the numbers in the drawing rather than written beside it.

2 essays call displacement-spread. The drawing above is what it returns with no arguments at all; every call below passes it something, because a placement that passes nothing draws whichever member of the family the generator happens to default to rather than the one its essay argues about — which is what optcheck and figfill exist to catch.