A family of functions from a universe to is universal if for every pair of distinct keys , where is drawn uniformly from (Carter and Wegman 1979). It is -independent if for every distinct keys and every , , so that the hash values of any keys are independent and uniform (Wegman and Carter 1981).

A sketch’s guarantee is a statement about the random choice of its hash function. The Count-Min bound holds with probability over the draw of , for every input, and its proof uses only the collision probability of pairs of keys, so it holds for any universal family. Other analyses use more: the variance bound of the AMS estimator of uses 4-independence, and the analysis of HyperLogLog assumes a fully random function, whose values on all keys are independent. Implementations such as Redis’s HyperLogLog hash with a fixed function, MurmurHash64A, which belongs to no family. The cheapest universal family, multiply-shift, costs one multiplication per key, and its values on structured keys are far from independent.

The integer families below differ by a factor of about 4 in evaluation cost, from 1.8 to 6.9 ns per key. On 61 million keys taken from the series benchmark, every family gives HyperLogLog, Count-Min and AMS their random-hash accuracy when the keys are already hash values. When the keys are dense integer identifiers , the 2-independent and universal families bias HyperLogLog by to in the median, with a spread of more than 50% across seeds, while the 3- and 4-independent families and MurmurHash3’s finalizer stay within the random-hash error of 0.81%.

Definitions

The definitions are ordered by strength. Let be distinct keys.

  • -approximately universal. for . Multiply-shift is 2-approximately universal.
  • Strongly universal, or 2-independent. is uniform on for . A 2-independent family is universal, and in addition each is uniform. A universal family need not have uniform values: multiply-shift maps 0 to 0 for every .
  • -independent. Any hash values are independent and uniform. A -independent family is -independent for every .
  • Fully random. is uniform over all functions , equivalently -independent. Storing such a function takes bits, so analyses that assume it describe an idealization.

A sketch computes a statistic of its input from the hash values. If the statistic depends on the hash values of at most keys at a time, as an expectation or a variance does, then under a -independent family that statistic takes the same value as under a fully random function. The expected Count-Min overestimate involves pairs, so a universal family gives . The variance of the AMS estimator with is a sum over quadruples of keys, so 4-independent signs give the fully random variance. HyperLogLog’s register values are maxima over all keys that share a register, so their distribution depends on the joint distribution of many hash values at once, and its analysis gives no bound for a family of bounded independence.

Constructions

Keys are -bit integers unless stated, and the output has bits, so . Each construction below is a family; drawing means drawing its parameters once, when the sketch is created. Two sketches that are merged must use the same parameters.

Multiply-shift

In C this is (a * x) >> (w - l) on unsigned w-bit integers. Dietzfelbinger et al. (1997) prove for . The family is not 2-independent, and its values on related keys are related: is determined by shifted by one bit, and the low bits of depend only on the low bits of . An implementation that takes the register index from the low bits of the product (a * x & (m - 1)) therefore assigns registers by alone, whatever is. Its parity bit equals the parity of .

Multiply-add-shift

The scheme is due to Dietzfelbinger (1996), who proves an approximate form of 2-independence for a version with a general modulus. For the power-of-two form above, Thorup (2015, Thm. 3.4) shows that it is exactly 2-independent for -bit keys whenever . For 64-bit keys it needs a 128-bit multiply, which unsigned __int128 provides in GCC and Clang.

Polynomials modulo a prime

For a prime and keys in ,

is -independent with values in (Wegman and Carter 1981). The case , , is the construction of Carter and Wegman. With a Mersenne prime such as or , reduction needs no division; for and a 122-bit product : equals after at most one subtraction of (Thorup 2015). Evaluating a degree polynomial by Horner’s rule costs such multiplications. Mapping to by taking the high bits leaves each value within a factor of uniform.

Simple tabulation

Split a key into characters of bits, , and fill tables of random -bit entries:

