Как работает функция двойного хеширования в C++?
Я читал о HashTable и нашел хороший источник, чтобы легко понять здесь.
Но я запутался в функции двойного хеширования. Вот деталь двойной функции хеширования.
Двойное хеширование использует идею применения второй хеш-функции к ключу при возникновении коллизии. Результатом второй хэш-функции будет количество позиций от точки столкновения для вставки.
Есть пара требований для второй функции:
it must never evaluate to 0 must make sure that all cells can be probedПопулярная вторая хеш-функция: Hash2(ключ) = R - (ключ% R), где R - простое число, которое меньше размера таблицы.
и вот изображение двойной хэш-функции.
Теперь начинается смятение. как они говорят в образе. 49 должно быть на 7 позиции из [9] индекс. тогда фактическая позиция будет [6] тогда почему они поставили 49 на [0] индекс? и то же самое для другого оставшегося целого числа.
А что будет, когда не будет пустого индекса?
2 ответа
На самом деле имидж неправильный. Основная идея состоит в том, чтобы прыгать ни на одно из мест по значению, заданному секундой, имеет функцию, если она уже занята, то продолжать прыгать по тому же номеру. мест, пока не будет найдена пустая ячейка. Чтобы это работало, вторая хеш-функция НЕ должна возвращать 0.
Для более подробного объяснения, пожалуйста, смотрите здесь.
Изображение неверно и может использовать другой метод хеширования.
Когда нет пустых ячеек, вам придется перефразировать. См. Раздел "Хеширование с перефразировкой" под секцией двойного хеширования.