Let U∈N+U \in \N^+, and S={x1,x2,…,xm}⊆ZUS = \{ x_1, x_2, \ldots, x_m \} \subseteq \mathbb{Z}_U be a set of distinct element.

Consider a function h:ZU→Znh: \mathbb{Z}_U \rightarrow \mathbb{Z}_n, where n≤Un \le U. We call hh a hash function. In the case where n<Un < U, there must be some i∈Zni \in \mathbb{Z}_n, s.t., ∣h−1(i)∣>1|h^{-1}(i)| > 1. We are interested in the number of total duplicate value in

h(S)≐{h(x1),h(x2),…,h(xm)}. h(S) \doteq \{ h(x_1), h(x_2), \ldots, h(x_m) \}.

If both SS and hh are fixed, there is nothing uncertain. There are two ways to add some randomness to our analysis

  1. hh is fixed, and SS follows some distribution on ZU\mathbb{Z}_U. E.g., let U=220U = 2^{20} and h(x)=x & 1023h(x) = x \ \& \ 1023 that returns the last 1010 bits of xx (in binary form). If SS is sampled uniformly at random from ZU\mathbb{Z}_U, then on average for each xi∈Sx_i \in S, there are k−11024\frac{k - 1}{1024} elements that have the same value as xix_i under hh.

  2. The assumption that SS follows some distribution is too strong. Instead we assume that given SS, we select a function hh uniformly, from a set of functions H\mathcal{H}. Now we are interested in the probability

    Pr⁡[h(xi)=h(xj)],i≠j. \Pr[ h(x_i) = h(x_j) ], \quad i \neq j.

The finite field Fp\mathbb{F}_p

Let p>Up > U be a prime number and

H≐{h(x)≐(ax+bmod  p)mod  n | a,b∈Fp}. \mathcal{H} \doteq \left\{ h(x) \doteq \left( ax + b \mod p \right) \mod n \, \middle| \, a, b \in \mathbb{F}_p \right\}.

Theorem. If hh is sampled uniformly at random from H\mathcal{H}, then

Pr⁡[h(xi)=h(xj)]≤1n,xi≠xj. \Pr[ h(x_i) = h(x_j) ] \le \frac{1}{n}, \quad x_i \neq x_j.

Lemma 1. Given xi,xj,s,t∈Fpx_i, x_j, s, t \in \mathbb{F}_p, s.t., xi≠xjx_i \neq x_j, there is a unique pair (a,b)∈Fp×Fp(a,b) \in \mathbb{F}_p \times \mathbb{F}_p

axi+b=s,axj+b=t, a x_i + b = s, \\ a x_j + b = t,

where the equations hold in the field Fp\mathbb{F}_p.

Proof. Since xi≠xjx_i \neq x_j, the following matrix is invertible

[xi,1xj,1]∈Fp2×2. \begin{bmatrix} x_i , 1 \\ x_j , 1 \end{bmatrix} \in \mathbb{F}_p^{2 \times 2}.

Therefore,

[ab]=[xi,1xj,1]−1[st] \begin{bmatrix} a \\ b \end{bmatrix} = \begin{bmatrix} x_i, 1 \\ x_j, 1 \end{bmatrix}^{-1} \begin{bmatrix} s \\ t \end{bmatrix}

□\square

Proof of the Theorem.

For xi≠xjx_i \neq x_j,

Pr⁡[h(xi)=h(xj)]=∑s,t∈Fp,s≡t(modn)Pr⁡[h(xi)=s∧h(xj)=t]=∑s,t∈Fp,s≡t(modn)1p2=∑s∈Fp(∑t∈Fp,t≡s(modn)1p2)≤∑s∈Fppn⋅1p2=1n. \begin{aligned} \Pr[h(x_i) = h(x_j)] &= \sum_{s, t \in \mathbb{F}_p, s \equiv t \pmod n} \Pr[ h(x_i) = s \wedge h(x_j) = t] \\ &= \sum_{s, t \in \mathbb{F}_p, s \equiv t \pmod n} \frac{1}{ p^2 } \\ &= \sum_{s \in \mathbb{F}_p} \left( \sum_{t \in \mathbb{F}_p, t \equiv s \pmod n} \frac{1}{ p^2 } \right) \\ &\le \sum_{s \in \mathbb{F}_p} \frac{p}{ n } \cdot \frac{1}{ p^2 } \\ &= \frac{1}{ n }. \end{aligned}

□\square

Lemma 3. The expected number of pair xi,xjx_i, x_j, s.t., xi≠xj∧h(xi)=h(xj)x_i \neq x_j \wedge h(x_i) = h(x_j) is given by

E[∑xi≠xjIh(xi)=h(xj)]=∑xi≠xjPr⁡[h(xi=xj)]=(m2)1n=m(k−1)2n \mathbb{E} \left[ \sum_{x_i \neq x_j} \mathbb{I}_{h(x_i) = h(x_j)} \right] = \sum_{x_i \neq x_j} \Pr[h(x_i = x_j)] = \binom{m}{2} \frac{1}{n} = \frac{m (k - 1)}{ 2n }

When m2≤nm^2 \le n, then E[∑xi≠xjIh(xi)=h(xj)]≤12\mathbb{E} \left[ \sum_{x_i \neq x_j} \mathbb{I}_{h(x_i) = h(x_j)} \right] \le \frac{1}{2}. By Markov inequality,

Pr⁡[∃  collision]≤12. \Pr[\exists \, \, \text{collision}] \le \frac{1}{ 2 }.

Lemma 4. With probability at most 1/21/2, some bin contains more than mn+2m\frac{m}{n} + \sqrt{2m} balls.

For a fixed bin, let YY denote the number of ball in this bin. Further, define

