Algorithms & Data Structures
the bound is a claim, and it is checkable
Concept

Finite size effect — where it appears

Behaviour at measurable sizes that the asymptotic statement does not describe, and which is often the only behaviour anybody will encounter. It is often the only behaviour anybody will encounter, which is why a measured crossover matters more in practice than the class it eventually gives way to.

Named by 5 essays across 4 fields — each of them below, with the objects they name alongside it.

-50%-40%-30%-20%-10%0%10%20%2561,0244,09616,384α = 0.5α = 0.8α = 0.9α = 0.95table size (slots)measured minus formula, relativemean of 6 fills per pointgreen band: within 5% of the formula

A limit is not a prediction

Measured from n = 64 to n = 4,096, this site's hybrid merge sort fits a linear class better than n log n. Measured out to n = 65,536, the ranking reverses. Nothing changed but the range — and this is not a flaw in the method, it is the method finding the exact place where measurement stops being able to help.

bounds · Bound 1234560.000.250.500.75formulameasuredload factor αprobes per insertion8,192 slots, mean of 8 fills, seeds stated in lib/structures.jstwo routes agree to 2.3%

The probe formula nobody checks

The expected number of probes to insert into a hash table under linear probing is ½(1 + 1/(1−α)²). It is quoted constantly, it is correct, and applied to a table of 256 slots at 95% load it overstates the measured cost by nearly half — because it is an asymptotic result and a real table is not asymptotic.

wrong · Distribution 0%25%50%75%100%0.30.40.50.60.70.80.850.90.95keys per slotconstructions that failed2 hashes, 1 slot3 hashes, 1 slot2 hashes, 2 slots2 hashes, 4 slots20 constructions a point, 256 bucketsa lookup reads hashes × slots, whatever the keys

More hashes or wider buckets

A cuckoo table with two hash functions and one slot per bucket cannot be built past about half full. Give it a third hash function and it builds to 0.92. Keep two hashes and give each bucket two slots and it builds to 0.89; four slots, past 0.95. Every shape keeps the worst-case lookup the plain table was built for, and every shape pays for its threshold in a different place.

randomness · Randomness 0.111010010³10³10⁴floor, in countsarrivals in the shard, nround-robin — n^1.02hashed — fit refusedresidual 2.7%slope 5.2 → 1.19k = 32 · 40,000 arrivalsthe table holds 1.33 of a hashed shard's keys and 0.01 of the stream's

A floor with two variables in it

Under round-robin a Space-Saving summary's floor is 0.0203·n^1.018 over a hundred-and-twenty-eight-fold range of shard size, worst residual 2.7%. Under hashing the same measurement has no exponent at all — the local slope runs from n^5.17 to n^1.19 — and a least-squares line through it reports n^1.73 at a 441% residual.

floors · Floor 3579111311.523510positions per key, krate ÷ the independent rateh₁ + i·h₂h₁ + i·h₂, step oddh₁ + i·h₂ + (i³ − i)/6optimal load m·ln 2 / k; one set of hash functions per schemedashed: the account

Two hash values and the keys they copy

A Bloom filter that makes its k bit positions from two hash values, as h₁ + i·h₂, answers yes to 1.6% of absent keys on a 64-bit filter where k independent hashes answer 0.69%. The penalty is not the one expected. With the step forced odd no key ever repeats a bit, while a quarter of independent keys do. What costs the filter is a query whose start and step reproduce a stored key's whole progression, which happens with probability 4n/m², measured to within a few per cent from 64 bits to 4,096. The penalty fades as the filter grows and returns as the hash count rises — 1.13 times at seven positions on 1,024 bits, 5.35 times at thirteen.

randomness · Randomness

Named alongside it

The objects these essays reach for when they reach for this one.

RegimeClosed formHash functionLoad factorHash tableThresholdAsymptotic analysisBloom filterConstructionCrossoverCuckoo hashingCurve fitting

All concepts