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

Question

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

Тип вопроса: Общие Backend Вероятность: 10% Категория: Golang Разработчик

Ответ

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

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

Алгоритм:

Вычисляется первичный хеш: h1(key).
Если ячейка h1(key) занята, вычисляется вторичный хеш h2(key), который определяет шаг смещения.
Последовательно проверяются ячейки: (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 
}

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

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

Недостатки:

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

Ответ 18+ 🔞

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

Смотри, обычное хеширование — это как ключ от одной квартиры. Пришел, хуяк ключом — о, бля, занято, какой-то мудак уже там сидит. Что делать? В линейном пробировании ты идешь как лох по порядку: соседняя квартира, следующая... Все такие же лохи так делают, и в итоге у подъезда образуется пиздец — толпа, кластеризация, все друг на друге висят.

А тут придумали, блядь, гениальную вещь. У тебя не один ключ, а два, ёпта! Первый — это твой основной ключ от подъезда, h1(key). Ты прикладываешь — охуенно, но квартира занята. Вместо того чтобы тупо стучаться в соседнюю, ты, хитрая жопа, достаёшь второй, запасной ключ — h2(key). Это ключ не от квартиры, а, типа, от лестничного пролёта. Он говорит тебе: "Иди, дружок, не на одну дверь дальше, а, допустим, на пять". И ты прыгаешь через эти пять дверей: (h1 + i * h2) % размер_таблицы.

Вот смотри, как это выглядит в коде, если бы его писал не заумный дядя, а нормальный человек:

// h1 и h2 — две разные, блядь, функции. Как два разных отмычка.
// size — это сколько всего у нас квартир в этом долбаном доме.
func найдиМесто(ключ string, размер int) int {
    // Пробуем главным ключом
    h1 := хеш1(ключ) % размер
    // А вот тут хитрость, сука! Второй ключ НИКОГДА не должен быть нулём.
    // Иначе будешь тупо долбиться в одну и ту же дверь. Как тот Герасим с Муму.
    h2 := 1 + (хеш2(ключ) % (размер - 1))

    for i := 0; i < размер; i++ {
        слот := (h1 + i*h2) % размер // Прыжок через h2 дверей!
        if слотСвободен(слот) {
            return слот // О, наконец-то, пусто! Заселяемся.
        }
    }
    // Если тут оказались — пиши пропало. Дом забит под завязку, овердохуища народу.
    return -1
}

Чем это, блядь, круто:

Кластеризации — пиздец. Все не толпятся у одного подъезда, потому что у каждого свой, ебаный, шаг смещения. Красота!
Памяти жрёт как суслик. Не надо, как в методе цепочек, за каждым жильцом таскать связку соседей — все лежат в своих ячейках рядами.

А чем сосёт:

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

Короче, метод охуенный, если всё правильно настроить. А если накосячить со второй функцией — будет как в том анекдоте: "Иди нахуй", — сказал монтёр, и пошёл по второму кругу.