Метод двойного хэширования — это способ разрешения коллизий в хеш-таблицах, при котором при возникновении коллизии вычисляется второй хэш, и следующий индекс для поиска элемента определяется с помощью этого второго хэша.

Идея:

Есть две хэш-функции: h1(key) и h2(key).
При вставке или поиске элемента сначала вычисляем h1(key) — начальный индекс.
Если позиция занята (коллизия), то следующий индекс вычисляется по формуле:

index = (h1(key) + i * h2(key)) mod table_size, где i — номер попытки (0,1,2,...)

Это позволяет обходить коллизии, перемещаясь по таблице с шагом, зависящим от ключа, что уменьшает кластеризацию по сравнению с линейным пробированием.

Пример на Go:

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

Здесь h2 всегда не равен нулю и гарантирует, что мы пройдем всю таблицу, если потребуется.

Можете объяснить принцип метода двойного хэширования для разрешения коллизий в хеш-таблицах?