Review question 2e) iii

cs240

2011-12-11 04:48:00 UTC

You are right. In this case, using k mode 32 would indeed give us a more
uniform distribution of the hash values. I forgot about the fact that the
U is given in the question. So yes, the answer should be k mod 32. In
practice prime number is often used because prime numbers generally give a
better distribution to the keys: even somewhat "structured" data is
probably not likely to have a non-uniform distribution. When using double
hashing, it also ensures that the secondary hash function will cycle
through all the slots before repeating and different keys will result in
different probe sequences.

I apologize for the mistake and thank you for bringing this up.

Vivian

Post by TT
I still do not understand why the correct hash function should be
H(k)= k mod 31 instead of H(k)=k mod 32
if the hash function is the first one.
Then the first 8 addresses (00000 to 00100) would have 9 possible
element to be put in, while address from 00101 to 11110 would each
have 8 possible elements that would be hashed into. and none of the
possible element can hash into address 11111
However if the hash function is the second one.
Each address will all have exactly 8 possible element that can be
hashed into.
I know that 32 is not a prime number, but it does a better job at
distributing the positions than 31.
So why does hash function always need to be a prime number?