Home

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


[Prev]   [Up]   

From Ch to si2

For a function h ∈ℋ, let us denote by Si the set of keys from S which are mapped to i ∈ ℤm by h. Say si = |Si|. So, the number of colliding-pairs in slot i is (si) 2. Hence,

∑ ( ) Ch = si i∈ℤ 2 ∑ m 2 = si −-si i∈ℤm 2 ( ∑ ∑ ) = 1- s2 − si 2 i∈ℤ i i∈ℤ ( m )m = 1- ∑ s2 − n 2 i i∈ℤm

So the following inequality from theorem 3 can be rewritten:

( Ch) < n(n − 1)𝜖 1 ∑ ⇔ -- s2i − n < n(n − 1)𝜖 2 i∈ℤm ⇔ ∑ s2 < 2n(n − 1)𝜖+ n i i∈ℤm

Corollary 4. Given 𝜖-Universal class ℋ and any set of n keys, if si is the number of keys mapped to slot i by a function h ∈ℋ, at least half of the functions in class ℋ must have si such that:

∑ 2 si < 2n(n − 1)𝜖+ n. i∈ℤm

This upper-bound on the sum of si2 finds its use for optimizing space in the FKS Method of Perfect Hashing [1].

■

References

[1]   M. L. Fredman, J. Komlós, E. Szemerédi. Storing a Sparse Table with O(1) Worst Case Access Time. J. ACM, Vol 31 (3) (1984), 538–544.

[2]   Z. J. Czech, G. Havas, B. S. Majewski. Fundamental Study: Perfect Hashing. Theoretical Computer Science, Vol 182 (1–2) (1997), 1–143.

[3]   T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein. Introduction to Algorithms, Third Edition. The MIT Press, 2009.

[Prev]   [Up]   

Copyright © 2021 Nitin Verma. All rights reserved.