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 ${\displaystyle \{0,\dots ,|U|-1\}}$.

The original proposal of Carter and Wegman^[1] was to pick a prime ${\displaystyle p\geq |U|}$ and define

${\displaystyle h_{a,b}(x)=((ax+b)~{\bmod {~}}p)~{\bmod {~}}m}$

where ${\displaystyle a,b}$ are randomly chosen integers modulo ${\displaystyle p}$ with ${\displaystyle a\neq 0}$. (This is a single iteration of a linear congruential generator.)

To see that ${\displaystyle H=\{h_{a,b}\}}$ is a universal family, note that ${\displaystyle h(x)=h(y)}$ only holds when

${\displaystyle ax+b\equiv ay+b+i\cdot m{\pmod {p}}}$

for some integer ${\displaystyle i}$ between ${\displaystyle 0}$ and ${\displaystyle (p-1)/m}$. Since ${\displaystyle p\geq |U|}$, if ${\displaystyle x\neq y}$ their difference ${\displaystyle x-y}$ is nonzero and has an inverse modulo ${\displaystyle p}$. Solving for ${\displaystyle a}$ yields

${\displaystyle a\equiv i\cdot m\cdot (x-y)^{-1}{\pmod {p}}}$.

There are ${\displaystyle p-1}$ possible choices for ${\displaystyle a}$ (since ${\displaystyle a=0}$ is excluded) and, varying ${\displaystyle i}$ in the allowed range, ${\displaystyle \lfloor (p-1)/m\rfloor }$ possible non-zero values for the right hand side. Thus the collision probability is

${\displaystyle \lfloor (p-1)/m\rfloor /(p-1)\leq ((p-1)/m)/(p-1)=1/m}$.

Another way to see ${\displaystyle H}$ is a universal family is via the notion of statistical distance. Write the difference ${\displaystyle h(x)-h(y)}$ as

${\displaystyle h(x)-h(y)\equiv (a(x-y)~{\bmod {~}}p){\pmod {m}}}$.

Since ${\displaystyle x-y}$ is nonzero and ${\displaystyle a}$ is uniformly distributed in ${\displaystyle \{1,\dots ,p-1\}}$, it follows that ${\displaystyle a(x-y)}$ modulo ${\displaystyle p}$ is also uniformly distributed in ${\displaystyle \{1,\dots ,p-1\}}$. The distribution of ${\displaystyle (h(x)-h(y))~{\bmod {~}}m}$ is thus almost uniform, up to a difference in probability of ${\displaystyle \pm 1/p}$ between the samples. As a result, the statistical distance to a uniform family is ${\displaystyle O(m/p)}$, which becomes negligible when ${\displaystyle p\gg m}$.

The family of simpler hash functions

${\displaystyle h_{a}(x)=(ax~{\bmod {~}}p)~{\bmod {~}}m}$

is only approximately universal: ${\displaystyle \Pr\{h_{a}(x)=h_{a}(y)\}\leq 2/m}$ for all ${\displaystyle x\neq y}$.^[1] Moreover, this analysis is nearly tight; Carter and Wegman ^[1] show that ${\displaystyle \Pr\{h_{a}(1)=h_{a}(m+1)\}\geq 2/(m-1)}$ whenever ${\displaystyle (p-1)~{\bmod {~}}m=1}$.

Hashing vectors

This section is concerned with hashing a fixed-length vector of machine words. Interpret the input as a vector ${\displaystyle {\bar {x}}=(x_{0},\dots ,x_{k-1})}$ of ${\displaystyle k}$ machine words (integers of ${\displaystyle w}$ bits each). If ${\displaystyle H}$ is a universal family with the uniform difference property, the following family (dating back to Carter and Wegman^[1]) also has the uniform difference property (and hence is universal):

${\displaystyle h({\bar {x}})=\left(\sum _{i=0}^{k-1}h_{i}(x_{i})\right)\,{\bmod {~}}m}$, where each ${\displaystyle h_{i}\in H}$ is chosen independently at random.

If ${\displaystyle m}$ is a power of two, one may replace summation by exclusive or.^[11]

In practice, if double-precision arithmetic is available, this is instantiated with the multiply-shift hash family of hash functions.^[12] Initialize the hash function with a vector ${\displaystyle {\bar {a}}=(a_{0},\dots ,a_{k-1})}$ of random odd integers on ${\displaystyle 2w}$ bits each. Then if the number of bins is ${\displaystyle m=2^{M}}$ for ${\displaystyle M\leq w}$:

