В чем преимущество применения сложной хеш-функции и последующего использования mod n вместо простого ввода mod n для ввода?
Давайте посмотрим на простой пример. Скажем, наши ключи - это 100 указателей на некоторые объекты в памяти, которые выровнены по 8 байтов: это означает, что 3 младших бита всегда равны 0. Наш размер таблицы в настоящее время составляет 128 ведер. Перед тем как хэшировать, мы изменили значения указателя на 128, поэтому получаем:
32-bit pointer bits xxxxxxxx xxxxxxxx xxxxxxxx xxxxx000
mod 128 00000000 00000000 00000000 0xxxx000
Обратите внимание, что только 4 потенциально значимых бита из указателя попадают в нашу хеш-функцию, что означает, что не более 16 различных значений достигают хеш-функции: наши 100 указателей будут сталкиваться только в 16 сегментах, что означает, что цепочки столкновений обычно имеют глубину 7 или 8 даже для самой сильной хэш-функции. Это печально, учитывая, что у нас было 128 сегментов для 100 ключей: у нас должно было быть в основном 0, 1 или 2 ключа, сопоставленных с любым конкретным сегментом.
Теперь, что бы произошло, если бы у нас было 100 указателей на области отображения памяти, каждая из которых была выровнена по 4096-байтовой странице? Все они были бы привязаны к одному и тому же ведру.
Не выполнение операции мода до конца гарантирует, что биты старшего разряда в ключах могут помочь рандомизировать позиции битов младшего разряда в хеш-значении, и эти биты младшего разряда могут повлиять на область, в которую преобразуется ключ. (Еще одна вещь, которая может немного помочь, это убедиться, что размер таблицы - это простое число, но лучше всего его использовать в сочетании с выполнением мода после хэширования. В качестве случайной выборки компилятор GNU C ++ использует счетчики простых сегментов для хеш-таблиц стандартной библиотеки, в то время как Visual C ++ использует степень двойки (и для длинных строк быстрее, но более слабые хеш-функции))
Q1) Независимо от того, как мы его хэшируем, оно просто сводится к значению от 0 до n-1 (напоминание при делении на n). Итак, как же важен выбор хеш-функции?
Очевидно, что если бы наша хеш-функция была h(key) { return 0 }, то каждый ключ сталкивался бы в сегменте 0. С другой стороны, криптографическая хеш-функция должна эффективно случайным образом, но многократно отображать любой данный ключ в данный сегмент, так что любой бит изменяется в любом месте ключа создается полностью некоррелированное отображение. Это помогает защитить вас от чрезмерных столкновений с ключами, которые не меняются во многих битовых позициях. Но сильные хеш-функции, как правило, требуют больше времени для вычисления, и уменьшение коллизий может или не может привести к выигрышу в чистой производительности. Иногда стоит выбирать силу хэш-функции, основываясь на знании того, насколько ключи могут отличаться друг от друга.
Q2) Я знаю, что идеальная хеш-функция распределяет входные значения равномерно по сегментам. В этом аспекте эти сложные функции хеширования превосходят функцию идентификации хеша?
В крайнем случае хеш-функции идентичности надеются, что входные числа будут отображаться в отдельные сегменты с большей вероятностью, чем хеш-функция криптографической стойкости: например, если мы хешируем 5, 6, 7, 8, 10 в таблицу, используя это тождественная функция, они плотные (близкие друг к другу) и охватывают всего 6 значений (от 5 до 10), поэтому до тех пор, пока размер таблицы> = 6 (например, простое значение 7), они гарантированно не столкнутся. Но хэш-функции идентичности с учетом склонных к коллизиям входов (например, указатели, приведенные к числам) являются катастрофой, поскольку они ничего не сделали, чтобы смешать более значимые биты с менее значимыми битами до того, как включится мод - та же проблема, что и для указателей выше.
В общем, хэш-функции идентичности могут иметь лучшую производительность в среднем случае для общих целочисленных ключей, но гораздо хуже в худшем случае для неплотных, не случайных / склонных к коллизиям ключей.