Hashtables: Double hashing when the second hash function returns a multiple of the table size

Question

I am implementing a HashTable in C++, using open addressing via double hashing.

I understand that the basic principle behind double hashing is that:

indexInProbingSequence = (originalIndex + i * hashFunction2(key)) % tableSize

I think I have implemented this part correctly. This is for a homework assignment, and it is the policy of the class that I cannot ask advice on any specific piece of code, so you will have to trust me on that part.

What seems to be causing me problems is that occasionally, some keys, when subjected to the second hash function, return a value that is a multiple of the (prime) table size. In these cases, all the indices in the probing sequence are the same. For example, when:

originalIndex = 32
hashFunction2(key) = 3035446
tableSize = 211

The probing sequence is:

(32 + 1 * 3035446) % 211 == 32
(32 + 2 * 3035446) % 211 == 32

and so on.

What am I missing?

Answer 1

I don't think you've missed anything, and in particular the problem arises regardless of table size when hashFunction2(key) == 0.

Use (hashFunction2(key) % (tableSize - 1) + 1) in place of hashFunction2(key). It's desirable that the stride is a generator of the ring modulo the table size (which is a posh way of saying that your probe eventually covers the whole table), or failing that at least has a large period. Since your table size is prime that just means you have to avoid 0.