[This page is auto-generated; please prefer to read the article’s PDF Form.]
Say, we are given the set of static-keys S having n keys and we need to find a collision-free hash-function mapping them to ℤm = {0,1,2,…,m − 1}. How can we search for such a function? From which collection of functions can we hope to find it, possibly after some trial-and-error?
What helps us here is the Universal Classes of hash-functions. They are a collection of hash-functions with the property that any two distinct keys can collide only under a specified maximum number of functions. Please refer to the article titled Universal Classes of Hash Functions ([3]) for the definition of Universal Class and 𝜖-Universal Class. In this discussion, we will make use of some relations about these classes as derived in that article.
Theorem 1 in [3] tells us that, for any 𝜖-Universal class and given any set S of n keys, we are guaranteed to find a certain proportion of collision-free functions in the class, if 𝜖 and n are related as specified. Specifically, the subsequent Corollary 2 ensures us that for any 1∕m-Universal class, if we choose m ≥ n(n − 1), at least half of its functions must be collision-free for S.
This is really useful for our problem. We can choose any 1∕m-Universal class and use the hashtable size m = n(n− 1). Then we can randomly select a function from this class and hash all the keys from S to see if there are any collisions. We can repeat until we find a function without collision. The above theorem ensures that we should succeed in a very few attempts because half of the functions are what we are looking for.
Copyright © 2021 Nitin Verma. All rights reserved.