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

Randomised data structure — where it appears

A structure whose shape is decided by coin flips rather than by the keys it holds. The consequence is that no key set is a bad case for it, and that its cost is a distribution whose spread matters more than its mean.

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

level 1level 2level 3level 4level 5key 21search: 8 comparisons, 3 hops26 keys, p = 0.5, seed 2026081057 coin flips decided the shape

A structure made of coin flips

Insert the same 512 keys into a skip list twice, once sorted and once shuffled, from the same seed, and the two structures are identical — the same 11 levels, the same height for every key, the same silhouette. Nothing about the data reached the layout. The 1,064 coin flips did all of it.

randomness · Randomness 024681,0244,09616,38465,536262,144keys, into as many bucketskeys in the busiest bucketone hashtwo hashes, take the emptierthree hasheslog n / log log nthe average load is 1 at every pointa lookup examines every choice, so two hashes is two probes

The second choice

Two hundred and sixty thousand keys into as many buckets. Under one hash the busiest bucket holds eight; under two, with each key going to whichever of its two is emptier, it holds four. The mean is exactly one in both. Nothing is rearranged afterwards, no key is ever moved, and the whole of the improvement is in a decision taken once, at the moment the key arrives.

randomness · Randomness 0%25%50%75%100%0.20.30.40.450.50.550.60.70.8keys per slotconstructions that failedconstructions that faileddisplacements, scaled to 36840 constructions per point, 256 slots per tablea lookup is two probes, whatever the keys are

An insertion that can fail

Every randomised structure in this field buys an expected cost and accepts a tail. Cuckoo hashing buys a worst case — a lookup examines exactly two slots, for any keys, always — and pays for it in the construction, which can fail outright. On a table of four thousand slots the construction never fails below 0.45 keys per slot and fails nineteen times in twenty above 0.55.

randomness · Randomness 2 halves, ties go left2 choices, ties at randomone choiceload 2 or more14,61015,03717,363load 3 or more2675785,250load 4 or morenone11,236load 5 or morenonenone223load 6 or morenonenone36load 7 or morenonenone2load 8 or morenonenone165,536 keys and buckets, seededbar length is log(1 + count)

The tie that breaks left

Two choices per key, the emptier bucket wins, and when the two are equally full a coin decides. Replace the coin with a rule — split the table into halves and always send a tie to the left one — and on a million keys the buckets holding three or more fall from 9,316 to 4,694, and the busiest bucket drops from four to three. The hashing, the probes and the keys are unchanged, and the rule spends no randomness at all.

randomness · Randomness

Named alongside it

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

Bucket loadMeasured countTrade offTwo choicesConcentrationExpected caseHash functionLoad balancingMaximum loadTail behaviourBinary searchBinary search tree

All concepts