Simple tabulation is 3-independent and not 4-independent. Pătraşcu and Thorup (2012) prove that it nonetheless gives Chernoff-type concentration for the number of keys hashing to a bin, constant expected time for linear probing and cuckoo hashing, and min-wise hashing with bounded bias. For 64-bit keys with the tables hold 64-bit words, 16 KiB, half of a 32 KiB L1 data cache.

Functions without a family

MurmurHash3’s 64-bit finalizer fmix64 (Appleby), which alternates three xor-shifts by 33 bits with two multiplications by odd constants, is a bijection on 64-bit words with no randomness. Seeding it, as in fmix64(x ^ seed), gives a set of functions indexed by the seed, but no independence property of that set is known. It is designed for avalanche: flipping one input bit flips each output bit with probability close to 1/2 over random inputs, a property that SMHasher tests empirically.

Strings

A string of characters in is reduced to one value in by evaluating a polynomial at a random point :

Two distinct strings of length at most collide with probability at most over , since their difference is a nonzero polynomial of degree at most , which has at most roots (Dietzfelbinger et al. 1992; Thorup 2015, Sec. 5). With and strings of at most 128 characters the collision probability is below , so composing with a universal function from to gives a function of strings whose collision probability is at most . Java’s String.hashCode evaluates the same polynomial with the fixed point modulo , so it is a single function with no collision guarantee.

Cost

Each function was timed on one core of the benchmark machine, hashing all 60,974,808 keys of the benchmark (64-bit integers) or the 5,843,219 key strings of the first hour (mean length 25.9 bytes), and summing the results so the work cannot be eliminated. The table gives the median of 5 passes.

FunctionKeysns per key
Multiply-shift64-bit integers1.8
Multiply-add-shift, 128-bit parameters64-bit integers2.8
fmix64(x ^ seed)64-bit integers4.1
64-bit integers5.7
Simple tabulation, entries64-bit integers6.3
Cubic polynomial mod 64-bit integers6.9
MurmurHash64Astrings17.5
FNV-1a, 64-bitstrings20.0
String.hashCode (base 31 mod )strings21.6
Seeded polynomial mod , 7-byte charactersstrings28.4
CRC-32 (zlib)strings36.3
Seeded polynomial mod , 1-byte charactersstrings85.0

The integer times include reading the keys sequentially from memory, and the polynomial families include reducing each 64-bit key modulo . Repeated runs differed by up to 20%. The seeded string polynomial costs one dependent 61-bit multiplication per character, so packing 7 bytes into each character, which keeps every character below , cuts its time by a factor of 3; the length of the string is appended as a final character so that strings of different lengths remain distinct polynomials.

What each analysis assumes

StructureIndependence used by the analysisSource
Count-Min sketchPairwise independent rows; the proof uses only the collision probability, so universality sufficesCormode and Muthukrishnan 2005
Count SketchPairwise independent bucket and sign functionsCharikar et al. 2004
AMS estimator of 4-independent signs for ; 2-independent signs give Alon et al. 1999
HyperLogLogFully random hash valuesFlajolet et al. 2007
Linear probing5-independence suffices for constant expected time; some 4-independent families give Pagh et al. 2009, Pătraşcu and Thorup 2010
Linear probing, cuckoo hashing, min-wise hashingSimple tabulation, despite being only 3-independentPătraşcu and Thorup 2012

A separate line of results explains why weak families often behave like fully random ones in practice. Chung, Mitzenmacher and Vadhan (2013) show that if each key of a stream has enough Rényi entropy conditioned on the keys before it, the hash values produced by a 2-universal family are close in statistical distance to independent uniform values, so any analysis that assumes fully random hashing applies up to that distance. Keys that are themselves outputs of a good hash have nearly full entropy. Dense identifiers in order have none: each key is determined by the previous one.

Measured on integer keys

Each family was used to build HyperLogLog, one row of a Count-Min sketch and an AMS estimator over the 60,974,808 distinct keys of the benchmark, with 200 independently drawn functions per family. The keys were presented in two forms. Dense keys are the integers , the index of each page in order of first appearance, which is how a database assigns surrogate keys. Hashed keys are the 64-bit MurmurHash64A values of the key strings, as in the HyperLogLog and Count-Min note. Each key’s count is its number of views in the day, so the Count-Min and AMS inputs are the real frequency vector with and .

Seven hash functions were compared: multiply-shift with the index taken from the high bits and from the low bits, multiply-add-shift with 128-bit parameters, , a cubic polynomial modulo (4-independent), simple tabulation with eight 8-bit characters, and fmix64(x ^ seed).

HyperLogLog

HyperLogLog used registers and Ertl’s estimator, whose standard error under a random hash is .

FamilyDense keys, median errorDense keys, 5th to 95th percentileHashed keys, median errorHashed keys, 5th to 95th percentile
Multiply-shift to to
Multiply-shift, low-bit index to to
Multiply-add-shift to to
to to
Cubic polynomial mod to to
Simple tabulation to to
fmix64(x ^ seed) to to

Under a random hash the 5th and 95th percentiles of the error are ( standard errors).

On hashed keys every family is within the random-hash error. On dense keys the four families with at most 2-independence give median errors of to , and the spread across functions is larger than the bias. Among the 200 multiply-shift functions the estimates range from 0.6% of the true count to 2.01 times it, and the largest estimate of each of the four families is between 1.99 and 2.02 times the true count. The bias is already present after the first keys ( for multiply-shift). The cubic polynomial, tabulation and the MurmurHash3 finalizer are indistinguishable from each other and from the random-hash prediction.

The register loads show why. The statistic of the number of keys per register, divided by its expectation under a random hash, is 0.046 for multiply-shift, 0.13 for multiply-add-shift and 0.023 for on dense keys, against 1.00 for the other three families. The products for are distributed more evenly than independent uniform values.

By the three-distance theorem (Świerczkowski 1958), applied to , the gaps between consecutive values in sorted order take at most three distinct lengths, and unless lies close to a fraction with a small denominator, all three are within a small factor of . The same holds for with , and for the high bits of multiply-add-shift. A register’s value is determined by the smallest hash offset among the keys it receives, and when those offsets are evenly spaced, the smallest is never much larger than the spacing. Registers with small values, which a random hash produces with a fixed probability, then do not occur. In the figure at and , a random hash leaves every register at 5 or above with probability about , and multiply-shift does so for 25 of 32 multipliers. HyperLogLog’s harmonic mean is dominated by the smallest register values, so removing them inflates the estimate. A multiplier close to a fraction with small places the keys near points of the circle instead, leaving most registers empty or nearly so, and produces the underestimates.

Taking the index from the low bits of multiply-shift makes the register assignment , which is independent of the multiplier. On dense keys every register receives exactly keys (), and the error comes from the remaining bits. On keys that are all multiples of , such as identifiers allocated in blocks of 1024, every key falls in register 0 and the estimate is below 0.1% of the true count, as the figure shows with the key set of multiples of 1024.

Count-Min

One Count-Min row of width was evaluated by its mean overestimate over all keys, , divided by , the bound on its expectation for a universal family.

FamilyDense, Dense, Dense, , largest of 200Hashed,
Multiply-shift1.692
Multiply-shift, low-bit index0.996
Multiply-add-shift1.323
1.155
Cubic polynomial mod 1.002
Simple tabulation1.002
fmix64(x ^ seed)1.002

Entries are the mean over 200 functions and the standard deviation across them.

Every family meets the bound in expectation, which is all the analysis requires. The weak families on dense keys differ in the spread across functions at , where each cell receives about 233 keys: one multiply-shift function of the 200 has a mean error 69% above , while no function of the three stronger families exceeds it by more than 0.2%. With the index taken from the low bits, the row’s assignment of keys to cells does not depend on the multiplier at all, so the 200 functions give the same error, and the failure probability of the guarantee, which is a probability over the choice of function, no longer describes it.

AMS

The AMS estimator with signs taken from the top bit of each hash value estimates by . Under fully random signs, has mean 1 and standard deviation on this frequency vector.

