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

Maximum load — where it appears

The number of items in the fullest bin when items are assigned to bins, a statistic of one bin rather than of all of them. Two random choices lower it from about log n over log log n to about log log n, while the mean load stays exactly where it was.

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

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 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 independent hashestwo values, h₁ + i·h₂2 choices, load 2+60,41859,9942 choices, load 3+2,2832,3672 choices, load 4+123 choices, load 2+46,45646,2433 choices, load 3+138145262,144 keys and buckets, seededbar length is log(1 + count)

Choices that are not independent

The power of two choices is analysed for choices drawn independently, and computing four independent hashes per key costs four hash evaluations. Compute two and take the choices to be h₁, h₁ + h₂, h₁ + 2h₂ and h₁ + 3h₂, and the choices are about as far from independent as they could be. On a million keys the buckets holding two or more come to 147,536 against 147,367 for four independent hashes, and the busiest bucket holds three either way.

randomness · Randomness 8121620240.000010.00010.0010.01bits a keyfalse-positive ratethe whole filterone block of 512 bitsthe emptier of two 512-bit blocksone block of 1,024 bits2,048 keys · 24 filters a pointdashed: no blocks

Two blocks and the chances they add

Send each key to the emptier of two 512-bit blocks and the busiest block of a filter at sixteen bits a key holds 38 keys instead of 55. The false-positive rate does not move: 0.100% against 0.095%. At eight bits a key it doubles. A lookup cannot tell which block a key went to, so it has to ask both, and asking twice is two chances to be wrong. The repair that tames a hash table's worst bucket buys a filter nothing that a block twice as wide does not.

randomness · Randomness

Named alongside it

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

Two choicesBucket loadHash functionLoad balancingMeasured countTail behaviourConcentrationHash familyRandom bitsRandomised data structureTrade offBalls in bins

All concepts