Probes per insertion against load factor, table of 8,192

Probes per insertion against load factor, table of 8,192

The line is Knuth's closed form for linear probing, integrated over the fill; the points are a table actually filled and counted. They agree to within 2.3% everywhere. At a load factor of 0.5 an insertion averages 1.49 probes; at 0.9 it averages 5.39. The formula that matters for insertion is the unsuccessful-search one, ½(1 + 1/(1−α)²), and using the successful-search form instead is an error that hides at low load and is glaring at high load.

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

21 essays call probe-count. 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.