The lengths of hash tables
This is something of a myth. If you have a good hash function, the number-theoretical properties of your table's modulus are irrelevant; conversely, if you have a bad hash function, a prime modulus does little to salvage it.
Indeed, a power-of-two modulus has a lot to recommend itself in practice: you can perform reduction of $x$ modulo a power of two $n$ in one processor cycle using the identity $x MOD n = x AND (n-1)$.
Look at the highest-performing hash table implementations and you will find they use powers of two. Examples include Google's sparsehash and Sean Barrett's hash table from his article on Judy arrays.
No comments:
Post a Comment