File UniversalHashing.h

↰ Parent directory (ADS/dictionary)

Universal hashing, beyond the book [see File HashFunctions.h for the fixed functions of section 7.1]: a class H of functions :math:` U rightarrow { 0 , ldots , m - 1 } ` is universal if two distinct keys collide under at most :math:` | H | / m ` of its functions, and c-universal if under at most :math:` c | H | / m ; a function drawn at random from it gives every set of keys the expected lists of length :math: 1 + alpha ` of the simple uniform hashing, :math:` alpha = n / m , and the longest of them is :math: O( log n / log log n ) ` in expectation when :math:` m = Theta( n ) `, whatever the keys, while for every fixed function there are n keys that fall in one list.

Definition (ADS/dictionary/UniversalHashing.h)

Detailed Description

The classes are

  • CarterWegmanHash, :math:` h_{a,b}( k ) = ( ( a k + b ) bmod p ) bmod m ` with p a prime larger than the keys, :math:` 1 le a < p ` and :math:` 0 le b < p , universal for every m; with :math: p = 2^{61} - 1 ` the product mod p is made of four products of 32 bits and a few shifts, with no integer of 128 bits [see mulMod61() and mulMod() in File NumberTheory.h];

  • DotProductHash, :math:` h_a( k ) = sum_i a_i k_i bmod m ` with m prime, the key cut into its r digits :math:` k_i ` in base m and :math:` a ` a vector of r digits: universal, since for two keys that differ in a digit the collision fixes that digit of a once the others are chosen;

  • MultiplyShiftHash, the class of Dietzfelbinger, Hagerup, Katajainen and Penttonen, :math:` h_a( k ) = ( a k bmod 2^h ) operatorname{div} 2^{h-l} ` with a odd, for keys of h bits and :math:` m = 2^l : 2-universal (two keys collide with probability at most :math: 2 / m `), and only a product and a shift, the fastest of the three;

  • StringHash, the polynomial :math:` sum_i s_i x^i bmod p ` of the characters of a string at a random point x, :math:` p = 2^{61} - 1 : two distinct strings of length at most L collide with probability at most :math: L / p `, since their difference is a polynomial of degree at most L with at most L roots; it turns a string into a key for the classes above.

DLeftHashTable is the d-left hashing of Vöcking on top of them: d tables of m / d lists, each with a function of its own, a key going to the shortest of its d lists and to the leftmost one on a tie; a search looks at the d lists. The longest list is then :math:` ln ln n / ( d ln phi_d ) + O( 1 ) ` with high probability for n = m keys, :math:` phi_d ` being the ratio of the generalized Fibonacci numbers, against :math:` Theta( log n / log log n ) ` with one function: the power of two choices of Azar, Broder, Karlin and Upfal, an exponential gain for one more probe, which lets each list be a bucket of fixed size :math:` O( log log n ) ` instead of a linked list. Its functions are simple tabulation [see TabulationHash in File RandomHashing.h], for which Dahlgaard, Knudsen, Rotenberg and Thorup proved a longest list of :math:` O( log log n ) ` with high probability.

The contracts [see File Contract.h]: a key below the universe of its class (p for CarterWegmanHash, :math:` m^r ` for DotProductHash, :math:` 2^h ` for MultiplyShiftHash), the parameters of a class in its range (a prime p or m is the caller’s duty, not checked), each hash below its m; insert() of DLeftHashTable ensures that the key is there and remove() that it is not, and its invariant is that each key is in one of its d lists and is counted once, checked on the key of the operation only past 1024 keys, so that a long sequence of operations at the level 3 stays linear. The functions are defined in UniversalHashing.tpp.

  1. Ferragina, Pearls of Algorithm Engineering, Cambridge University Press, 2023, chapter 8 (sections 8.2 and 8.3)

    1. Carter, M. N. Wegman, Universal classes of hash functions, Journal of Computer and System Sciences 18(2), 143-154, 1979, doi:10.1016/0022-0000(79)90044-8

  1. Dietzfelbinger, T. Hagerup, J. Katajainen, M. Penttonen, A reliable randomized algorithm for the closest-pair problem, Journal of Algorithms 25(1), 19-51, 1997, doi:10.1006/jagm.1997.0873

  1. Azar, A. Z. Broder, A. R. Karlin, E. Upfal, Balanced allocations, SIAM Journal on Computing 29(1), 180-200, 1999, doi:10.1137/S0097539795288490

  1. Vöcking, How asymmetry helps load balancing, Journal of the ACM 50(4), 568-589, 2003, doi:10.1145/792538.792546

  1. Dahlgaard, M. B. T. Knudsen, E. Rotenberg, M. Thorup, The power of two choices with simple tabulation, Proceedings of SODA 2016, 1631-1642, 2016

Donato Meoli

Dipartimento di Informatica Universita’ di Pisa

by Donato Meoli

Includes

Included By

Namespaces

Classes