Skip to main content
1 of 1
Per Vognsen
  • 2.1k
  • 19
  • 24

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.

Per Vognsen
  • 2.1k
  • 19
  • 24