Home

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


[Prev]   [Up]   [Next]   

Counting Collision-Free Functions

Consider a πœ–-Universal class β„‹ of H functions, mapping U to β„€m. Say we are given a set S of n keys from U. Are there any functions in β„‹ which give no collision for all keys in S? We will refer to such functions as β€œCollision-Free” for S. So, these functions map the n distinct keys to n distinct values of β„€m. Such a function would exist only if |β„€m|β‰₯|S|, i.e. m β‰₯ n.

The definition of πœ–-Universal class provides an upper bound of πœ–H on the number of functions where any key pair would collide. We can form (n) 2 key pairs from S. Thus, the maximum number of functions where any of these (n) 2 pairs can collide is:

(n) 2 πœ–H
(1)

Note that this is only an upper-bound and can even exceed the available functions count of H. The subset of functions where a pair collides may overlap with the subset of functions where some other pair collides. Since above we simply added maximum size of each such subset (i.e. πœ–H), once for each pair, this upper bound may be loose.

Based on (1), the minimum number of functions in β„‹ which must be collision-free for S, if (n) 2πœ–H ≀ H:

( ) H βˆ’ n πœ–H 2

So, the minimum proportion of such functions in β„‹:

( ( ) ) H βˆ’ n2 πœ–H (n ) Ξ± = -----H-------= 1 βˆ’ 2 πœ–
(2)

Although (2) need not provide a tight lower bound on the proportion of functions which are collision-free for a given set of n keys, it can still be useful. It relates the lower-bound Ξ± to πœ–, and it may be possible to adjust the parameters of the universal class to achieve certain πœ–. For example, for a 1βˆ•m-Universal class, πœ– = 1βˆ•m can be modified by simply modifying the table-size m.

Suppose we want to ensure the lower bound Ξ± is at least 1/2; so at least half of the functions in β„‹ are collision-free for a given set of n keys. Then (2) gives:

(n) 1 1 1βˆ’ πœ– β‰₯ -- ⇔ πœ– ≀ -------- 2 2 n (n βˆ’ 1)
(3)

For any 1βˆ•m-Universal class, (3) becomes:

-1 ≀ ----1--- ⇔ m β‰₯ n (n βˆ’ 1) m n (n βˆ’ 1)

And for 2βˆ•m-Universal class, (3) becomes:

-2 ≀ ----1--- ⇔ m β‰₯ 2n (n βˆ’ 1) m n (n βˆ’ 1)

To make α at least f ∈ (0,1), we need:

( ) n 2(1-βˆ’-f) 1 βˆ’ 2 πœ– β‰₯ f ⇔ πœ– ≀ n(n βˆ’ 1)

Theorem 1. Given πœ–-Universal class β„‹ and any set of n keys, the proportion of functions in β„‹ which are collision-free for those keys is at least f ∈ (0,1) if:

2(1βˆ’ f) πœ– ≀ --------. n(n βˆ’ 1)

Corollary 2. Given πœ–-Universal class β„‹ with πœ– = 1βˆ•m, and any set of n keys, at least half of the functions in β„‹ are collision-free for those keys if: m β‰₯ n(n βˆ’ 1). For πœ– = 2βˆ•m, this condition is: m β‰₯ 2n(n βˆ’ 1).

[Prev]   [Up]   [Next]   

Copyright © 2021 Nitin Verma. All rights reserved.