Почему хороший выбор мода «просто не слишком близко к точному 2»

Question

Чтобы создать хеш-функцию, скопируйте ключ k в один из m слотов, взяв остаток k, деленный на m. То есть, хеш-функция

h (k) = k mod m.

Я прочитал в нескольких местах, что хороший выбор м будет

1. Наглядный - Я понимаю, что мы хотим, чтобы удалить общие факторы, следовательно, простое число выбрано
2. не слишком близко к точная сила 2 - почему?

Answer 1

От Введение в алгоритмы:

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

Как вы видите изображение ниже, если я выбрал 2^3, что означает p = 3 и m = 8. Хешированные ключи зависят только от младших 3 (p) бит, что плохо, потому что когда вы используете хэш, вы хотите включить как можно больше данных для хорошего распространения.