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

Что вы ожидаете от книги за 1,25 доллара?

Во всяком случае, у меня были годы, чтобы думать о природе математики, и до сих пор не могу понять это.

Является ли распределение чисел действительно более четным, даже если есть простое число сегментов? Или это история старого программиста, которую все принимают, потому что все остальные принимают ее?

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Убедитесь, что вы не генерируете слишком много hashCodes, кратных другому hashCode, как в {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

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

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

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

Лучше спросить, почему именно число 31?

ТЛ; др

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Эту проблему можно устранить, сделав HCF 1. Простые числа очень хороши для этого.

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

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

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

Копирование с моего другого ответа https://stackoverflow.com/a/43126969/917428 . Смотрите его для более подробной информации и примеров.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Как мы получаем уникальный индекс? Делая начальный размер внутреннего контейнера также простым. Таким образом, в основном используется Prime, потому что он обладает уникальной особенностью создания уникальных чисел, которые мы в конечном итоге используем для идентификации объектов и поиска индексов во внутреннем контейнере.

Пример:

ключ = "ключ"

значение = "значение" uniqueId = "k" * 31 ^ 2 + "e" * 31 ^ 1` + "y"

сопоставляет уникальный идентификатор

Теперь мы хотим уникальное место для нашей ценности - поэтому мы

uniqueId % internalContainerSize == uniqueLocationForValueПредполагая internalContainerSizeэто также простое число.

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

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

Основные модули выгодны, потому что:

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

Однако они имеют большой недостаток, они требуют целочисленного деления, которое занимает много (~ 15-40) циклов, даже на современном процессоре. Примерно с половиной вычислений можно убедиться, что хеш очень хорошо перемешан. Два умножения и операции xorshift будут смешиваться лучше, чем простое moudulus. Затем мы можем использовать любой размер хеш-таблицы, и сокращение хеша происходит быстрее всего, что дает 7 операций в общей сложности для мощности двух размеров таблицы и около 9 операций для произвольных размеров.

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

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

Как правило, мощность 2 столов намного быстрее. Там дорогой h % n => h & bitmask, где битовая маска может быть вычислена через clz(«считать ведущие нули») размера n. Функция по модулю должна выполнять целочисленное деление, которое примерно в 50 раз медленнее, чем логическое and. Есть некоторые приемы, которые нужно избегать по модулю, например, использование https://lemire.me/blog/2016/06/27/a/fast-alternative-to-the-modulo-reduction/ Lemire , но обычно быстрые хеш-таблицы используют мощность из 2, и безопасные хеш-таблицы используют простые числа.

Почему так?

Безопасность в этом случае определяется атаками на стратегию разрешения коллизий, которая в большинстве хеш-таблиц представляет собой просто линейный поиск в связанном списке коллизий. Или с более быстрыми таблицами с открытой адресацией линейного поиска в таблице напрямую. Таким образом, имея мощность 2 таблиц и некоторые внутренние знания таблицы, например размер или порядок списка ключей, предоставляемых некоторым интерфейсом JSON, вы получаете количество используемых правильных битов. Количество единиц в битовой маске. Обычно это меньше 10 бит. И для 5-10 битов банальные силовые столкновения тривиальны даже с самыми сильными и самыми медленными хэш-функциями. Вы больше не получаете полную безопасность ваших 32-битных или 64-битных хеш-функций. И дело в том, чтобы использовать быстрые маленькие хэш-функции, а не монстров, таких как ропот или даже сифаш.

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

Таким образом, наилучшие варианты для предотвращения подобных столкновений

1) использовать простые таблицы, потому что тогда

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

2) использовать лучшие меры против фактической атаки, вместе с быстрой силой 2 размера.

• подсчитайте количество столкновений и прервите или спите при обнаруженных атаках, то есть числах столкновений с вероятностью <1%. Как 100 с 32-битными хеш-таблицами. Это то, что делает, например, dnb resolver djb.
• преобразовать связанный список столкновений в дерево с помощью поиска O (log n), а не O (n), когда обнаружена атака столкновений. Это то, что, например, делает Java.

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

Хеш-функции для хеш-таблиц в основном должны быть небольшими (чтобы быть встроенными) и быстрыми. Безопасность может прийти только от предотвращения линейного поиска в столкновениях. И не использовать тривиально плохие хеш-функции, например, нечувствительные к некоторым значениям (например, \ 0 при использовании умножения).

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

function eratosthenes(n) {

    function getPrime(x) {
        var middle = (x-(x%2))/2;
        var arr_rest = [];
        for(var j=2 ; j<=middle;j++){
            arr_rest.push(x%j);
        }

        if(arr_rest.indexOf(0) == -1) {
            return true
        }else {
            return false
        }

    }
    if(n<2)  {
        return []
    }else if(n==2){
        return [2]
    }else {
        var arr = [2]
        for(var i=3;i<n;i++) {
            if(getPrime(i)){
                arr.push(i)
            }
        }
    }

    return arr;
}