Хеш-функции и таблицы размером вида 2 ^ p

Question

При расчете индекса сегмента хеш-таблицы из хеш-кода ключа, почему мы избегаем использования остатка после деления (по модулю), когда размер массива сегментов равен степени 2?

Answer 1

При вычислении хэша вы хотите получить как можно больше информации, с которой можно дешево разбираться, с хорошим распределением по всему диапазону битов: например, 32-разрядные целые числа без знака обычно хороши, если у вас нет много (> 3 миллиардов) элементов для хранения в хеш-таблице.

Это преобразование хеш-кода в индекс сегмента, который вас действительно интересует. Когда количество сегментов n равно степени двух, все, что вам нужно сделать, это выполнить операцию И между хеш-кодом h и (n 1), а результат равен h mod n.

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

Answer 2

Допустим, размер таблицы равен m = 2 ^ p. Пусть k будет ключом. Тогда всякий раз, когда мы делаем k mod m, мы получим только последние p бит двоичного представления k. Таким образом, если я добавлю несколько ключей с одинаковыми последними p-битами, хеш-функция будет работать ОЧЕНЬ ОЧЕНЬ плохо, поскольку все ключи будут хэшированы в один и тот же слот в таблице. Таким образом, избегайте сил 2