13
votes
0answers
294 views

Reusing 5-independent hash functions for linear probing

In hash tables that resolve collisions by linear probing, in order to ensure $O(1)$ expected performance, it is both necessary and sufficient that the hash function be from a 5-independent family. ...