FamilyDense, meanDense, standard deviationHashed, meanHashed, standard deviation
Multiply-shift1.101.020.940.98
Multiply-shift, low bit1.8100.920
Multiply-add-shift0.961.041.091.31
1.031.210.931.15
Cubic polynomial mod 1.001.030.941.01
Simple tabulation0.870.920.990.93
fmix64(x ^ seed)1.011.120.971.04

With 200 functions the bootstrap standard error of each standard deviation is 0.05 to 0.11, and the measured values lie within 2.6 such errors of 1.076 in both directions. The 2-independent families, for which the variance bound does not apply, are not more spread than the 4-independent polynomial on this frequency vector. The exception is the low bit of multiply-shift, which equals the parity of the key, so every multiplier gives the same : on dense keys for all 200 functions, and on hashed keys 0.92.

Measured on string keys

The HyperLogLog and Count-Min note found that Java’s String.hashCode underestimates the number of distinct page titles by 4.1% for the day, at a standard error of 0.81%, and in each of the 24 hours by to . Two further measurements locate the cause. Following hashCode with MurmurHash3’s 32-bit finalizer, a bijection that preserves its collisions, gives a mean error of over the 24 hours (standard deviation 0.70%), so the collisions of hashCode are not the source of the bias; the distribution of its bits is. The seeded polynomial modulo followed by , with 8 random seeds, gives a mean error of and a standard deviation of over the 192 hour and seed combinations, consistent with an unbiased estimator; the 7-byte-character version gave a mean of and a standard deviation of 0.86% over 8 seeds on the first hour. MurmurHash64A, unseeded, gives and over the 24 hours.

Comparing families on structured keys

¼½124estimate ÷ n (log scale)rms errormult-shift60%mult-shift low66%mult-add-shift58%(ax+b) mod p64%cubic mod p3.4%tabulation3.0%fmix323.3%
0.00.10.20.30.40.5456789101112131415register valuefraction

With multiply-shift, the median estimate over 32 seeds is off by +28.5% and the rms error is 60.0%, against 1.04/√m = 3.25%. A random hash leaves all 1024 registers at 5 or above with probability about one in 166 million; 25 of the 32 seeds here do. Within twice the random-hash error: cubic polynomial mod p, simple tabulation, fmix32.

Simulation in the browser: 32-bit versions of the hash families feed a HyperLogLog sketch with m = 1024 registers and Ertl's estimator, 32 independent seeds per family. The keys are integers, not the pageview data; scrambled IDs are 0, …, n − 1 passed through a fixed invertible mixing function.

The figure runs the seven families in their 32-bit forms on three key sets, with registers and 32 random functions per family. On dense identifiers the upper four rows reproduce the bias measured on the benchmark at a smaller scale. Multiples of 1024 send every key to one register under multiply-shift with the low-bit index. Scrambled identifiers, the dense keys passed through a fixed invertible mixing function before hashing, put every family back within twice the random-hash error, which is the high-entropy case of Chung, Mitzenmacher and Vadhan. The histogram shows the register values of the median function against their distribution under a random hash.

Consequences for implementations

If the keys entering a sketch are themselves outputs of a strong hash, as when a system stores a 64-bit fingerprint per row, then a 2-independent family supplies the randomness the guarantee is stated over at a cost of one or two multiplications per key, and every sketch measured above behaves as its analysis predicts. If the keys can be structured, as identifiers, timestamps, addresses or offsets often are, HyperLogLog needs a function whose output on those keys is close to independent: on the benchmark the 4-independent polynomial, simple tabulation and the MurmurHash3 finalizer all met that condition. Taking the register index or the Count-Min cell from the low bits of a multiplicative hash removes the dependence on the random parameter, and with it the probabilistic guarantee. For strings, a seeded polynomial modulo over 7-byte characters hashed the benchmark’s key strings in 28.4 ns each, against 17.5 ns for MurmurHash64A and 21.6 ns for String.hashCode, and it has a proven collision bound that the unseeded functions lack.