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?
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.