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

Hash family — where it appears

A set of hash functions one is drawn from at random, which is what makes a guarantee about collisions a statement anybody can rely on. Drawing from it at random is what stops an adversary aiming at the function, and a single fixed function has no such defence however good it looks.

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

hash rowh1h2h3h4h1 → cell 30: 10,433h2 → cell 29: 10,624h3 → cell 19: 10,575h4 → cell 4: 10,895key 0 occurred 9,579 times · the minimum of the four is 10,433 · over by 854the additive bound at this width is e/w × N = 5,0974×32 counters · 4,096 bits · Zipf s = 1.1exact would take 162,288 bits

A count that is never under

The Count-Min sketch holds four rows of counters and answers how often a key occurred. Its error is one-sided with no probability attached — the estimate is never below the truth on any stream — and the probabilistic half of its guarantee is only about how far above.

streaming · Sketch average 8.001,0242,048bucket, 0 to 255keys in the bucketthe low bits · keys built for this hashworst bucket 2,048 against 8.0

A hash is a family, not a function

Two thousand and forty-eight keys into two hundred and fifty-six buckets. Under a hash that takes the low bits of the key, all 2,048 land in bucket zero and 255 buckets are empty. Under a multiplier drawn at random, the worst bucket holds 11. The keys are the same keys, and they are the multiples of the table size.

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 +1−1keys, most frequent firstΣ s(x)·f(x) = 9,034squared: 81,613,156true F2: 36,931,352121.0% outa polynomial of degree 4 · cash-register model · counts exactone register, 32 bits

The estimate that squares the stream

The length of a stream is a counter and the number of distinct keys is a register bank. The sum of the squared frequencies has nothing obvious to count — and one number, one sign per key, and a squaring get within 4% of it in a fortieth of the space.

streaming · Moment 1 coefficient13 members2 coefficients169 members3 coefficients2,197 members4 coefficients28,561 members1 key2 keys3 keys4 keys5 keysexact92% gone99% gone100% gone100% goneexactexact92% gone99% gone100% goneexactexactexact92% gone99% goneexactexactexactexact92% goneevery member walked · GF(13) · no tolerance and no seeddegree 1, 2, 3, 4

The independence an estimator spends

Every sketch's analysis begins by assuming a truly random hash, and nobody comes back to that line. Independence has a degree, the degree is enumerable over a small field, and an estimator's mean and its variance spend different amounts of it.

randomness · Moment 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 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.

Hash functionUniversal hashingBucket loadEstimatorIndependence assumptionk-wise independenceMeasured countRandom bitsAdversarial inputBloom filterClosed formDerandomisation

All concepts