Information about Universal Hash Function

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

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,

Without qualification, the latter definition is probably intended.

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, h_a,b, as

See also

• Hash functions.
• Universal One-Way Hash Functions UOWHF.

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.