Hash table lengths and prime numbers

Hash table lengths and prime numbers

This has been bugging me for some time now...
The first thing you do when inserting/retreiving from hash table is to calculate the hashCode for the given key and then find the correct bucket by trimming the hashCode to the size of the hashTable by doing hashCode % table_length. Here are 2 statements that you most probably have read somewhere

• If you use a power of 2 for table_length, finding (hashCode(key) % 2^n ) is as simple and quick as (hashCode(key) & (2^n -1)). But if your function to calculate hashCode for a given key isn't good, you will definitely suffer from clustering of many keys in a few hash buckets.
• But if you use prime numbers for table_length, hashCodes calculated could map into the different hash buckets even if you have a slightly stupid hashCode function.

Ok, but now can someone tell me why it is so...today I think I found out why...if u think I'm wrong put in a comment, atleast for the sake of others. I suggest you think about the solution on your own before reading further...

If suppose your hashCode function results in the following hashCodes among others {x , 2x, 3x, 4x, 5x, 6x...}, then all these are going to be clustered in just m number of buckets, where m = table_length/GreatestCommonFactor(table_length, x). (It is trivial to verify/derive this). Now you can do one of the following to avoid clustering 

1. Make sure that you don't generate too many hashCodes that are multiples of another hashCode like in {x, 2x, 3x, 4x, 5x, 6x...}.But this may be kind of difficult because you have to come up with a perfect hashCode function.
2. Or simply make m equal to the table_length by making GreatestCommonFactor(table_length, x) equal to 1, i.e by making table_length coprime with x. And if x can be just about any number then make sure that table_length is a prime number.

Lets go for an example :

Let an Array size is 20 

Need to store number from 10 to 100 

So we should able to store all numbers as we have Array size > Number of element without clustering 

array [1,2,3,4,5,6,7,8,9,10]

Element need to add is 10,20,30,40,50,60,70,80,90,100

My Hash function is very bad i.e Number % Table Size is my Key 

H(n) = number%Table_size

so for 10 key is 10%20 = 10 (Clustering or duplicate Key)

so for 20 key is 20%20 = 1

so for 30 key is 30%20 = 10

so for 40 key is 40%20 = 2  

so for 50 key is 50%20 = 10 (Clustering or duplicate Key)

so for 60 key is 60%20 = 18

so for 70 key is 70%20 = 10 (Clustering or duplicate Key) 

so for 80 key is 80%20 = 4

so for 90 key is 90%20 = 10 (Clustering or duplicate Key)

so for 100 key is 100%20 = 5  

Now try with table number as prime let 21

so for 10 key is 10%21 = 10  

so for 20 key is 20%21 = 20

so for 30 key is 30%21 = 9

so for 40 key is 40%21 = 19  

so for 50 key is 50%21 = 8

so for 60 key is 60%21 = 18

so for 70 key is 70%21 = 7  

so for 80 key is 80%21 = 17

so for 90 key is 90%21 = 6

so for 100 key is 100%21 = 16