Wikipedia / Universal hashing
Wikipedia / 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
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.
is called a universal family.
. This is exactly the probability of collision we would expect if the hash function assigned truly random hash codes to every key.
. This concept was introduced by Carter and Wegman in 1977, and has found numerous applications in computer science (see, for .
-almost universality.
Many, but not all, universal families have the following stronger uniform difference property:
.
, which counts collisions. The uniform difference property is stronger.
is a power of two.)
An even stronger condition is pairwise independence. Pairwise independence is sometimes called strong universality.
. Universality does not imply uniformity. However, strong universality does imply uniformity.
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.
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
keys, using a universal family guarantees the following properties.
. When implementing hash tables by chaining (for example a query, insertion or deletion).
bins, there are no collisions at all with probability at least a half.
., this result is no longer true.
, 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 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
.
The original proposal of Carter and Wegman and define
. (This is a single iteration of a linear congruential generator.)
only holds when
is nonzero and has an inverse modulo yields
.
possible non-zero values for the right hand side. Thus the collision probability is
.
is a universal family is via the notion of statistical distance as
.
.
The family of simpler hash functions
is only approximately. Moreover, this analysis is nearly tight; Carter and Wegman .
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 bits as the hash code. In mathematical notation, this is
This scheme does not satisfy the uniform difference property and is only -almost-universal.
is a random odd integer and odd integers have inverses in the ring.
. To obtain a truly 'universal' hash function, one can use the multiply-add-shift scheme that picks higher-order bits
-bit unsigned integers. This version of multiply-shift is due to Dietzfelbinger, and was later analyzed more precisely by Woelfel.
Hashing vectors
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):
is chosen independently at random.
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. of random odd:
.
It is possible to halve the number of multiplications, which roughly translates to a two-fold speed-up in practice. of random odd bits each. The following hash family is universal:
.
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. bits. Compute
.
.
Hashing strings
This refers to hashing a variable-sized. 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.
is not known a priori. A universal family proposed by be a prime and define:
.
Using properties of modular arithmetic, above can be computed without producing large numbers for large strings as follows:
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 allowing integer to overflow because it is equivalent to mod (Max-Int-Value modulus is prone to collisions with certain inputs, regardless of the value of a. Below table shows values chosen to initialize h and a for some of the popular implementations. 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:
to be close to a power of two, such as a Mersenne prime's are 32-bit values.
results. Since the slower string hashing is applied on a substantially smaller vector, this will essentially be as fast as vector hashing.
to be implemented without division (using faster operations of bit masking). The NH hash-function family takes this approach.
See also
References
Further reading
External links