Ответ 1

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

(first char) + k * (second char) + k^2 * (third char) + ...

Затем, если в комплект подана группа строк, каждая из которых имеет тот же самый первый char, то результаты будут одинаковыми по модулю k, по крайней мере, до тех пор, пока не будет переполнен целочисленный тип.

[В качестве примера, строка строки hashCode строки очень похожа на это - это символы обратного порядка, с k = 31. Таким образом, вы получаете поразительные отношения по модулю 31 между строками, которые заканчиваются одинаково, и поразительные отношения по модулю 2 ^ 32 между строками, которые остаются теми же, кроме конца. Это не серьезно испортило поведение hashtable.]

Хэш-таблица работает, беря модуль хеша над количеством ведер.

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

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

Оказывается, что "из-за природы математики", если константа, используемая в хеше, и количество ведер, coprime, тогда столкновения сведено к минимуму в некоторых распространенных случаях. Если они не coprime, то есть довольно простые отношения между входами, для которых не минимизированы столкновения. Все хеши выходят одинаково по модулю общего коэффициента, а это означает, что все они попадут в 1/n-й из ковшей, которые имеют это значение по модулю общего коэффициента. Вы получаете n раз столько же столкновений, где n - общий фактор. Поскольку n равно по крайней мере 2, я бы сказал, что неприемлемо для довольно простого варианта использования, чтобы генерировать по крайней мере вдвое больше коллизий, чем обычно. Если какой-то пользователь нарушит наше распределение в ведрах, мы хотим, чтобы это было несчастным случаем, а не простое предсказуемое использование.

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

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

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

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

[Edit: есть еще одна, более специализированная причина использовать простое число ковшей, которое есть, если вы обрабатываете столкновения с линейным зондированием. Затем вы вычисляете шаг из хэш-кода, и если этот шаг окажется фактором подсчета ведра, вы можете делать только (bucket_count/stride) зонды, прежде чем вы вернетесь туда, где вы начали. Случай, который вы больше всего хотите избежать, - это stride = 0, конечно, который должен быть специально обрезанным, но для того, чтобы исключить значение bucket_count/stride с особыми условиями, равное маленькому целому числу, вы можете просто сделать bucket_count простым и не заботясь о том, что stride при условии, что он не равен 0.]

Ответ 2

Первое, что вы делаете при вставке/выходе из хеш-таблицы, - это вычисление хэш-кода для данного ключа, а затем поиск правильного ведра путем обрезки хэш-кода на размер хеш-таблицы путем выполнения hashCode% table_length. Вот 2 "заявления", которые вы, скорее всего, где-то читали

• Если вы используете значение 2 для table_length, поиск (hashCode (key)% 2 ^ n) так же прост и быстр, как (hashCode (key) и (2 ^ n -1)). Но если ваша функция для вычисления hashCode для заданного ключа не подходит, вы, безусловно, страдаете от кластеризации многих ключей в нескольких хэш-кодах.
• Но если вы используете простые числа для table_length, вычисляемые хэш-коды могут отображаться в разных хэш-ведрах, даже если у вас есть немного глупая функция hashCode.

И вот доказательство.

Если предположим, что ваша функция hashCode приводит к следующим хэш-кодам среди других {x, 2x, 3x, 4x, 5x, 6x...}, то все они собираются в виде всего m кол-во ведер, где m = table_length/GreatestCommonFactor (table_length, x). (Тривиально проверить/вывести это). Теперь вы можете сделать одно из следующих действий, чтобы избежать кластеризации

Убедитесь, что вы не генерируете слишком много хэш-кодов, которые являются кратными другому хэш-коду, например, в {x, 2x, 3x, 4x, 5x, 6x...}. Но это может быть довольно сложно, если ваш hashTable должен иметь миллионы записей. Или просто сделайте m равным table_length, сделав GreatestCommonFactor (table_length, x) равным 1, то есть сделав table_length взаимно просты с x. И если x может быть почти любым числом, тогда убедитесь, что table_length является простым числом.

От - http://srinvis.blogspot.com/2006/07/hash-table-lengths-and-prime-numbers.html

Ответ 3

http://computinglife.wordpress.com/2008/11/20/why-do-hash-functions-use-prime-numbers/

Довольно четкое объяснение, с картинками тоже.

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

Лучший вопрос: почему именно число 31?

Ответ 4

TL;DR

