Что такое Double Hashing?

Подробное объяснение Double Hashing (Двойного хеширования)

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

Как работает Double Hashing?

Основная идея заключается в том, чтобы равномерно распределять элементы по таблице даже при высокой нагрузке, избегая кластеризации, типичной для линейного пробирования.

Алгоритм вставки элемента:

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

package main

type HashTable struct {
    size  int
    table []*int
}

func doubleHashInsert(key int, table []*int, size int) int {
    h1 := hash1(key, size)
    step := hash2(key, size)
    
    // Убедимся, что шаг не равен 0 (иначе будем на месте топтаться)
    if step == 0 {
        step = 1
    }
    
    for i := 0; i < size; i++ {
        index := (h1 + i*step) % size
        if table[index] == nil {
            return index // Нашли свободную ячейку
        }
    }
    return -1 // Таблица заполнена
}

// Простая первая хеш-функция
func hash1(key, size int) int {
    return key % size
}

// Вторая хеш-функция должна возвращать значения, взаимно простые с размером таблицы
func hash2(key, size int) int {
    // Часто используют: hash2(key) = R - (key % R), где R - простое число меньше размера таблицы
    return 7 - (key % 7) // 7 - простое число
}

Ключевые требования к хеш-функциям

1. Вторая хеш-функция никогда не должна возвращать 0, иначе мы застрянем в одной ячейке.
2. Желательно, чтобы размер таблицы и шаг были взаимно простыми (для этого размер таблицы часто выбирают простым числом).
3. Хеш-функции должны быть независимыми, чтобы минимизировать вероятность повторных коллизий.

Преимущества Double Hashing

• Сводит к минимуму кластеризацию — элементы не группируются в кластеры как при линейном пробировании.
• Обеспечивает равномерное распределение — даже если два ключа имеют одинаковый hash1, разные hash2 обеспечат разные последовательности проб.
• Эффективен при высокой загрузке — сохраняет хорошую производительность даже при заполненности таблицы 80-90%.

Недостатки и нюансы

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

Сравнение с другими методами пробирования

// Линейное пробирование: step = 1 (постоянный шаг)
// Легко реализовать, но приводит к первичной кластеризации
index := (hash1(key) + i) % size

// Квадратичное пробирование: шаг зависит от квадрата попытки
// Уменьшает кластеризацию, но может не покрыть все ячейки таблицы
index := (hash1(key) + i*i) % size

// Двойное хеширование: шаг вычисляется второй хеш-функцией
// Наиболее равномерное распределение, покрывает все ячейки
index := (hash1(key) + i*hash2(key)) % size

Практическое применение в Go

В стандартной библиотеке Go хеш-таблицы (map) используют более сложные механизмы, но понимание double hashing важно для:

• Реализации собственных специализированных хеш-таблиц
• Решения задач с высокими требованиями к производительности
• Понимания основ Computer Science для технических собеседований

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