javahashhashmaphashtabledouble-hashing

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?


Solution

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