${\displaystyle h_{\bar {a}}({\bar {x}})=\left({\big (}\sum _{i=0}^{k-1}x_{i}\cdot a_{i}{\big )}~{\bmod {~}}2^{2w}\right)\,\,\mathrm {div} \,\,2^{2w-M}}$.

It is possible to halve the number of multiplications, which roughly translates to a two-fold speed-up in practice.^[11] Initialize the hash function with a vector ${\displaystyle {\bar {a}}=(a_{0},\dots ,a_{k-1})}$ of random odd integers on ${\displaystyle 2w}$ bits each. The following hash family is universal:^[13]

${\displaystyle h_{\bar {a}}({\bar {x}})=\left({\Big (}\sum _{i=0}^{\lceil k/2\rceil }(x_{2i}+a_{2i})\cdot (x_{2i+1}+a_{2i+1}){\Big )}{\bmod {~}}2^{2w}\right)\,\,\mathrm {div} \,\,2^{2w-M}}$.

If double-precision operations are not available, one can interpret the input as a vector of half-words (${\displaystyle w/2}$-bit integers). The algorithm will then use ${\displaystyle \lceil k/2\rceil }$ multiplications, where ${\displaystyle k}$ 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.^[14]

Strong universality at high speed is also possible.^[15] Initialize the hash function with a vector ${\displaystyle {\bar {a}}=(a_{0},\dots ,a_{k})}$ of random integers on ${\displaystyle 2w}$ bits. Compute

${\displaystyle h_{\bar {a}}({\bar {x}})^{\mathrm {strong} }=(a_{0}+\sum _{i=0}^{k-1}a_{i+1}x_{i}{\bmod {~}}2^{2w})\,\,\mathrm {div} \,\,2^{w}}$.

The result is strongly universal on ${\displaystyle w}$ bits. Experimentally, it was found to run at 0.2 CPU cycle per byte on recent Intel processors for ${\displaystyle w=32}$.

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 ${\displaystyle h(s)}$ is just the length of ${\displaystyle s}$. As long as zeroes are forbidden in the string, the zero-padding can be ignored when evaluating the hash function without affecting universality.^[11] 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.^[15]

Now assume we want to hash ${\displaystyle {\bar {x}}=(x_{0},\dots ,x_{\ell })}$, where a good bound on ${\displaystyle \ell }$ is not known a priori. A universal family proposed by ^[12] treats the string ${\displaystyle x}$ as the coefficients of a polynomial modulo a large prime. If ${\displaystyle x_{i}\in [u]}$, let ${\displaystyle p\geq \max\{u,m\}}$ be a prime and define:

${\displaystyle h_{a}({\bar {x}})=h_{\mathrm {int} }\left({\big (}\sum _{i=0}^{\ell }x_{i}\cdot a^{\ell -i}{\big )}{\bmod {~}}p\right)}$, where ${\displaystyle a\in [p]}$ is uniformly random and ${\displaystyle h_{\mathrm {int} }}$ is chosen randomly from a universal family mapping integer domain ${\displaystyle [p]\mapsto [m]}$.

Using properties of modular arithmetic, above can be computed without producing large numbers for large strings as follows:^[16]

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.^[17] Above algorithm is also known as Multiplicative hash function.^[18] 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 ${\displaystyle {\bar {x}},{\bar {y}}}$ and let ${\displaystyle \ell }$ be length of the longer one; for the analysis, the shorter string is conceptually padded with zeros up to length ${\displaystyle \ell }$. A collision before applying ${\displaystyle h_{\mathrm {int} }}$ implies that ${\displaystyle a}$ is a root of the polynomial with coefficients ${\displaystyle {\bar {x}}-{\bar {y}}}$. This polynomial has at most ${\displaystyle \ell }$ roots modulo ${\displaystyle p}$, so the collision probability is at most ${\displaystyle \ell /p}$. The probability of collision through the random ${\displaystyle h_{\mathrm {int} }}$ brings the total collision probability to ${\displaystyle {\frac {1}{m}}+{\frac {\ell }{p}}}$. Thus, if the prime ${\displaystyle p}$ 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.