Что такое двойное хеширование (Double Hashing) и как оно решает коллизии?

Двойное хеширование (Double Hashing) — это один из методов разрешения коллизий в хеш-таблицах, относящийся к классу техник открытой адресации.

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

Алгоритм:

1. Вычисляется первичный хеш: h1(key).
2. Если ячейка h1(key) занята, вычисляется вторичный хеш h2(key), который определяет шаг смещения.
3. Последовательно проверяются ячейки: (h1(key) + i * h2(key)) % tableSize для i = 1, 2, 3, ... до тех пор, пока не будет найдена свободная ячейка.

Пример на Go (псевдокод):

// h1 и h2 - разные хеш-функции
// size - размер хеш-таблицы
func findSlotFor(key string, size int) int {
    // Первичный хеш
    h1 := hash1(key) % size
    // Вторичный хеш для шага. Важно, чтобы h2 никогда не возвращал 0.
    h2 := 1 + (hash2(key) % (size - 1))

    for i := 0; i < size; i++ {
        slot := (h1 + i*h2) % size
        if isSlotEmpty(slot) {
            return slot
        }
    }
    // Таблица заполнена
    return -1 
}

Преимущества:

• Минимизирует кластеризацию: Значительно лучше, чем линейное пробирование, так как последовательности проб для разных ключей отличаются.
• Эффективное использование памяти: Не требует дополнительной памяти для хранения списков или деревьев, как в методе цепочек.

Недостатки:

• Вычислительная сложность: Требует вычисления двух хеш-функций вместо одной.
• Сложность реализации: Требуется подобрать хорошую вторую хеш-функцию, которая не возвращает ноль и значение которой является взаимно простым с размером таблицы.