Yi={1,if the i-th ball falls into the bin0,otherwise Y_i = \begin{cases} 1, \qquad \text{if the } i \text{-th ball falls into the bin} \\ 0, \qquad \text{otherwise} \end{cases}

Then Y=∑iYiY = \sum_i Y_i, and

E[Y]=mn \mathbb{E} [Y] = \frac{m}{n} \\

By pair-wise independence, we have

Var[Y]=∑iVar[Yi]=m1n(1−1n) Var[Y] = \sum_i Var[Y_i] = m \frac{1}{n} \left(1 - \frac{1}{n} \right)

Therefore, by Chebyshev inequality, we have

Pr⁡[∣Y−E[Y]∣≥2nm1n(1−1n)]=Pr⁡[∣Y−E[Y]∣≥2n⋅σ]≤Var[Y]2nσ2=12n. \Pr \left[ |Y - \mathbb{E}[Y]| \ge \sqrt{2n} \sqrt{ m \frac{1}{n} \left(1 - \frac{1}{n} \right)} \right] = \Pr[|Y - \mathbb{E}[Y]| \ge \sqrt{2n} \cdot \sigma] \le \frac{Var[Y]}{2n\sigma^2} = \frac{1}{2n}.

Finally, applying union bound over nn bins, we get

Pr⁡[some bin gets more than 2m balls]≤12. \Pr[\text{some bin gets more than } \sqrt{2m} \text{ balls} ] \le \frac{1}{2}.

The finite field F2k\mathbb{F}_{2^k}

We consider an extension such that each element xi∈Sx_i \in S is now a vector ∈F2k\in \mathbb{F}_2^k.

We would like to have some operations ⊗\otimes and ⊕\oplus, such that if we sample a hash function h:F2k→F2kh : \mathbb{F}_2^k \rightarrow \mathbb{F}_2^k uniformly at random from the following family

H={h(x)≐a⊗x⊕b | a,b∈F2k}, \mathcal{H} = \left\{ h(x) \doteq a \otimes x \oplus b \, \middle| \, a, b \in \mathbb{F}_2^k \right\},

then h(xi)h(x_i) and h(xj)h(x_j) are pairwise independent for xi≠xjx_i \neq x_j.

In particular, when xi≠xjx_i \neq x_j, it holds that

Pr⁡[h(xi)=s ∧ h(xj)=t]=Pr⁡[h(xi)=s]⋅Pr⁡[h(xj)=t]=(12k)2,∀s,t∈F2k. \begin{align*} \Pr[ h(x_i) = s \, \wedge \, h(x_j) = t] &= \Pr[ h(x_i) = s ] \cdot \Pr[ h(x_j) = t ] \\ &= \left( \frac{1}{2^k} \right)^2, &\quad \forall s, t \in \mathbb{F}_2^k. \end{align*}

We would like the a,b∈F2ka, b \in \mathbb{F}_2^k to be determined by

[ab]=[xi,1xj,1]−1[st]. \begin{bmatrix} a \\ b \end{bmatrix} = \begin{bmatrix} x_i, 1 \\ x_j, 1 \end{bmatrix}^{-1} \begin{bmatrix} s \\ t \end{bmatrix}.

In order that this holds, the set of vectors F2m\mathbb{F}_2^m, when augmented with operations ⊗\otimes and ⊕\oplus, should constitute a field.

Fact. For each k∈N+k \in \mathbb{N}^+, there is a polynomial qkq_k with coefficients in F2\mathbb{F}_2 and of degree kk that is irreducible (cannot be factor).

We now view xi=(xi[0],…,xi[k−1])x_i = (x_i[0], \ldots, x_i[k - 1]) as a polynomial

pxi(z)≐(xi[0]+xi[1]⋅z+⋯+xi[k−1]⋅zk−1)mod  qk. p_{x_i}(z) \doteq \left( x_i[0] + x_i[1] \cdot z + \cdots + x_i[k - 1] \cdot z^{k - 1} \right) \mod q_k.

The ⊕\oplus is defined to be the addition of polynomials. Hence,

xi⊕xj=(xi[0]+xj[0],…,xi[k−1]+xj[k−1]), x_i \oplus x_j = (x_i[0] + x_j[0], \ldots, x_i[k - 1] + x_j[k - 1]),

since

pxi(z)+pxj(z)=((xi[0]+xj[0])+(xi[1]+xj[1])⋅z+⋯+(xi[k−1]+xj[k−1])⋅zk−1)mod  qk. \begin{aligned} &p_{x_i}(z) + p_{x_j}(z) \\ &= \left( ( x_i[0] + x_j[0] ) + ( x_i[1] + x_j[1] ) \cdot z + \cdots + ( x_i[k - 1] + x_j[k - 1] ) \cdot z^{k - 1} \right) \mod q_k. \end{aligned}

Moreover, we can consider the ⊗\otimes as polynomial multiplications (modq)k\pmod q_k, which results in a polynomial of degree at most kk.

Finally, since qkq_k is irreducible, if xi≠0x_i \neq 0, there exists polynomial cc and dd, such that c(modq)k≡cc \pmod q_k \equiv c and

1=c⋅xi+d⋅qk. 1 = c \cdot x_i + d \cdot q_k.

Hence, cc can be viewed as the inverse of xix_i and division is well-defined. It concludes that (F2k,⊗,⊕)(\mathbb{F}_2^k, \otimes, \oplus) constitute a field.

Reference

[1] Sanjeev Arora, Cos 521: Advanced Algorithm Design, Lecture 1: Course Intro and Hashing.

[2] Nick Harvey, CPSC 536N: Randomized Algorithms 2014-15 Term 2, Lecture 13, University of British Columbia