An 8-probe budget binds linear probing at load 0.277 for a 1e-3 failure level
Linear probing with an 8-probe budget and a 1e-3 failure level hits its limit at load 0.277, a hash-table study reports. Sizing to that tail instead of the mean takes about 3.25 times the slots of a table run at 0.9.
The Engineer · Build desk
Linear-probing table, slots per key for the same keys: 1.11 when run at load 0.9, rising to 3.61 when sized to the 0.277 binding load, about 3.25 times the slots.
| Measure | Value | As of | Claim |
|---|---|---|---|
| Run at load 0.9 | 1.11 slots per key | 10 | |
| Sized to 0.277 binding load | 3.61 slots per key | 10 |
What happened
- At load 0.90 the measured 99th-percentile cost of an unsuccessful search is 7.39 times the mean, and at 0.95 it is 5.20 times.
- For linear probing under uniform hashing, the post says the textbook mean formula matches the measured mean inside a two-sided 0.15 band.
- For Robin Hood hashing the classical form is off by -0.993 at load 0.99, with an across-seed band of 0.004, and by -0.300 at 0.50.
- The study counts probes and records no timings, across two schemes, 12 seeds per instance, 23 load points up to 0.99 and a fixed table of 65536 slots.
- The post's author re-ran the shipped script at the published commit, and the reports and figure set regenerated byte-identically.
Why it matters
- decision The failure level becomes a sizing input that someone has to own. The solve takes a probe budget and a failure share and returns a maximum load, so capacity planning starts from the cap.
- constraint A sizing rule is scheme-specific. The classical form that fits linear probing's mean misses Robin Hood's, so each scheme needs its own solve before a load target is set.
- exposure A table checked only against the textbook mean can pass every check and still exceed an 8-probe cap on 1e-3 of operations at a load far below 0.9.
A probe budget caps one operation. A mean averages over all of them. The post says the 0.277 figure is not the load at which the mean reaches eight probes [9]. The mean can sit well under eight while a small share of lookups runs past it.
The excerpt does not define "binds". In our reading, the budget binds at the load where the share of operations needing more than eight probes reaches the 1e-3 failure level. Under that reading the sizing procedure runs backward. Fix the budget and the failure share, solve for the maximum load, then size the table.
That solve costs memory. Slots per key is 1/load, so a load of 0.277 means about 3.61 slots per key against 1.11 at 0.9, a ratio of about 3.25 [10]. In our view sizing for the tail is the right tradeoff where eight probes is a hard cap, such as a fixed probe window, and 1e-3 is a failure rate someone has agreed to. Where overflow triggers a resize or a fallback path, the mean still prices the common case.
The evidence is counts. According to the post, every number in the package is an integer probe count, a rate over a named denominator, or a moment derived from integers [7]. The stated reason is that hash-table throughput is dominated by cache lines, prefetchers and page faults, and a stopwatch cannot show a p99. That is a sound choice for this question. It leaves open what eight probes cost in nanoseconds on any given machine.
The reproduction run exited with status 2. No step failed. Four journal gates reported NOT RUN because the exported archive has no .git, and the script labels that "a coordinate of this run, not a finding about the work" [2]. Byte-identical output shows that the shipped code is deterministic [1]. Whether uniform hashing describes your keys has to be tested on your keys.
For 0.277 to transfer, three things have to hold. Your hash function has to behave like the uniform hashing under which the post states its mean check [5]. Your table has to be close enough to the study's fixed 65,536 slots that size does not matter, and the study reports only that one size [8]. And your cap and tolerance have to be eight probes and 1e-3, since the solve changes with both.
The excerpt does not name the paper or its authors, so every figure here is the post's account of it.
What to watch
- The paper itself: the excerpt does not name it, and the full text would show how it defines the binding load and how alpha*(k_max) is computed.
- Binding loads for Robin Hood and for the other five budget steps, which the excerpt does not report.
- A rerun of the probe-count harness with a production hash function and a table size other than 65536.
Clarity's read
What the record supports and how the coverage leans. The claims behind it follow.
Reality
- Evidence66
- Adoption
- Insufficient
- Hype gap+8
- Incentives
- Insufficient
- Confidence60
Claim ledger
Ranked by verification strength, evidence, and original report placement.
- [1]
The post's author ran reproduce.sh from a git archive export of origin/main, and the four spike reports, the nine-file figure set and the manuscript all regenerated byte-identically to the shipped versions.
- [2]
The reproduce script exited with status 2: no step failed, but four gates (numgate, linkgate, pointgate, refgate) reported NOT RUN, with the post attributing the journal gates' result to the export having no .git; the script's output calls this 'a coordinate of this run, not a finding about the work'.
- [3]
At alpha = 0.90 the measured p99 unsuccessful-search cost is 7.39 times the mean; at alpha = 0.95 it is 5.20 times the mean.
- [4]
With a probe budget k_max = 8 and a failure level of 1e-3, the load at which the budget binds for linear probing is alpha*(8) = 0.277.
- [5]
For linear probing under uniform hashing, the textbook mean formula agrees with the measured mean in 23 of 23 + 7 cells inside a two-sided 0.15 band.
- [6]
For Robin Hood hashing the classical form is off by -0.993 at alpha = 0.99, with an across-seed band of 0.004, and already off by -0.300 at alpha = 0.50.
- [7]
Every number in the package is a count of probes as an exact integer, a rate over a named denominator, or a moment derived from integers, with no timings; the post says throughput is dominated by cache lines, prefetchers and page faults, so a p99 cannot be seen through a stopwatch.
- [8]
The study uses four instruments with 60, 252, 288 and 276 cells, two schemes (linear probing and Robin Hood), 12 seeds per instance at a fixed table size m = 65536, and 23 load points up to alpha = 0.99, with no timings anywhere.
- [9]
The load at which the 8-probe budget binds for linear probing is not the load at which the mean reaches eight probes.
- [10]
Sizing a linear-probing table to the 0.277 binding load takes about 3.25 times the slots of a table run at load 0.9 for the same keys (3.61 slots per key against 1.11).
Get this ledger inside ChatGPT. Ask about any of our stories and the answer brings its figure, each claim’s verdict and the sources. Free, no account.
Sources
1 independent publisher whose own reporting we read for this story.
- dev.toYour hash table runs at 0.9. Its probe budget binds at 0.277. The load factor is not the tail.
1 article · October 13, 2026
Topics and entities
Follow any of these and your For You feed starts watching them — no settings page required.
Topics
- Tail LatencyFollow
- Open addressingFollow
- Hash tablesFollow
- Reproducible ResearchFollow