Tabulation Based 5-Universal Hashing and Linear Probing

TY - GEN

T1 - Tabulation Based 5-Universal Hashing and Linear Probing

AU - Thorup, Mikkel

AU - Zhang, Yin

N1 - Covered by teTZ12

PY - 2010

Y1 - 2010

N2 - Previously [SODA'04] we devised the fastest known algorithm for 4-universal hashing. The hashing was based on small pre-computed 4-universal tables. This led to a five-fold improvement in speed over direct methods based on degree 3 polynomials. In this paper, we show that if the pre-computed tables are made 5-universal, then the hash value becomes 5-universal without any other change to the computation. Relatively this leads to even bigger gains since the directmethods for 5-universal hashing use degree 4 polynomials. Experimentally, we find that our method can gain up to an order of magnitude in speed over direct 5-universal hashing. Some of the most popular randomized algorithms have been proved to have the desired expected running time using 5-universal hashing, e.g., a non-recursive variant of quicksort takes O(n log n) expected time [Karloff Raghavan JACM'93], and linear probing does updates and searches in O(1) expected time [Pagh et al. SICOMP'09]. In contrast, inputs have been constructed leading to muchworse expected performance with some of the classic primality based 2-universal hashing schemes. In the context of linear probing, we compare our new fast 5-universal hashing experimentally with the fastest known plain universal hashing. We know that any reasonable hashing scheme will work on random input, but from Pagh et al., we know that 5-universal hashing leads to good expected performance on all input. We use a dense interval as an example of a structured yet realistic input, wanting to see if this could push the fastest multiplication-shift based plain universal hashing into bad performance. Even though our 5-universal hashing itself is slower than the fast plain universal hashing, it makes linear probing much more robust.

AB - Previously [SODA'04] we devised the fastest known algorithm for 4-universal hashing. The hashing was based on small pre-computed 4-universal tables. This led to a five-fold improvement in speed over direct methods based on degree 3 polynomials. In this paper, we show that if the pre-computed tables are made 5-universal, then the hash value becomes 5-universal without any other change to the computation. Relatively this leads to even bigger gains since the directmethods for 5-universal hashing use degree 4 polynomials. Experimentally, we find that our method can gain up to an order of magnitude in speed over direct 5-universal hashing. Some of the most popular randomized algorithms have been proved to have the desired expected running time using 5-universal hashing, e.g., a non-recursive variant of quicksort takes O(n log n) expected time [Karloff Raghavan JACM'93], and linear probing does updates and searches in O(1) expected time [Pagh et al. SICOMP'09]. In contrast, inputs have been constructed leading to muchworse expected performance with some of the classic primality based 2-universal hashing schemes. In the context of linear probing, we compare our new fast 5-universal hashing experimentally with the fastest known plain universal hashing. We know that any reasonable hashing scheme will work on random input, but from Pagh et al., we know that 5-universal hashing leads to good expected performance on all input. We use a dense interval as an example of a structured yet realistic input, wanting to see if this could push the fastest multiplication-shift based plain universal hashing into bad performance. Even though our 5-universal hashing itself is slower than the fast plain universal hashing, it makes linear probing much more robust.

M3 - Article in proceedings

SP - 62

EP - 76

BT - Proceedings of the 12th Workshop on Algorithm Engineering and Experiments (ALENEX)

PB - SIAM

ER -