Jimmy Tan - 1 year ago 61

Java Question

I know that in Double Hashing,

`h1(key) = key mod 11`

h2(key) = 7 - (key mod 7)

The

`h1`

`h2`

But I do not know how to solve for the probe sequence.

For example, if key is

`14`

Can you explain to me why the answer is

`3,10,6,2,9,5,1,8,4,0`

Answer Source

In your example, the size of the table is 11 (positions numbered 0 to 10). The size of the step is the number to add to the current position to get the next position (modulus the size of the table).

```
h1 = 14 mod 11 = 3
h2 = 7 - (14 mod 7) = 7 - 0 = 7
```

So, the first position, call it `p`

, is 3, as given by `h1`

. Each subsequent position, `p'`

is given by --

```
p' = (p + h2) mod table_size
```

for this example,

```
p' = (p + 7) mod 11
```

so, the second position is --

```
(3 + 7) mod 11 = 10 mod 11 = 10
```

and the third is --

```
(10 + 7) mod 11 = 17 mod 11 = 6
```

and so on.