Will Java's hashCode() reduce collisions regardless of table size?

Question

for a class project we have to count the number of collisions from inserting words from a plaintext document into a hashtable. I read that using prime numbers for table sizes can offset the collisions resulting from a poor hashing function.

Do I have to create a poor hashing function to demonstrate the effects of table sizes on collision? Right now I am using Java's native hashCode() method as the key and am passing it into a hashing function to get the index. I passed the generated hashCode into variations of hashing functions, but found no difference in # of collisions between prime/non-prime table sizes.

//Hashing function   
    scale = rand.nextInt(prime−1) + 1;
    shift = rand.nextInt(prime);    
    private int hashValue(K key) {
                return (int) ((Math.abs(key.hashCode()*scale + shift) % prime) }

I also implemented quadratic probing, but my book says it should result in more collisions if the table size is non-prime.. I would really appreciate your advice.

Answer 1

Java's default implementation for hashCode() is probably doing quite a good job. If you were designing (or implementing) a language then you'd want to design your hashing function perform well. So yes, you should be generating your own hash codes.

If hash codes are more-or-less random (as they should be) then table size does not matter at all. Table size only starts to matter when the hash function is poor.

Suppose that, by some fluke, your hash function only output even numbers. Then, if the table size also were even, you'd only ever use half of the slots in your table (the even ones) - more than doubling the collision rate.

Now suppose that, all hash codes are $1$ modulo $3$. If your table size is a multiple of three, then you'd only ever use slots that are $1$ modulo $3$, cutting the effective size of your table by third.

The reason you want to pick a prime as table size is that this avoids any issues with poor hash functions (unless your hash codes all happen to be the same modulo that prime). On the other hand, picking $223092870$ as table size is a terrible idea.