Universal hashing

In mathematics and computing, universal hashing (in a randomized algorithm or data structure) refers to selecting a hash function at random from a family of hash functions with a certain mathematical property (see definition below). This guarantees a low number of collisions in expectation, even if the data is chosen by an adversary. Many universal families are known (for hashing integers, vectors, strings), and their evaluation is often very efficient. Universal hashing has numerous uses in computer science, for example in implementations of hash tables, randomized algorithms, and cryptography.
Introduction.
Assume we want to map keys from some universe formula_1 into formula_2 bins (labelled formula_3). The algorithm will have to handle some data set formula_4 of formula_5 keys, which is not known in advance. Usually, the goal of hashing is to obtain a low number of collisions (keys from formula_6 that land in the same bin). A deterministic hash function cannot offer any guarantee in an adversarial setting if the size of formula_1 is greater than formula_8, since the adversary may choose formula_6 to be precisely the preimage of a bin. This means that all data keys land in the same bin, making hashing useless. Furthermore, a deterministic hash function does not allow for "rehashing": sometimes the input data turns out to be bad for the hash function (e.g. there are too many collisions), so one would like to change the hash function.
The solution to these problems is to pick a function randomly from a family of hash functions. A family of functions formula_10 is called a universal family if, formula_11.
In other words, any two keys of the universe collide with probability at most formula_12 when the hash function formula_13 is drawn randomly from formula_14. This is exactly the probability of collision we would expect if the hash function assigned truly random hash codes to every key. Sometimes, the definition is relaxed to allow collision probability formula_15. This concept was introduced by Carter and Wegman in 1977, and has found numerous applications in computer science (see, for example ). If we have an upper bound of formula_16 on the collision probability, we say that we have formula_17-almost universality.
Many, but not all, universal families have the following stronger uniform difference property:
Note that the definition of universality is only concerned with whether formula_23, which counts collisions. The uniform difference property is stronger.
An even stronger condition is pairwise independence: we have this property when formula_18 we have the probability that formula_30 will hash to any pair of hash values formula_31 is as if they were perfectly random: formula_32. Pairwise independence is sometimes called strong universality.
Another property is uniformity. We say that a family is uniform if all hash values are equally likely: formula_33 for any hash value formula_34. Universality does not imply uniformity. However, strong universality does imply uniformity.
Given a family with the uniform distance property, one can produce a pairwise independent or strongly universal hash family by adding a uniformly distributed random constant with values in formula_22 to the hash functions. (Similarly, if formula_2 is a power of two, we can achieve pairwise independence from an XOR universal hash family by doing an exclusive or with a uniformly distributed random constant.) Since a shift by a constant is sometimes irrelevant in applications (e.g. hash tables), a careful distinction between the uniform distance property and pairwise independent is sometimes not made.
For some applications (such as hash tables), it is important for the least significant bits of the hash values to be also universal. When a family is strongly universal, this is guaranteed: if formula_14 is a strongly universal family with formula_38, then the family made of the functions formula_39 for all formula_40 is also strongly universal for formula_41. Unfortunately, the same is not true of (merely) universal families. For example, the family made of the identity function formula_42 is clearly universal, but the family made of the function formula_43 fails to be universal.
UMAC and Poly1305-AES and several other message authentication code algorithms are based on universal hashing.
In such applications, the software chooses a new hash function for every message, based on a unique nonce for that message.
Several hash table implementations are based on universal hashing.
In such applications, typically the software chooses a new hash function only after it notices that "too many" keys have collided; until then, the same hash function continues to be used over and over.
(Some collision resolution schemes, such as dynamic perfect hashing, pick a new hash function every time there is a collision. Other collision resolution schemes, such as cuckoo hashing and 2-choice hashing, allow a number of collisions before picking a new hash function). A survey of fastest known universal and strongly universal hash functions for integers, vectors, and
strings is found in.
Mathematical guarantees.
For any fixed set formula_6 of formula_45 keys, using a universal family guarantees the following properties.
As the above guarantees hold for any fixed set formula_6, they hold if the data set is chosen by an adversary. However, the adversary has to make this choice before (or independent of) the algorithm's random choice of a hash function. If the adversary can observe the random choice of the algorithm, randomness serves no purpose, and the situation is the same as deterministic hashing.
The second and third guarantee are typically used in conjunction with rehashing. For instance, a randomized algorithm may be prepared to handle some formula_60 number of collisions. If it observes too many collisions, it chooses another random formula_13 from the family and repeats. Universality guarantees that the number of repetitions is a geometric random variable.
Constructions.
Since any computer data can be represented as one or more machine words, one generally needs hash functions for three types of domains: machine words ("integers"); fixed-length vectors of machine words; and variable-length vectors ("strings").
Hashing integers.
This section refers to the case of hashing integers that fit in machines words; thus, operations like multiplication, addition, division, etc. are cheap machine-level instructions. Let the universe to be hashed be formula_71.
The original proposal of Carter and Wegman was to pick a prime formula_72 and define
where formula_74 are randomly chosen integers modulo formula_75 with formula_76. (This is a single iteration of a linear congruential generator.)
To see that formula_77 is a universal family, note that formula_54 only holds when
for some integer formula_80 between formula_81 and formula_82. Since formula_72, if formula_84 their difference formula_85 is nonzero and has an inverse modulo formula_75. Solving for formula_87 yields
There are formula_89 possible choices for formula_87 (since formula_91 is excluded) and, varying formula_80 in the allowed range, formula_93 possible non-zero values for the right hand side. Thus the collision probability is
Another way to see formula_14 is a universal family is via the notion of statistical distance. Write the difference formula_96 as
Since formula_98 is nonzero and formula_87 is uniformly distributed in formula_100, it follows that formula_101 modulo formula_75 is also uniformly distributed in formula_100. The distribution of formula_104 is thus almost uniform, up to a difference in probability of formula_105 between the samples. As a result, the statistical distance to a uniform family is formula_106, which becomes negligible when formula_107.
The family of simpler hash functions
is only "approximately" universal: formula_109 for all formula_110. Moreover, this analysis is nearly tight; Carter and Wegman show that formula_111 whenever formula_112.
Avoiding modular arithmetic.
The state of the art for hashing integers is the multiply-shift scheme described by Dietzfelbinger et al. in 1997. By avoiding modular arithmetic, this method is much easier to implement and also runs significantly faster in practice (usually by at least a factor of four). The scheme assumes the number of bins is a power of two, formula_113. Let formula_114 be the number of bits in a machine word. Then the hash functions are parametrised over odd positive integers formula_115 (that fit in a word of formula_114 bits). To evaluate formula_117, multiply formula_46 by formula_87 modulo formula_120 and then keep the high order formula_121 bits as the hash code. In mathematical notation, this is
and it can be implemented in C-like programming languages by
This scheme does "not" satisfy the uniform difference property and is only "formula_124-almost-universal"; for any formula_110, formula_109.
To understand the behavior of the hash function, 
notice that, if formula_127 and formula_128 have the same highest-order 'M' bits, then formula_129 has either all 1's or all 0's as its highest order M bits (depending on whether formula_127 or formula_131 is larger).
Assume that the least significant set bit of formula_85 appears on position formula_133. Since formula_87 is a random odd integer and odd integers have inverses in the ring formula_135, it follows that formula_136 will be uniformly distributed among formula_114-bit integers with the least significant set bit on position formula_133. The probability that these bits are all 0's or all 1's is therefore at most formula_139.
On the other hand, if formula_140, then higher-order M bits of 
formula_129 contain both 0's and 1's, so 
it is certain that formula_142. Finally, if formula_143 then bit formula_144 of 
formula_129 is 1 and formula_146 if and only if bits formula_147 are also 1, which happens with probability formula_148.
This analysis is tight, as can be shown with the example formula_149 and formula_150. To obtain a truly 'universal' hash function, one can use the multiply-add-shift scheme
which can be implemented in C-like programming languages by
where formula_87 is a random odd positive integer with formula_115 and formula_155 is a random non-negative integer with formula_156. With these choices of formula_87 and formula_155, formula_159 for all formula_160. This differs slightly but importantly from the mistranslation in the English paper.
Hashing vectors.
This section is concerned with hashing a fixed-length vector of machine words. Interpret the input as a vector formula_161 of formula_162 machine words (integers of formula_114 bits each). If formula_14 is a universal family with the uniform difference property, the following family (dating back to Carter and Wegman) also has the uniform difference property (and hence is universal):
If formula_2 is a power of two, one may replace summation by exclusive or.
In practice, if double-precision arithmetic is available, this is instantiated with the multiply-shift hash family of hash functions. Initialize the hash function with a vector formula_168 of random odd integers on formula_169 bits each. Then if the number of bins is formula_113 for formula_171:
It is possible to halve the number of multiplications, which roughly translates to a two-fold speed-up in practice. Initialize the hash function with a vector formula_168 of random odd integers on formula_169 bits each. The following hash family is universal:
If double-precision operations are not available, one can interpret the input as a vector of half-words (formula_176-bit integers). The algorithm will then use formula_177 multiplications, where formula_162 was the number of half-words in the vector. Thus, the algorithm runs at a "rate" of one multiplication per word of input.
The same scheme can also be used for hashing integers, by interpreting their bits as vectors of bytes. In this variant, the vector technique is known as tabulation hashing and it provides a practical alternative to multiplication-based universal hashing schemes.
Strong universality at high speed is also possible. Initialize the hash function with a vector formula_179 of random integers on formula_169 bits. Compute
The result is strongly universal on formula_114 bits. Experimentally, it was found to run at 0.2 CPU cycle per byte on recent Intel processors for formula_183.
Hashing strings.
This refers to hashing a "variable-sized" vector of machine words. If the length of the string can be bounded by a small number, it is best to use the vector solution from above (conceptually padding the vector with zeros up to the upper bound). The space required is the maximal length of the string, but the time to evaluate formula_184 is just the length of formula_185. As long as zeroes are forbidden in the string, the zero-padding can be ignored when evaluating the hash function without affecting universality. Note that if zeroes are allowed in the string, then it might be best to append a fictitious non-zero (e.g., 1) character to all strings prior to padding: this will ensure that universality is not affected.
Now assume we want to hash formula_186, where a good bound on formula_187 is not known a priori. A universal family proposed by 
treats the string formula_46 as the coefficients of a polynomial modulo a large prime. If formula_189, let formula_190 be a prime and define:
Using properties of modular arithmetic, above can be computed without producing large numbers for large strings as follows:
uint hash(String x, int a, int p)
 uint h = INITIAL_VALUE
 for (uint i=0 ; i < x.length ; ++i)
 h = ((h*a) + x[i]) mod p
 return h
This Rabin-Karp rolling hash is based on a linear congruential generator.
Above algorithm is also known as "Multiplicative hash function". In practice, the "mod" operator and the parameter "p" can be avoided altogether by simply allowing integer to overflow because it is equivalent to "mod" ("Max-Int-Value" + 1) in many programming languages. Below table shows values chosen to initialize "h" and a for some of the popular implementations.
Consider two strings formula_195 and let formula_187 be length of the longer one; for the analysis, the shorter string is conceptually padded with zeros up to length formula_187. A collision before applying formula_193 implies that formula_87 is a root of the polynomial with coefficients formula_200. This polynomial has at most formula_187 roots modulo formula_75, so the collision probability is at most formula_203. The probability of collision through the random formula_193 brings the total collision probability to formula_205. Thus, if the prime formula_75 is sufficiently large compared to the length of strings hashed, the family is very close to universal (in statistical distance).
Other universal families of hash functions used to hash unknown-length strings to fixed-length hash values include the Rabin fingerprint and the Buzhash.
Avoiding modular arithmetic.
To mitigate the computational penalty of modular arithmetic, three tricks are used in practice: