KOB KOB - 15 days ago 5
Java Question

HashMaps - Unclear on the hash function and double hashing

I have been asked to implement a hash map using an array. I need to insert the following keys:

15, 7, 26, 39, 11, 9, 27, 5, 18, 2, 54, 22, 4


into an array of size 19 using the hash function:

(3x + 7) % 19


Using linear probing, I would expect to get the following array (correct me if I'm wrong):

Index: 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18
Key: 4 11 5 18 7 26 39 27 2 15 9 22 54


where 26 had a collision with 7 at index 9, and so was inserted at index 10, and 39 then had a collision with 26 at index 10 and so was inserted at index 11.

I am now attempting to insert the same elements in an array implementation of a HashMap, using double hashing instead of linear probing. The 2nd hash function I am given is:

11 - (x % 11)


I have two questions:

Does this mean that my array will be of size 11 or still 19?

Do I initially use the original hash function and if the given index is free, insert the element there, otherwise if there is a collision, use the 2nd hash function and insert the element there?

Answer

According to Wikipedia the secondary hash function is used indirectly in the probing function:

h(0, x) = (3x + 7) % 19
h(j, x) =  ((3x + 7) + j(11 - (x % 11))) % 19

Where j is the collision counter.