Say I have a greater-than-expected number of collisions in my hash table that has 2^w buckets (half of them empty). So I pick a fresh new random CRC polynomial that generates w-bit check values (i.e., a w+1 bit value with the high bit and the low bit forced to 1, and the other w-1 bits pulled from /dev/random ), and re-hash all the items in my table using the new CRC as a hash function. Will most such hash functions have close to the expected number of collisions predicted by the birthday problem, no matter what particular strings Mallory gave me to use as keys for the items in my hash table?

In other words:

Is the Rabin fingerprinting scheme with a random polynomial a universal hash function family?

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.