Как выбрать по модулю для целого или строкового хэша?

Question

Обычно мы выполняем хеширование, вычисляя integer или string в соответствии с правилом, а затем возвращаем hash(int-or-str) % m в качестве индекса в хэш-таблице, но как выбрать модуль по модулю m?Есть ли соглашение, которому нужно следовать?

Answer 1

Есть два возможных соглашения. Одним из них является использование простого числа, которое дает хорошую производительность при квадратичном зондировании .

Другой - использовать степень двойки, поскольку n mod m , где m = 2 ^ k - быстрый операция; это побитовое И с m -1. Конечно, модуль должен быть равен размеру хеш-таблицы, а степень двойки означает, что ваша хеш-таблица должна удваиваться в размерах, когда она переполнена. Это дает амортизированную вставку O (1) аналогично динамическому массиву .

Answer 2

Поскольку [val modulo m] используется в качестве индекса для таблицы, m - это количество элементов в этой таблице.Вы можете выбрать это?Тогда используйте достаточно большое простое число.Если вам нужно изменить размер таблицы, вы можете либо выбрать большее простое число, либо (если вы решите удвоить таблицу для изменения размера), вам лучше убедиться, что у вашей хэш-функции достаточно энтропии в младших битах.