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

Question

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

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

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

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

PS: мне известно о: Хеш-таблица: почему размер должен быть простым?

Answer 1

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

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

---

EDIT:

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

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

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

Answer 2

Метод деления

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

- CLRS

Чтобы понять, почему m = 2<sup>p</sup> использует только 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<sup>4</sup> = 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<sup>4</sup> = 11 - это просто двоичная форма 91 с оставшимися только p=4 младшими битами.

---

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

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

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

Answer 3

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

Answer 4

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

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

РЕДАКТИРОВАТЬ # 4

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

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

Answer 5

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

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

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

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

Answer 6

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

Answer 7

вот способ понять: «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

Answer 8

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

...

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

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

Answer 9

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

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

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