Двойная константа хеширования 5?
Я обнаружил множество примеров двойного хэширования. Все примеры говорят мне, что вы должны использовать%5 при хешировании во второй раз.
У меня вопрос почему 5? Это соглашение, что вы всегда используете 5 или как это работает?
один пример: https://www.cs.washington.edu/education/courses/326/00wi/handouts/lecture16/sld025.htm
3 ответа
В хеш-таблице с N местами идея состоит в том, чтобы использовать две независимые хеш-функции h1(ключ) и h2(ключ), а затем использовать последовательность зондирования
h1 % N, (h1 + h2) % N, (h1 + 2*h2) % N, (h1 + 3*h2) % N, ...
Вы хотите убедиться, что наибольший общий делитель h2 и N равен 1, иначе вы не достигнете всех мест в таблице.
Есть несколько схем, которые могут быть достигнуты, например:
- выберите N в качестве простого числа и пусть h2 даст результат в интервале [1, N-1]
- выберите N в качестве степени 2, и пусть h2 даст нечетное число в интервале [1, N-1]
Нет. Вторая функция хеширования может быть любой, какой вы хотите. В идеале, он должен иметь равные шансы достичь каждой ячейки вашего хеш-массива.
Полагаю, вы не искали примеров двойного хеширования из другого источника. Источник, который вы использовали, решил использовать % 5 несколько раз для простоты.
Вы не всегда используете 5 и даже не всегда используете%.
В вашем примере. %7 и%5 - ваши функции хеширования. Однако на самом деле у них могут быть совершенно разные функции.
В этом примере используется%5, потому что он достаточно прост для примера. Единственное реальное требование - две функции независимы.