Universal Classes of Hash Functions: Counting Colliding-Pairs

[This page is auto-generated; please prefer to read the article’s PDF Form.]

[Prev] [Up] [Next]

Counting Colliding-Pairs

Now we perform another counting, for the key-pairs which collide. For any distinct keys x,y ∈ S and h ∈ℋ, we will call the pair (x,y) a “colliding-pair under h” if h(x) = h(y). We will not distinguish between pairs (x,y) and (y,x). Among the total (n)
2 pairs in S, can we say anything about the number of colliding-pairs under h? Let us denote the set of all (n)
2 pairs as P, and the number of colliding-pairs under h as C_h.

The deﬁnition of 𝜖-Universal class only tells us about the maximum number of functions under which a pair in P becomes a colliding-pair (𝜖H). For a particular function h, we don’t know how many pairs from P will become a colliding-pair. But if we count the number of colliding-pairs for each h ∈ℋ and add them together, we can progress as below:

∑ ∑ Ch = (Number of p ∈ P such that p is colliding-pair under h) h∈ℋ h∈∑ℋ = |{p ∈ P | p is a colliding-pair under h}| h∈ℋ {interestingly, this count can also be performed as below} ∑ = (Number of h ∈ ℋ such that p is colliding-pair under h) p∈P ∑ = |{h ∈ ℋ | p is a colliding-pair under h}| p∈P {any pair collides under maximum 𝜖H functions} ∑ ≤ 𝜖H p∈P (n ) = 2 𝜖H

Thus,

∑ C h (n ) h∈ℋ----≤ 𝜖 H 2

(4)

In words, the number of colliding-pairs for a function (C_h), averaged over all functions in ℋ, is maximum ( )
n
2 𝜖.

Note that for all h ∈ℋ, 0 ≤ C_h ≤ (n)
2 . It is easy to prove that among any H non-negative numbers, with average A, at least ⌈H∕2⌉ numbers must be less than 2A. So, we can conclude:

Theorem 3. Given 𝜖-Universal class ℋ and any set of n keys, at least half of the functions in class ℋ must have number of colliding-pairs C_h < 2 (n)
2 𝜖 = n(n − 1)𝜖.

This provides an upper-bound on C_h attained by at least half of the functions. So, to make sure that at least half of the functions are collision-free for a given set of n keys, i.e. have C_h = 0, we can restrict this upper-bound to be 1 (C_h are integers):

---1---- n(n − 1)𝜖 ≤ 1 ⇔ 𝜖 ≤ n(n− 1)

and adjust our universal-class to achieve such 𝜖. Note that this relation is same as equation (3) obtained in the last section.

Similarly, we know that at least one function must have C_h not exceeding the average of all C_h. So, to make sure that at least one function is collision-free (C_h = 0), we can restrict this average to be less than 1:

( ) n ----2--- 2 𝜖 < 1 ⇔ 𝜖 < n (n − 1).

[Prev] [Up] [Next]