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

The thread: The structure is a coin flip

A skip list's express lanes are not placed where the keys need them; they are placed where the coins fell, before a single key was compared. Build it twice and it is two different objects, so one build is an anecdote and the distribution over builds is the result.
level 1level 2level 3level 4level 5key 21search: 8 comparisons, 3 hops26 keys, p = 0.5, seed 2026081057 coin flips decided the shape When the algorithm flips a coin

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.

 share of nodespredictedlevel 149.68% · 50.00%level 225.29% · 25.00%level 312.52% · 12.50%level 46.24% · 6.25%level 53.08% · 3.13%level 61.64% · 1.56%level 70.79% · 0.78%level 80.34% · 0.39%20,000 nodes, p = 0.5, seed 5150worst departure 0.32 points When the algorithm flips a coin

The height is a distribution, and the coin is a parameter

A skip list over 2,048 keys is described as being about log₂ n levels tall. Across two hundred builds of exactly those keys its height ranged from 9 to 19. The number in the description is the mean of something, and choosing the coin is choosing which something.

 46810120.010.1bits per element (m / n)false-positive ratemeasured(1 − e^(−kn/m))^kfrom the bits set60,000 absent-key queries per point, seed 80800 false negatives at every size When the algorithm flips a coin

A filter that is allowed to be wrong

A Bloom filter holding four thousand keys in five thousand bytes answers membership in four memory probes and gets 1.14% of its negative answers wrong. It never gets a positive one wrong. That asymmetry is the whole design, and the rate it makes errors at is a third quantity beside the operation count and the space.

 root, priority 0.9651.00.0prioritykey24 keys, sorted insertion, seed 20260810height 8 against an ideal of 4 Structures

The priority nobody supplied

Insert 4,096 sorted keys into a binary search tree and it reaches height 4,095, costing 8,386,560 comparisons to build. Give every key a second, random key and keep the tree heap-ordered on that instead, and the same insertion reaches height 26 for 32,750 comparisons. Nothing detected the imbalance, and nothing rebalanced.

 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 When the algorithm flips a coin

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.

 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 When the algorithm flips a coin

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.

 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) When the algorithm flips a coin

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.

All threads