index[hash(input)%2] приведет к столкновению для половины всех возможных хэшей и диапазона значений. index[hash(input)%prime] приводит к столкновению < 2 всех возможных хешей. Фиксирование делителя на размер таблицы также гарантирует, что число не может быть больше, чем таблица.

Ответ 5

Премывания используются, потому что у вас есть хорошие шансы получить уникальное значение для типичной хэш-функции, которая использует полиномы по модулю P. Скажем, вы используете такую ​​хэш-функцию для строк длины <= N, и у вас есть столкновение. Это означает, что 2 разных многочлена производят одно и то же значение по модулю P. Разность этих многочленов снова является полиномом той же степени N (или меньше). Он имеет не более N корней (здесь характер самой математики проявляется, так как это утверждение справедливо только для полинома над полем = > простое число). Поэтому, если N намного меньше P, вы, вероятно, не столкнетесь. После этого эксперимент, вероятно, может показать, что 37 достаточно велик, чтобы избежать столкновений для хэш-таблицы строк, длина которых 5-10, и достаточно мала для использования для расчетов.

Ответ 6

Просто, чтобы предоставить альтернативную точку зрения на этом сайте:

http://www.codexon.com/posts/hash-functions-the-modulo-prime-myth

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

Ответ 7

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

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

Однако использование простых чисел является старым техника. Ключ здесь, чтобы понять что до тех пор, пока вы можете создать достаточно уникальный ключ, который вы можете перемещать к другим методам хэширования тоже. Идти здесь, чтобы узнать больше об этой теме http://www.azillionmonkeys.com/qed/hash.html

http://computinglife.wordpress.com/2008/11/20/why-do-hash-functions-use-prime-numbers/

Ответ 8

Это зависит от выбора хэш-функции.

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

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

С другой стороны, эти факторы обычно состоят из нечетных простых чисел, поэтому вы также должны быть безопасны, используя полномочия двух для своей хэш-таблицы (например, Eclipse использует 31, когда генерирует метод Java hashCode()).

Ответ 9

Предположим, что ваш размер таблицы (или номер по модулю) - T = (B * C). Теперь, если хэш для вашего ввода похож на (N * A * B), где N может быть любым целым числом, тогда ваш вывод будет не очень хорошо распределен. Поскольку каждый раз, когда n становится C, 2C, 3C и т.д., Ваш выход начнет повторяться. т.е. ваш выход будет распределен только в положениях С. Обратите внимание, что здесь C (T/HCF (размер таблицы, хеш)).

Эта проблема может быть устранена с помощью HCF 1. Для этого очень хорошие номера.

Еще одна интересная вещь, когда T равно 2 ^ N. Они выдадут результат точно так же, как и все младшие N бит входного-хеша. Поскольку каждое число может быть представлено степенями 2, когда мы будем брать по модулю любого числа с T, мы вычтем все степени 2-го числа форм, которые являются >= N, и, следовательно, всегда выдает число определенного шаблона, зависящее от ввода, Это также плохой выбор.

Аналогично, T как 10 ^ N также плохо из-за аналогичных причин (шаблон в десятичной нотации чисел вместо двоичного).

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

Ответ 10

Я хотел бы добавить что-то для ответа Стива Джессопа (я не могу комментировать его, так как у меня недостаточно репутации). Но я нашел полезный материал. Его ответ очень помогает, но он допустил ошибку: размер ведра не должен быть сильным 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 не изменяет его хеш-значение.

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

Ответ 11

Копирование из моего другого ответа fooobar.com/questions/5346/.... См. Подробности и примеры.

Я считаю, что это связано с тем, что компьютеры работают в базе 2. Просто подумайте, как одно и то же работает для базы 10:

• 8% 10 = 8
• 18% 10 = 8
• 87865378% 10 = 8

Не имеет значения, какое число: до тех пор, пока оно заканчивается на 8, его по модулю 10 будет 8.

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

Ответ 12

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

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

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

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

Ответ 13

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

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

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

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

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

Как мы получаем уникальный индекс? Сделав начальный размер внутреннего контейнера простым. Таким образом, в основном, премьер участвует, потому что он обладает этой уникальной чертой для создания уникальных чисел, которые мы в конечном итоге используем для объектов ID и находим индексы внутри внутреннего контейнера.

Пример:

key = "key"

value = "value" uniqueId = "k" * 31 ^ 2 + "e" * 31 ^ 1` + "y"

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

Теперь мы хотим уникальное местоположение для нашего значения - так что мы

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

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