hashtable size and significant bits of key

问题:

I have a question regarding hashtable size and modular hashing. The hashing algorithm I'm referring to is the following: hash_key % table_size = array_index. I'm reading an algorithms textbook where the following bit of advice is given:

If the table size is not prime, it may be the case that all of the bits of the key do not play a role in determining the array_index.

Can anyone explain what this means exactly with an example?

回答1:

What you want to avoid is common factors. There is a theorem that states that every number can be expressed as a product of prime numbers.

So as a consequence if you have a prime number as a mod. You will not share any factors in the division.

say A % 30, so any multiple of 2, 3 and 5 will share the factors in the division and that factor will be useless in the division.

250/30 = 50 / 6 = 25 / 3

You want to minimize useless factors.