Почему размер 127 (prime) лучше 128 для хеш-таблицы?

Предположим, что это простое равномерное хеширование, то есть любое заданное значение одинаково похоже на хэш в любой из слотов хэша. Почему лучше использовать таблицу размером 127, а не 128? Я действительно не понимаю, в чем проблема с мощностью 2 чисел. Или как это вообще имеет значение вообще.

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

Предположим, что возможные элементы находятся только между 1 и 10000, и я выбрал размер таблицы как 128. Как может быть лучше? Итак, 128 - 2 ^ 6 (1000000) и 127 - 0111111. Какая разница? Все числа (при хэшировании) по-прежнему будут бит p младшего разряда k для 127 тоже. У меня что-то не так?

Я ищу несколько примеров, поскольку я действительно не могу понять, почему это плохо. Большое спасибо заранее!

PS: Я знаю: Таблица хэшей: почему размер должен быть простым?

Ответ 1

Все числа (при хэшировании) по-прежнему будут младшими битами младшего разряда k для 127.

Это неправильно (или я неправильно понял..). k % 127 зависит от всех бит k. k % 128 зависит только от 7 младших бит.

EDIT:

Если у вас идеальное распределение между 1 и 10 000. 10,000 % 127 и 10,000 % 128 оба превратят это в превосходное меньшее распределение. Все ковши будут содержать 10 000/128 = 78 (или 79) предметов.

Если у вас есть распределение между 1 и 10000, которое смещено, потому что {x, 2x, 3x,..} встречаются чаще. Тогда основной размер даст гораздо лучшее распределение, как описано в этом . (Если x не является именно таким простым размером.)

Таким образом, отсечение высоких бит (с использованием размера 128) не является проблемой вообще , если распределение в младших битах достаточно хорошее. Но с реальными данными и реальными плохо разработанными хеш-функциями вам понадобятся эти высокие бит.

Ответ 2

Метод разделения

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

- CLRS

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

Ключ можно записать в терминах частного q и остатка r.

k = nq + r

Выбор частного для q = m позволяет написать k % m просто как остаток в приведенном выше уравнении:

k % m = r = k - nm,  where r < m

Следовательно, k % m эквивалентно непрерывному вычитанию m всего n раз (до r < m):

k % m = k - m - m - ... - m,  until r < m

Давайте попробуем хэшировать ключ k = 91 с помощью m = 2⁴ = 16.

  91 = 0101 1011
- 16 = 0001 0000
----------------
  75 = 0100 1011
- 16 = 0001 0000
----------------
  59 = 0011 1011
- 16 = 0001 0000
----------------
  43 = 0010 1011
- 16 = 0001 0000
----------------
  27 = 0001 1011
- 16 = 0001 0000
----------------
  11 = 0000 1011

Таким образом, 91 % 2⁴ = 11 - это всего лишь двоичная форма 91, в которой остаются только младшие бит p=4.

Важное различие:

Это относится конкретно к методу деления хеширования. На самом деле обратное верно для метода умножения, как указано в CLRS:

"Преимущество метода умножения состоит в том, что значение m не является критическим... Обычно мы выбираем [m] как мощность 2, так как тогда мы можем легко реализовать эту функцию на большинстве компьютеров".

Ответ 3

Во-первых, это не о выборе простого номера. Например, если вы знаете, что ваш набор данных будет находиться в диапазоне от 1 до 10000, выбор 127 или 128 не будет иметь никакого значения, если это будет плохой выбор дизайна.

Скорее, лучше выбрать ДЕЙСТВИТЕЛЬНО большое простое, например 3967, для вашего примера, чтобы у каждой информации была своя уникальная пара ключей/значений. Вы просто хотите минимизировать столкновения. Выбор 127 или 128 для вашего примера не будет иметь значения. Bc все коты 127/128 будут равномерно заполнены (это плохо и приведет к ухудшению времени выполнения вставки и поиска O (1) до O (n)), в отличие от 3967 (который сохранит время выполнения O (1))

EDIT # 4

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

Как почему простые числа являются "предпочтительными", рассмотреть "противоборствующий" анализ, Предположим, я разработал общий хеширование структуры данных, как будет ли он выполняться с учетом наихудшего результата от противника. Поскольку производительность диктуется хеширующими столкновениями вопрос становится тем, что хэш использование, которое минимизирует столкновение в худшее состояние. Одним из таких условий является когда ввод всегда числа делится на некоторое целое число, скажем 4. Если вы используете N = 128, то любое число делится на 4 mod 128, все еще делится на 4, что означает только ведра 4, 8, 12,... всегда всегда используется, что приводит к 25% использованию структура данных. Эффективно уменьшает вероятность таких сценарий, с номерами > N.

Ответ 4

Ник прав, что размер хэш-таблицы вообще не имеет значения. Однако в специальном случае, когда используется открытая адресация с двойным хэшированием (в котором интервал между пробками вычисляется другой хэш-функцией), то хэш-таблица простого размера лучше всего, чтобы все записи таблицы хэшей были доступны для нового элемента (как упоминалось в Corkscreewe).

Ответ 5

Если у вас есть идеальная хэш-функция, которая имеет равномерное распределение, тогда это не имеет значения.

Ответ 6

В Википедии есть хорошее резюме:

http://en.wikipedia.org/wiki/Hash_table

Они указывают, что некоторые хэш-функции предназначены для работы ТОЛЬКО с простыми числами. В этой статье объясняется, почему две силы являются плохими:

http://www.concentric.net/~Ttwang/tech/primehash.htm

Ответ 7

Я больше не могу это доказать, хотя я помню, что мне приходилось делать это на экзамене в университете миллион лет назад, но оптимальные размеры хэша не просто просто. Вы хотите выбрать простое число N такое, что N = 4*M − 1 (где M также является целым числом).

Это делает 31 лучшим числом ковшей, чем 29. M равно 8, когда N равно 31, но нет интеграла M, когда N равно 29.

Как я уже сказал, я больше не помню математику, чтобы доказать это. Это было в курсе теории, преподаваемом Рэйчел Манбер, женой Удиса, около 25 лет назад или около того.

Ответ 8

Я считаю, что это просто связано с тем, что компьютеры работают с в основании 2. Что-то подобное происходит с базой 10.

...

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

Из Почему хеш-таблицы должны использовать размер простого числа.

Ответ 9

вот способ понять: "k% 127 зависит от всех бит k. k% 128 зависит только от 7 младших бит"..
k% 128 равно k и (2 ^ 7-1), например: 129% 128 = 1, в двоичном формате: 1000 0001 и 0111 1111 = 0000 0001, любой верхний бит (2 ^ 7-1) будет 0, что означает, что доза не имеет значения, какова высокая позиция. но этот перевод недействителен для чисел, которые не равны 2 ^ n.
теперь давайте посмотрим, как мы делимся на Десятичный 129% 127, сначала посмотрим на самую высокую позицию 1, меньше 127, затем мы получим следующий элемент 2 в сочетании с кулаком, который мы получаем 12, 12 меньше 127, затем объединяем с 9, что означает 129, деленное на 127, осталось 2, мы можем записать это в математике: 129 = 1 * 127 +2, поэтому мы получили 2 [все это называется Long_division], и это то же самое в двоичном делении, теперь мы знаем, что k% 127 зависит от всех бит k