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.
| Function | Keys | ns per key |
|---|---|---|
| Multiply-shift | 64-bit integers | 1.8 |
| Multiply-add-shift, 128-bit parameters | 64-bit integers | 2.8 |
fmix64(x ^ seed) | 64-bit integers | 4.1 |
| 64-bit integers | 5.7 | |
| Simple tabulation, entries | 64-bit integers | 6.3 |
| Cubic polynomial mod | 64-bit integers | 6.9 |
| MurmurHash64A | strings | 17.5 |
| FNV-1a, 64-bit | strings | 20.0 |
String.hashCode (base 31 mod ) | strings | 21.6 |
| Seeded polynomial mod , 7-byte characters | strings | 28.4 |
| CRC-32 (zlib) | strings | 36.3 |
| Seeded polynomial mod , 1-byte characters | strings | 85.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
| Structure | Independence used by the analysis | Source |
|---|---|---|
| Count-Min sketch | Pairwise independent rows; the proof uses only the collision probability, so universality suffices | Cormode and Muthukrishnan 2005 |
| Count Sketch | Pairwise independent bucket and sign functions | Charikar et al. 2004 |
| AMS estimator of | 4-independent signs for ; 2-independent signs give | Alon et al. 1999 |
| HyperLogLog | Fully random hash values | Flajolet et al. 2007 |
| Linear probing | 5-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 hashing | Simple tabulation, despite being only 3-independent | Pă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 .
| Family | Dense keys, median error | Dense keys, 5th to 95th percentile | Hashed keys, median error | Hashed 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.
| Family | Dense, | Dense, | Dense, , largest of 200 | Hashed, |
|---|---|---|---|---|
| Multiply-shift | 1.692 | |||
| Multiply-shift, low-bit index | 0.996 | |||
| Multiply-add-shift | 1.323 | |||
| 1.155 | ||||
| Cubic polynomial mod | 1.002 | |||
| Simple tabulation | 1.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.
| Family | Dense, mean | Dense, standard deviation | Hashed, mean | Hashed, standard deviation |
|---|---|---|---|---|
| Multiply-shift | 1.10 | 1.02 | 0.94 | 0.98 |
| Multiply-shift, low bit | 1.81 | 0 | 0.92 | 0 |
| Multiply-add-shift | 0.96 | 1.04 | 1.09 | 1.31 |
| 1.03 | 1.21 | 0.93 | 1.15 | |
| Cubic polynomial mod | 1.00 | 1.03 | 0.94 | 1.01 |
| Simple tabulation | 0.87 | 0.92 | 0.99 | 0.93 |
fmix64(x ^ seed) | 1.01 | 1.12 | 0.97 | 1.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
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.
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.
How this was measured
The harness sources and outputs are in the
hashing-experimentsdirectory, andrun.shreproduces every number. It reuses the per-key files that the HyperLogLog and Count-Min harness builds from the 24 hourly pageview files of 4 March 2026.
- Integer keys.
fam.creads the 60,974,808 distinct 64-bit key hashes in order of first appearance and the per-key daily view counts. For each of 200 trials and each family it draws parameters from a SplitMix64 stream seeded by the trial and family, hashes either the dense index or the 64-bit key hash, and builds a HyperLogLog sketch with (estimates at , , , and keys), Count-Min rows of width and , the register loads and the AMS sum. The polynomial families reduce 64-bit keys modulo first and shift their 61-bit values left by 3. Simple tabulation uses eight tables of 256 64-bit words.analyze_fam.pyproducesfam_summary.json.- String keys.
strq.chashes each raw key stringdomain_code page_titlewithString.hashCode(base 31 modulo ), the same followed byfmix32, MurmurHash64A, and the seeded polynomial with 8 seeds, and estimates each hour and the day with Ertl’s estimator at (strq.txt).- Cost.
speed.ctimes each function single-threaded, 5 passes over the keys held in memory, and reports the median (speed.txt).check7.cchecks the 7-byte-character polynomial with HyperLogLog on the first hour (check7.txt).- Environment. gcc 13.3 with
-O2 -march=native -fopenmp, Python 3.13.18, on a 4-core Intel Xeon at 2.10 GHz with 15 GB of memory. The 200 trials take about 15 minutes on 4 cores.- The figure. The figure computes everything in the browser with 32-bit versions of the families: multiply-shift with a 32-bit odd multiplier, multiply-add-shift with 64-bit parameters, polynomials modulo , tabulation with four 8-bit characters and
fmix32. Its sketches are tested against an independent NumPy implementation (figure_ref.py,figure_check.py): the register histograms of 63 cases match exactly and the estimates to .
Potentially interesting ideas
- The register floor on the benchmark. The figure measures the smallest register value per function at . The same statistic for the 64-bit families at on the 61 million dense keys was not recorded; it would test whether the floor explains the full bias there, or whether the upper tail of the register distribution also changes.
- Which multipliers underestimate. The gaps between consecutive multiples of modulo are governed by the continued fraction expansion of . A large partial quotient early in that expansion means that is close to a fraction with a small denominator, which should predict the underestimating functions. Correlating each function’s error with its continued fraction was not done.
- AMS with 2-independent signs. The variance of under 2-independent signs can exceed the 4-independent value when the frequency vector is chosen against the family. The pageview frequencies showed no such excess; a constructed input, for example frequencies placed on keys in arithmetic progression, might.
- Twisted and mixed tabulation. These variants add a second round of table lookups to simple tabulation. Their cost per key and their behaviour with HyperLogLog on dense keys were not measured.
Related notes
- Probabilistic data structures, the series index, with the notation and the benchmark stream
- HyperLogLog and Count-Min, the estimators whose inputs are hashed here
- Expectation and concentration, for the Markov and Chebyshev bounds that pairwise and 4-wise independence support