Page "Hash function" Paragraph 27

We can allow the table size n to not be a power of 2 and still not have to perform any remainder or division operation, as these computations are sometimes costly.

For example, let n be significantly less than 2 < sup > b </ sup >.

Consider a pseudo random number generator ( PRNG ) function P ( key ) that is uniform on the interval 2 < sup > b </ sup > − 1.

A hash function uniform on the interval n-1 is n P ( key )/ 2 < sup > b </ sup >.

We can replace the division by a ( possibly faster ) right bit shift: nP ( key ) >> b.