4 ms·
Except for the last bit - a prime modulus ameliorates weaknesses in the hash function. Since most hash tables are written to support user-supplied hash functio
by barrkel 17y ago
Except for the last bit - a prime modulus ameliorates weaknesses in the hash function.
Since most hash tables are written to support user-supplied hash functions, and users need to write hash functions to support value-based equality when storing values of custom types in hash tables, it makes a lot of sense for the hash table implementer to take this into account.
Finally, there's a trade-off: sometimes a fast hash function with some weaknesses, but using a prime modulus, can be a better choice than a slower, more thorough hash function with e.g. a power of two modulus (bitwise and).