Что такое Double Hashing

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

Пример:

func doubleHash(key string, size int) int {
    h1 := hash1(key) % size
    h2 := hash2(key) % (size - 1) + 1 // Гарантируем, что шаг ≠ 0
    for i := 0; ; i++ {
        slot := (h1 + i*h2) % size
        if isSlotEmpty(slot) {
            return slot
        }
    }
}

Плюсы:

• Уменьшает кластеризацию по сравнению с линейным пробированием.
• Обеспечивает равномерное распределение.

Минусы:

• Требует двух хеш-функций.
• Может быть медленнее, чем другие методы (например, цепочки).