Efficient Delta-Universal and Strongly-Universal Hashing

Dana Jansens

In this talk we review the first half of a paper by Woelfel in which he presents simple but important hash classes that are computationally efficient on modern hardware. The functions make use of only addition, multiplication, and integer division. When done relative to powers of two, these translate into addition and bit shifts, which are very efficient. These hash classes are important because of his work to show that they are provably good, rather than basing them simply on heuristics.

We will see proofs that these functions are good at placing keys in a hash table such that any pair of inputs fall at any given distance in the hash table with low probability. A second class follows that maps a pair of inputs to any fixed pair of outputs with low probability. These properties are termed delta-universality, and strong-universality.