Universal hash function
From Wikipedia, the free encyclopedia
In computer science, a universal hash function is a theoretical construct primarily used to show that an algorithm based on a hash function cannot be forced to have bad performance by an adversary. Bad performance in hashing comes from collisions, and a universal hash function guarantees that these cannot be forced to occur too often.
The formal definition involves a set of keys, K, a set of values, V, and a family of hash functions, H, mapping keys to values. Let |V| denote size of V, the number of possible values. Then for all pairs of distinct keys x and y in K, H is a 2-universal family of hash functions if
![\Pr_{h \in H}[h(x) = h(y)] \le \frac{1}{|V|} .](../../../math/5/d/a/5da2e492f1b2dec990da0441d4bb2750.png)
More stringently, H is a strongly 2-universal family if for all pairs of distinct keys x and y in K, and for all values x′ and y′ in V,
![\Pr_{h \in H}[h(x) = x' \mbox{ and } h(y) = y'] = \frac{1}{|V|^2} .](../../../math/1/4/e/14ed13c50662c26d32dcfb1a05a4477b.png)
Without qualification, the latter definition is probably intended.
[edit] Example
Let the keys, K, be {0,1,…,p−1} for some prime, p, and let the values, V, be {0,1,…n−1}. Define a 2-parameter family of functions, ha,b, as
[edit] See also
- Hash functions.
- Universal One-Way Hash Functions UOWHF.
[edit] References
- Knuth, Donald Ervin (1998). [The Art of Computer Programming], Vol. III: Sorting and Searching, 2e, Reading, Mass ; London: Addison-Wesley. ISBN 0-201-89685-0.
