Can you explain the double hashing method for collision resolution in hash tables?

Double hashing is a collision resolution method in hash tables where, upon a collision, a second hash is computed, and the next index for searching for an element is determined using this second hash.

Idea:

• There are two hash functions: h1(key) and h2(key).

• When inserting or searching for an element, first compute h1(key) — the initial index.

• If the position is occupied (collision), the next index is calculated using the formula:

  index = (h1(key) + i * h2(key)) mod table_size, where i is the attempt number (0,1,2,...)

This allows avoiding collisions by moving through the table with a step size dependent on the key, reducing clustering compared to linear probing.

Example in Go:

func doubleHashing(key int, i int, tableSize int) int {
    h1 := key % tableSize
    h2 := 1 + (key % (tableSize - 1))
    return (h1 + i*h2) % tableSize
}

Here, h2 is always non-zero and guarantees that we will traverse the entire table if necessary.