The hash function used in double hashing is of the form:

Correct formula: h(k,i) = (h1(k) + i * h2(k)) mod m.

Explanation:

• h1(k) gives the initial probe position (for i = 0).

• h2(k) provides a step size that is multiplied by the probe number i, so each successive probe moves by a multiple of h2(k). This helps avoid primary clustering common in linear probing.

• Choose h2(k) so it is nonzero and preferably relatively prime to m to ensure the probe sequence can cover the whole table (no short cycles). A common choice is h2(k) = 1 + (k mod (m-1)).

Short comparison:

• Linear probing uses an offset proportional to i (for example h(k,i)= (h1(k)+i) mod m), which causes clustering.

• Double hashing multiplies i by a key-dependent second hash, producing different probe sequences for different keys and reducing clustering.

Example:

1. Let m = 10, h1(k) = 3, h2(k) = 4.

2. i = 0: index = (3 + 0*4) mod 10 = 3

3. i = 1: index = (3 + 1*4) mod 10 = 7

4. i = 2: index = (3 + 2*4) mod 10 = 1

5. i = 3: index = (3 + 3*4) mod 10 = 5

Summary: The defining feature of double hashing is that the second hash function determines the step size and is multiplied by the probe number i to compute successive probe indices.