Почему хэш-функции должны использовать модуль простых чисел?

Question

Давным-давно я купил книгу со структурами данных за столом сделок за 1,25 доллара. В этом объяснении хеширующей функции сказано, что она должна в конечном итоге изменяться на простое число из-за «природы математики».

Что вы ожидаете от книги за 1,25 доллара?

Во всяком случае, у меня были годы, чтобы думать о природе математики, и до сих пор не могу понять это.

Действительно ли распределение чисел действительно больше, даже если есть простое число сегментов? Или это история старого программиста, которую все принимают, потому что все иначе принимают ее?

Answer 1

Я бы хотел добавить кое-что для ответа Стива Джессопа (я не могу это комментировать, так как у меня недостаточно репутации). Но я нашел несколько полезных материалов. Его ответ очень помогает, но он допустил ошибку: размер корзины не должен быть степенью 2. Я просто процитирую из книги «Введение в алгоритм» Томаса Кормена, Чарльза Лайзерсена и др. На стр. 263:

При использовании метода деления мы обычно избегаем определенных значений m. Например, m не должно быть степенью 2, так как если m = 2 ^ p, то h (k) - это просто p младших битов k. Если мы не знаем, что все p-битовые комбинации младших разрядов одинаково вероятны, нам лучше разработать хеш-функцию, которая будет зависеть от всех битов ключа. Как показано в упражнении 11.3-3, выбор m = 2 ^ p-1, когда k - это символьная строка, интерпретируемая в radix 2 ^ p, может быть плохим выбором, поскольку перестановка символов k не меняет его хеш-значения.

Надеюсь, это поможет.

Answer 2

Я читал популярный веб-сайт WordPress, на который есть ссылки на некоторые из приведенных выше популярных ответов вверху. Из того, что я понял, я хотел бы поделиться простым наблюдением, которое я сделал.

Вы можете найти все подробности в статье здесь , но примите во внимание следующее:

• Использование простого числа дает нам «лучший шанс» уникального значения

Общая реализация hashmap хочет, чтобы две вещи были уникальными.

• Уникальный хеш-код для клавиши
• Уникальный индекс для хранения фактического значения

Как получить уникальный индекс? Делая начальный размер внутреннего контейнера также простым. Таким образом, в основном используется Prime, потому что он обладает уникальной особенностью создания уникальных чисел, которые мы в конечном итоге используем для идентификации объектов и поиска индексов внутри внутреннего контейнера.

* +1032 * Пример: * 1 033 *

ключ = "ключ"

значение = "значение" uniqueId = "k" * 31 ^ 2 + "e" * 31 ^ 1` + "y"

отображается на уникальный идентификатор

Теперь нам нужно уникальное местоположение для нашей стоимости - поэтому мы

uniqueId % internalContainerSize == uniqueLocationForValue, предполагая, что internalContainerSize также является простым числом.

Я знаю, что это упрощено, но я надеюсь донести общую идею до конца.

Answer 3

Для хэш-функции важно не только минимизировать коллизии в целом, но и сделать невозможным использование одного и того же хеша при изменении нескольких байтов.

Скажем, у вас есть уравнение: (x + y*z) % key = x с 0<x<key и 0<z<key. Если ключ является простым числом n * y = ключ равен true для каждого n в N и false для любого другого числа.

Пример, где ключ не является основным примером: х = 1, z = 2 и ключ = 8 Поскольку ключ / z = 4 все еще является натуральным числом, 4 становится решением для нашего уравнения, и в этом случае (n / 2) * y = ключ является истинным для каждого n в N. Количество решений для уравнения практически удвоилось потому что 8 не простое число.

Если наш злоумышленник уже знает, что 8 является возможным решением для уравнения, он может изменить файл с создания 8 на 4 и все еще получает тот же хеш.