Should number of buckets be a prime number in a hash table

A little refresher. Given an object, we calculate its hash code, and given its hash code we find the bucket in the hash table. Usually we do it by taking the modulo of the hashcode:

bucket = hashcode % #buckets

If that's the case, the best way to ensure a decent distribution of keys is to choose a prime number for the number of buckets.  Proof follows later.

However, Java doesn't use the approach or using the mod function to map key to bucket, and they don't trust the quality of the original hashcodes, so they are modified further inside the hash map implementation.

Well, if bucket number had been determined using a mod operation, would it matter if number of buckets was prime?  Yes.

As an illustrative example, consider number 7 (prime) and 9 (non-prime) used as number of buckets.
Note what happens with hashcodes divisible by 3 and 7.

key  bucket                bucket
       (if 7 buckets)   (if 9 buckets)
3   3                   3
6   6                   6
7   0                   7
9   2                   0
14  0                   5
18  4                   0
27  6                   0

Because number 9 isn't prime, it can be expressed as 3 x 3,
so when we use keys that are multiples of 3, they all fall
in only 3 buckets (0, 3, 6).  Other keys are uniformly distributed
when bucket number is 9.


3                       3
6                       6
9                       0
12                      3
15                      6
18                      0
21                      3
24                      6
27                      0

When using number of buckets as 7, only multiples of 7 are put
in the same bucket (same as when multiples of 9 are put in
the same bucket).  The difference here that in case of non-prime number
of buckets there are more cases when keys are unevenly distributed.

A more formal proof could be along these lines:

modulo operation is
    mod(n) = r
if
    n = mq + r
above, m is number of buckets, so
    n = 9q + r
resulting bucket where key is mapped is
    r = n - 9q
what if we're only looking at multiples of 3, so k*3,
how to prove that there are fewer outputs:
    r = 3k - 9q
    r = 3(k - 3q)
So no matter what the input key is, the output is tripled,
which means that for every bucket for which key is mapped into,
there are two buckets that were skipped.