KOB - 4 months ago 24

Java Question

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.