Hashing using division method

Question

For the hash function : h(k) = k mod m;

I understand that m=2^n will always give the last n LSB digits. I also understand that m=2^p-1 when K is a string converted to integers using radix 2^p will give same hash value for every permutation of characters in K. But why exactly "a prime not too close to an exact power of 2" is a good choice? What if I choose 2^p - 2 or 2^p-3? Why are these choices considered bad?

Following is the text from CLRS:

"A prime not too close to an exact power of 2 is often a good choice for m. For example, suppose we wish to allocate a hash table, with collisions resolved by chaining, to hold roughly n D 2000 character strings, where a character has 8 bits. We don’t mind examining an average of 3 elements in an unsuccessful search, and so we allocate a hash table of size m D 701. We could choose m D 701 because it is a prime near 2000=3 but not near any power of 2."

user_312896 · Answer

Suppose we work with radix 2^p.

2^p-1 case:

Why that is a bad idea to use 2^p-1? Let us see,

k = ∑a_i2^ip

and if we divide by 2^p-1 we just get

k = ∑a_i2^ip = ∑a_i mod 2^p-1

so, as addition is commutative, we can permute digits and get the same result.

2^p-b case:

Quote from CLRS:

A prime not too close to an exact power of 2 is often a good choice for m.

k = ∑a_i2^ip = ∑a_ibⁱ mod 2^p-b

So changing least significant digit by one will change hash by one. Changing second least significant bit by one will change hash by two. To really change hash we would need to change digits with bigger significance. So, in case of small b we face problem similar to the case then m is power of 2, namely we depend on distribution of least significant digits.

Hashing using division method

1 Answers

2p-1 case:

2p-b case:

2^p-1 case:

2^p-b case: