структуры данных — как работает функция двойного хеширования в 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] индекс? и то же самое для другого оставшегося целого числа.
А что будет, когда не будет пустого индекса?
Решение
Действительно изображение неправильно. Основная идея состоит в том, чтобы прыгать ни на одно из мест по значению, заданному секундой, имеет функцию, если она уже занята, то продолжать прыгать по тому же номеру. мест, пока не будет найдена пустая ячейка. Чтобы это работало, вторая хеш-функция НЕ должна возвращать 0.
Для более подробного объяснения, пожалуйста, смотрите Вот.
Другие решения
Изображение неверно и может использовать другой метод хеширования.
Когда нет пустых ячеек, вам придется перепев. См. Раздел «Хеширование с перефразировкой» ниже раздела «Двойное хеширование».
detector