Kas saaksite selgitada topelt-hashimise meetodi põhimõtet kolitsioonide lahendamiseks hash-tabelites?

Double hashing method is a way to resolve collisions in hash tables, where upon collision, a second hash is computed, and the next index for searching the 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 by 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 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 needed.