Хэш-функция

Сопоставление произвольных данных со значениями фиксированного размера

Хэш-функция, которая сопоставляет имена целым числам от 0 до 15. Между ключами «Джон Смит» и «Сандра Ди» возникает конфликт .

Хэш -функция — это любая функция , которую можно использовать для сопоставления данных произвольного размера со значениями фиксированного размера, хотя существуют некоторые хэш-функции, которые поддерживают вывод переменной длины. ^[1] Значения, возвращаемые хэш-функцией, называются хеш-значениями , хэш-кодами , хэш-дайджестами , дайджестами или просто хэшами . ^[2] Значения обычно используются для индексации таблицы фиксированного размера, называемой хеш-таблицей . Использование хеш-функции для индексации хеш-таблицы называется хешированием или адресацией рассеянного хранилища .

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

Использование хэш-функций основано на статистических свойствах взаимодействия ключей и функций: поведение в худшем случае невыносимо плохо, но редко, а поведение в среднем случае может быть почти оптимальным (минимальное столкновение ). ^{[3] : 527}

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

Обзор

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

Можно считать, что хеш-функция выполняет три функции:

• Преобразуйте ключи переменной длины в значения фиксированной длины (обычно длины машинного слова или меньше), складывая их по словам или другим единицам с помощью оператора, сохраняющего четность, такого как ADD или XOR.
• Зашифруйте биты ключа так, чтобы полученные значения были равномерно распределены по пространству ключей.
• Сопоставьте ключевые значения со значениями, меньшими или равными размеру таблицы.

Хорошая хеш-функция удовлетворяет двум основным свойствам: 1) она должна вычисляться очень быстро; 2) следует минимизировать дублирование выходных значений (коллизии). Хэш-функции полагаются на создание благоприятных распределений вероятностей для своей эффективности, сокращая время доступа почти до постоянного значения. Высокие коэффициенты загрузки таблицы, патологические наборы ключей и плохо спроектированные хеш-функции могут привести к тому, что время доступа будет приближаться к линейному по количеству элементов в таблице. Хэш-функции могут быть разработаны так, чтобы обеспечить наилучшую производительность в наихудшем случае, ^{[Примечания 1]} хорошую производительность при высоких коэффициентах загрузки таблицы, а в особых случаях - идеальное (без коллизий) отображение ключей в хеш-коды. Реализация основана на битовых операциях с сохранением четности (XOR и ADD), умножении или делении. Необходимым дополнением к хеш-функции является метод разрешения коллизий, который использует вспомогательную структуру данных, такую ​​​​как связанные списки , или систематическое исследование таблицы для поиска пустого слота.

Хэш-таблицы

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

Специализированное использование

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

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

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

Хэш-таблицы также используются для реализации ассоциативных массивов и динамических наборов . ^[5]

Характеристики

Единообразие

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

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

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

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

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

Тестирование и измерение

При тестировании хеш-функции равномерность распределения хеш-значений можно оценить с помощью теста хи-квадрат . Этот тест представляет собой меру согласия: это фактическое распределение элементов в корзинах по сравнению с ожидаемым (или равномерным) распределением элементов. Формула: ${\displaystyle {\frac {\sum _{j=0}^{m-1}(b_{j})(b_{j}+1)/2}{(n/2m)(n+2m-1)}}}$

где: количество ключей, количество сегментов, количество элементов в сегменте ${\displaystyle n}$ ${\displaystyle m}$ ${\displaystyle b_{j}}$ ${\displaystyle j}$

Отношение в пределах одного доверительного интервала (0,95–1,05) указывает на то, что оцениваемая хеш-функция имеет ожидаемое равномерное распределение.

Хэш-функции могут иметь некоторые технические свойства, которые повышают вероятность того, что они будут иметь равномерное распределение при применении. Одним из них является строгий лавинный критерий : всякий раз, когда один входной бит дополняется, каждый из выходных битов изменяется с вероятностью 50%. Причиной этого свойства является то, что выбранные подмножества пространства ключей могут иметь низкую изменчивость. Чтобы выходные данные были равномерно распределены, небольшая степень изменчивости, даже один бит, должна трансформироваться в высокую степень изменчивости (т. е. распределение по табличному пространству) в выходных данных. Каждый бит должен меняться с вероятностью 50%, потому что, если некоторые биты не хотят меняться, ключи группируются вокруг этих значений. Если биты хотят измениться слишком быстро, отображение приближается к фиксированной функции XOR одного бита. В литературе описаны стандартные тесты на это свойство. ^[6] Здесь оценивается релевантность критерия мультипликативной хэш-функции. ^[7]

Эффективность

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

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

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

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

Мы можем позволить, чтобы размер таблицы n не был степенью 2 , и при этом нам не нужно было выполнять какие-либо операции остатка или деления, поскольку эти вычисления иногда являются дорогостоящими. Например, пусть n будет значительно меньше 2 ^b . Рассмотрим функцию генератора псевдослучайных чисел P (ключ) , равномерную на интервале [0, 2 ^b  − 1] . Хеш-функция, равномерная на интервале [0, n -1] , равна n P (key)/2 ^b . Мы можем заменить деление сдвигом вправо (возможно, быстрее) : nP (ключ) >> b .

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

Универсальность

Универсальная схема хеширования — это рандомизированный алгоритм , который выбирает хеш-функцию h среди семейства таких функций таким образом, что вероятность столкновения любых двух различных ключей равна 1/ m , где m — количество различных значений хеш-функции. желаемый — независимо от двух ключей. Универсальное хеширование гарантирует (в вероятностном смысле), что приложение хеш-функции будет вести себя так же, как если бы оно использовало случайную функцию, при любом распределении входных данных. Однако в нем будет больше коллизий, чем при идеальном хешировании, и может потребоваться больше операций, чем в хеш-функции специального назначения.

Применимость

Хэш-функция, которая допускает только определенные размеры таблиц, строки только до определенной длины или не может принимать начальное число (т. е. разрешает двойное хеширование), не так полезна, как та, которая это делает. ^{[ нужна цитата ]}

Хэш-функция применима в самых разных ситуациях. В частности, в криптографии, известные приложения включают: ^[8]

• Проверка целостности: идентичные значения хеш-функции для разных файлов подразумевают равенство, обеспечивая надежные средства обнаружения изменений файлов.
• Вывод ключа: незначительные входные изменения приводят к случайному изменению выходных данных, известному как свойство диффузии. Таким образом, хэш-функции полезны для функций вывода ключей.
• Коды аутентификации сообщений (MAC). Благодаря интеграции конфиденциального ключа с входными данными хеш-функции могут генерировать MAC-адреса, гарантирующие подлинность данных, например, в HMAC .
• Хранение паролей. Хэш-значение пароля не раскрывает никаких подробностей пароля, что подчеркивает важность безопасного хранения хешированных паролей на сервере.
• Подписи: подписываются хеши сообщений, а не все сообщение целиком.

Детерминированный

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

Детерминизм находится в контексте повторного использования функции. Например, в Python добавлена ​​функция, позволяющая хэш-функциям использовать рандомизированное начальное число, которое генерируется один раз при запуске процесса Python в дополнение к вводу, подлежащему хешированию. ^[9] Хэш Python ( SipHash ) по-прежнему является допустимой хеш-функцией при использовании в рамках одного запуска. Но если значения сохраняются (например, записываются на диск), их больше нельзя рассматривать как действительные значения хеш-функции, поскольку при следующем запуске случайное значение может отличаться.

Определенный диапазон

Часто желательно, чтобы выходные данные хеш-функции имели фиксированный размер (см. ниже). Если, например, выходные данные ограничены 32-битными целочисленными значениями, хеш-значения можно использовать для индексации в массиве. Такое хеширование обычно используется для ускорения поиска данных. ^[10] Получение выходных данных фиксированной длины из входных данных переменной длины может быть достигнуто путем разбиения входных данных на фрагменты определенного размера. Хэш-функции, используемые для поиска данных, используют некоторые арифметические выражения, которые итеративно обрабатывают фрагменты входных данных (например, символы в строке) для получения хэш-значения. ^[10]

Переменный диапазон

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

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

Переменный диапазон с минимальным перемещением (динамическая хэш-функция)

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

Желательна хеш-функция, которая будет перемещать минимальное количество записей при изменении размера таблицы. Что необходимо, так это хеш-функция H ( z , n )  – где z – хешируемый ключ, а n – количество разрешенных значений хеш-функции – такая, что H ( z , n  + 1) = H ( z , n ) с вероятностью близко к n /( n  + 1) .

Линейное хеширование и спиральное хеширование являются примерами динамических хеш-функций, которые выполняются за постоянное время, но ослабляют свойство однородности для достижения свойства минимального движения. Расширяемое хеширование использует динамическую хэш-функцию, которой для вычисления хеш-функции требуется пространство, пропорциональное n , и она становится функцией предыдущих вставленных ключей. Было изобретено несколько алгоритмов, которые сохраняют свойство однородности, но требуют времени, пропорционального n , для вычисления значения H ( z , n ) . ^{[ нужны разъяснения ]}

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

Нормализация данных

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

Хеширование целочисленных типов данных

Существует несколько распространенных алгоритмов хеширования целых чисел. Метод, дающий наилучшее распределение, зависит от данных. Одним из самых простых и распространенных на практике методов является метод деления по модулю.

Хэш-функция идентификации

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

Значение слова «достаточно маленький» зависит от размера типа, который используется в качестве хешированного значения. Например, в Java хеш-код представляет собой 32-битное целое число. Таким образом, 32-битные целые числа Integerи 32-битные объекты с плавающей запятой Floatмогут просто использовать значение напрямую; тогда как 64-битное целое число Longи 64-битное число с плавающей запятой Doubleне могут использовать этот метод.

Другие типы данных также могут использовать эту схему хеширования. Например, при сопоставлении строк символов между верхним и нижним регистром можно использовать двоичную кодировку каждого символа, интерпретируемого как целое число, для индексации таблицы, которая дает альтернативную форму этого символа («A» для «a», « 8" вместо "8" и т. д.). Если каждый символ хранится в 8 битах (как в расширенном ASCII ^{[Примечания 2]} или ISO Latin 1 ), в таблице будет только 2 ⁸ = 256 записей; в случае символов Юникода таблица будет иметь размер 17×2 ¹⁶ =1 114 112 записей.

Тот же метод можно использовать для сопоставления двухбуквенных кодов стран , таких как «нас» или «за», с названиями стран (26 ² = 676 записей в таблице), пятизначных почтовых индексов, таких как 13083, с названиями городов (100 000 записей) и т. д. Недопустимые значения данных (например, код страны «xx» или почтовый индекс 00000) можно оставить неопределенными в таблице или сопоставить с каким-либо подходящим «нулевым» значением.

Тривиальная хэш-функция

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

Складной

Сворачивающийся хэш-код создается путем разделения входных данных на n секций по m бит, где 2 ^m — размер таблицы, и использования побитовой операции с сохранением четности, такой как ADD или XOR, для объединения секций, за которой следует маска или сдвиги для обрежьте все лишние биты на верхнем или нижнем конце. Например, для таблицы размером 15 бит и значением ключа 0x0123456789ABCDEF имеется пять разделов, состоящих из 0x4DEF, 0x1357, 0x159E, 0x091A и 0x8. Сложив, мы получаем 0x7AA4, 15-битное значение.

Средние квадраты

Хэш-код средних квадратов создается путем возведения входных данных в квадрат и извлечения соответствующего количества средних цифр или битов. Например, если входные данные равны 123 456 789 и размер хеш-таблицы 10 000, возведение ключа в квадрат дает 15 241 578 750 190 521, поэтому хеш-код принимается как средние 4 цифры 17-значного числа (игнорируя старшую цифру) 8750. Средние квадраты Метод создает разумный хэш-код, если в ключе не так много начальных или конечных нулей. Это вариант мультипликативного хеширования, но он не так хорош, поскольку произвольный ключ не является хорошим множителем.

Хеширование деления

Стандартный метод заключается в использовании функции по модулю ключа путем выбора делителя, который представляет собой простое число, близкое к размеру таблицы, т. е . Размер таблицы обычно равен степени 2. Это дает распределение от . Это дает хорошие результаты для большого количества наборов ключей. Существенным недостатком хеширования деления является то, что деление микропрограммируется на большинстве современных архитектур, включая x86, и может быть в 10 раз медленнее, чем умножение. Второй недостаток заключается в том, что он не разбивает кластерные ключи. Например, ключи 123000, 456000, 789000 и т. д. по модулю 1000 соответствуют одному и тому же адресу. Этот метод хорошо работает на практике, поскольку многие наборы ключей уже достаточно случайны, и вероятность того, что набор ключей будет циклическим из-за большого простого числа, мала. ${\displaystyle M}$ ${\displaystyle h(K)=K{\bmod {M}}}$ ${\displaystyle \{0,M-1\}}$

Алгебраическое кодирование

Алгебраическое кодирование — это вариант метода хеширования с делением, который использует деление на полином по модулю 2 вместо целого числа для преобразования n бит в m бит. ^{[3] : 512–513} В этом подходе мы постулируем полином степени . Ключ можно рассматривать как полином . Остаток с использованием полиномиальной арифметики по модулю 2 равен . Затем . Если он сконструирован так, чтобы иметь или меньше ненулевых коэффициентов, то ключи, которые имеют меньше битов, гарантированно не будут конфликтовать. ${\displaystyle M=2^{m}}$ ${\displaystyle m}$ ${\displaystyle \mathrm {Z} (x)=x^{m}+\zeta _{m-1}x^{m-1}+...+\zeta _{0}}$ ${\displaystyle K=(k_{n-1}...k_{1}k_{0})_{2}}$ ${\displaystyle K(x)=k_{n-1}x^{n-1}+...+k_{1}x+k_{0}}$ ${\displaystyle K(x){\bmod {Z}}(x)=h_{m-1}x^{m-1}+...+h_{1}x+h_{0}}$ ${\displaystyle h(K)=(h_{m-1}...h_{1}h_{0})_{2}}$ ${\displaystyle Z(x)}$ ${\displaystyle t}$ ${\displaystyle t}$

${\displaystyle Z}$функция , и , делитель , строится из поля. Кнут приводит пример: для n=15, m=10 и t=7, . Вывод следующий: ${\displaystyle k}$ ${\displaystyle t}$ ${\displaystyle n}$ ${\displaystyle 2^{k}-1}$ ${\displaystyle GF(2^{k})}$ ${\displaystyle Z(x)=x^{10}+x^{8}+x^{5}+x^{4}+x^{2}+x+1}$

Пусть – наименьший набор целых чисел такой, что и . ^{[Примечания 3]} ${\displaystyle S}$ ${\displaystyle \{1,2,...,t\}\subseteq S}$ ${\displaystyle (2j{\bmod {n}})\in S\quad \forall j\in S}$

Определите, где и где в этом поле вычисляются коэффициенты . Тогда степень . Поскольку является корнем всякий раз , когда является корнем, из этого следует, что коэффициенты удовлетворяют , поэтому все они равны 0 или 1. Если является любым ненулевым многочленом по модулю 2 с не более чем ненулевыми коэффициентами, то он не кратен модулю 2. ^{[Примечания 4 ]} Из этого следует, что соответствующая хэш-функция будет отображать ключи, имеющие менее общих битов, в уникальные индексы. ^{[3] : 542–543.} ${\displaystyle P(x)=\prod _{j\in S}(x-\alpha ^{j})}$ ${\displaystyle \alpha \in ^{n}GF(2^{k})}$ ${\displaystyle P(x)}$ ${\displaystyle P(x)=|S|}$ ${\displaystyle \alpha ^{2j}}$ ${\displaystyle P(x)}$ ${\displaystyle \alpha ^{j}}$ ${\displaystyle p^{i}}$ ${\displaystyle P(x)}$ ${\displaystyle p_{i}^{2}=p_{i}}$ ${\displaystyle R(x)=r_{(n-1)}x^{n-1}+...+r_{1}x+r_{0}}$ ${\displaystyle t}$ ${\displaystyle R(x)}$ ${\displaystyle P(x)}$ ${\displaystyle t}$

Обычный результат таков: либо он станет большим, либо станет большим, либо и то, и другое, чтобы схема стала вычислительно осуществимой. Поэтому он больше подходит для аппаратной реализации или реализации микрокода. ^{[3] : 542–543.} ${\displaystyle n}$ ${\displaystyle t}$

Уникальное хеширование перестановок

См. также уникальное хеширование перестановок, которое обеспечивает гарантированное лучшее время вставки в худшем случае. ^[11]

Мультипликативное хеширование

Стандартное мультипликативное хеширование использует формулу , которая создает хеш-значение в формате . Значение представляет собой правильно выбранное значение, которое должно быть относительно простым ; он должен быть большим ^{[ необходимы пояснения ]} и его двоичное представление должно представлять собой случайную смесь ^{[ необходимо пояснение ]} единиц и нулей. Важный практический частный случай возникает, когда и являются степенями 2, а размер машинного слова . В этом случае эта формула принимает вид . Это особенное явление, поскольку в языках программирования низкого уровня арифметические операции по модулю выполняются по умолчанию, а целочисленное деление на степень 2 — это просто сдвиг вправо, поэтому, например, в C эта функция принимает вид ${\displaystyle h_{a}(K)=\lfloor (aK{\bmod {W}})/(W/M)\rfloor }$ ${\displaystyle \{0,\ldots ,M-1\}}$ ${\displaystyle a}$ ${\displaystyle W}$ ${\displaystyle W=2^{w}}$ ${\displaystyle M=2^{m}}$ ${\displaystyle w}$ ${\displaystyle h_{a}(K)=\lfloor (aK{\bmod {2}}^{w})/2^{w-m}\rfloor }$ ${\displaystyle 2^{w}}$

беззнаковый хэш (беззнаковый K){ возврат (a*K) >> (wm);}

и для фиксированного , и это преобразуется в одно целочисленное умножение и сдвиг вправо, что делает его одной из самых быстрых хеш-функций для вычисления. ${\displaystyle m}$ ${\displaystyle w}$

Мультипликативное хеширование подвержено «распространенной ошибке», которая приводит к плохой диффузии — входные биты с более высоким значением не влияют на выходные биты с меньшим значением. ^[12] Преобразование на входе, которое сдвигает диапазон оставшихся старших битов вниз и выполняет операцию XOR или добавляет их к ключу до того, как это будет исправлено на этапе умножения. Итоговая функция выглядит так: ^[7]

беззнаковый хэш (беззнаковый K){ К ^= К >> (шм); возврат (a*K) >> (wm);}

Хеширование Фибоначчи

Хеширование Фибоначчи — это форма мультипликативного хеширования, в которой множителем является , где — длина машинного слова, а (фи) — золотое сечение (приблизительно 5/3). Свойством этого множителя является то, что он равномерно распределяет по табличному пространству блоки последовательных ключей относительно любого блока битов в ключе. Последовательные ключи в старших или младших битах ключа (или какого-либо другого поля) встречаются относительно часто. Множители для различной длины слова : ${\displaystyle 2^{w}/\phi }$ ${\displaystyle w}$ ${\displaystyle \phi }$ ${\displaystyle w}$

• 16: а =9Э37 ₁₆"="40 503 ₁₀
• 32: а =9Э37 79Б9 ₁₆"="2 654 435 769 ₁₀
• 48: а =9Э37 79Б9 7Ф4Б ₁₆"="173 961 102 589 771 ₁₀ ^{[Примечание 5]}
• 64: а =9E37 79B9 7F4A 7C15 ₁₆"="11 400 714 819 323 198 485 ₁₀

Множитель должен быть нечетным, поэтому младший бит вывода обратим по модулю . Для достижения этой цели последние два значения, приведенные выше, округляются (в большую и меньшую сторону соответственно) более чем на 1/2 младшего бита. ${\displaystyle 2^{w}}$

Зобристское хеширование

Табулационное хеширование, более широко известное как хеширование Зобриста в честь Альберта Зобриста , американского ученого-компьютерщика, представляет собой метод построения универсальных семейств хэш-функций путем объединения поиска в таблице с операциями XOR. Этот алгоритм оказался очень быстрым и качественным для целей хеширования (особенно хеширования целочисленных ключей). ^[13]

Зобристское хеширование изначально было введено как средство компактного представления шахматных позиций в компьютерных игровых программах. Для обозначения каждого типа фигур (по шесть для черных и белых) на каждом поле доски было присвоено уникальное случайное число. Таким образом, в начале программы инициализируется таблица размером 64×12 таких чисел. Случайные числа могли быть любой длины, но 64 бита были естественными из-за 64 клеток на доске. Позиция транскрибировалась путем циклического перебора фигур в позиции, индексирования соответствующих случайных чисел (пустые места не включались в расчет) и их совместного выполнения исключающего ИЛИ (начальное значение могло быть 0, идентификационное значение для исключающего ИЛИ или случайное значение). семя). Полученное значение уменьшалось по модулю, свертыванию или какой-либо другой операции для создания индекса хеш-таблицы. Исходный хэш Зобриста сохранялся в таблице как представление позиции.

Позже метод был расширен до хеширования целых чисел путем представления каждого байта в каждой из 4 возможных позиций слова уникальным 32-битным случайным числом. Таким образом, строится таблица из 2 ^{8 ×4 таких случайных чисел.} 32-битное хешированное целое число транскрибируется путем последовательного индексирования таблицы со значением каждого байта простого текстового целого числа и выполнения операции XOR загруженных значений вместе (опять же, начальным значением может быть идентификационное значение или случайное начальное число). Естественным расширением 64-битных целых чисел является использование таблицы из 2 ⁸ × 8 64-битных случайных чисел.

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

Индивидуальная хэш-функция

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

Хеширование данных переменной длины

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

Середина и концы

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

Складывание персонажей

Парадигматическим примером свертывания по символам является сложение целочисленных значений всех символов в строке. Лучшая идея — умножить общую сумму хеша на константу, обычно на значительное простое число, перед добавлением следующего символа, игнорируя переполнение. Использование исключающего «или» вместо «добавить» также является разумной альтернативой. Последней операцией будет операция по модулю, маске или другой функции, позволяющая уменьшить значение слова до индекса размером с таблицу. Слабость этой процедуры заключается в том, что информация может группироваться в старших или младших битах байтов, и такая кластеризация останется в хешированном результате и вызовет больше коллизий, чем правильный рандомизирующий хеш. Например, байтовые коды ASCII имеют старший бит, равный 0, а печатаемые строки не используют первые 32 байтовых кода, поэтому информация (95-байтовые коды) группируется в оставшихся битах неочевидным образом.

Классический подход, получивший название хэша PJW, основан на работе Питера. Дж. Вайнбергер из ATT Bell Labs в 1970-х годах изначально был разработан для хеширования идентификаторов в таблицы символов компилятора, как указано в «Книге Дракона» . ^[14] Эта хеш-функция смещает байты на 4 бита перед их сложением. При переносе количества старшие 4 бита сдвигаются и, если они не равны нулю, выполняются операция XOR обратно в младший байт совокупного количества. Результатом является хеш-код размера слова, к которому можно применить операцию уменьшения по модулю или другую операцию для получения окончательного хэш-индекса.

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

Сворачивание длины слова

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

Хеширование преобразований Radix

Аналогично тому, как строка символов ASCII или EBCDIC, представляющая десятичное число, преобразуется в числовую величину для вычислений, строка переменной длины может быть преобразована как ( x ₀ a ^{k −1} + x ₁ a ^{k −2} +...+ Икс _{k -2} а + Икс _{k -1} ) . Это просто многочлен по основанию a  > 1 , который принимает компоненты ( x ₀ , x ₁ ,..., x _{k −1} ) в качестве символов входной строки длины k . Его можно использовать непосредственно в качестве хэш-кода или применить к нему хеш-функцию для сопоставления потенциально большого значения с размером хеш-таблицы. Значение a обычно представляет собой простое число, по крайней мере, достаточно большое, чтобы вместить количество различных символов в наборе символов потенциальных ключей. Хеширование строк с преобразованием системы оснований сводит к минимуму количество коллизий. ^[15] Доступные размеры данных могут ограничивать максимальную длину строки, которую можно хешировать с помощью этого метода. Например, 128-битное двойное длинное слово будет хешировать только буквенную строку из 26 символов (без учета регистра) с основанием 29; печатаемая строка ASCII ограничена 9 символами с использованием системы счисления 97 и длинного 64-битного слова. Однако буквенные ключи обычно имеют небольшую длину, поскольку ключи должны храниться в хеш-таблице. Строки числовых символов обычно не представляют проблемы; 64 бита могут считать до 10 ¹⁹ или 19 десятичных цифр с основанием 10.

Роллинг хеша

В некоторых приложениях, таких как поиск подстроки , можно вычислить хэш-функцию h для каждой подстроки из k символов заданной строки из n символов, перемещая окно шириной k символов вдоль строки; где k — фиксированное целое число, а n больше k . Простое решение — извлечь такую ​​подстроку в каждой позиции символа текста и вычислить h отдельно — требует ряда операций, пропорциональных k · n . Однако при правильном выборе h можно использовать технику прокрутки хеша для вычисления всех этих хешей с затратами, пропорциональными mk  +  n , где m — количество вхождений подстроки. ^{[ нужна цитата ] [ каков выбор h? ]}

Самый знакомый алгоритм этого типа — Рабин-Карп с лучшим и средним показателями производительности O ( n + mk ) и худшим случаем O ( n · k ) (справедливости ради, худший случай здесь серьезно патологичен: и текстовая строка, и подстроки состоят из повторяющихся одиночных символов, например t ="AAAAAAAAAAA" и s ="AAA"). Хэш-функция, используемая для алгоритма, обычно представляет собой отпечаток пальца Рабина , предназначенный для предотвращения коллизий в 8-битных символьных строках, но также используются и другие подходящие хэш-функции.

Нечеткий хеш

Нечеткое хеширование , также известное как хеширование по сходству, ^[16] — это метод обнаружения данных, которые похожи, но не совсем совпадают с другими данными. В этом отличие от криптографических хэш-функций , которые разработаны так, чтобы иметь существенно разные хеш-функции даже при незначительных различиях. Нечеткое хеширование использовалось для идентификации вредоносного ПО ^{[17] [18]} и имеет потенциал для других приложений, таких как предотвращение потери данных и обнаружение нескольких версий кода. ^{[19] [20]}

Перцептивный хеш

Перцептивное хеширование — это использование алгоритма снятия отпечатков пальцев , который создает фрагмент, хэш или отпечаток пальца различных форм мультимедиа . ^{[21] [22]} Перцептивный хэш — это тип хеша, чувствительного к местонахождению , который аналогичен, если характеристики мультимедиа схожи. В этом отличие от криптографического хеширования , которое основано на лавинном эффекте небольшого изменения входного значения, вызывающего резкое изменение выходного значения. Перцептивные хеш-функции широко используются при обнаружении случаев нарушения авторских прав в Интернете , а также в цифровой криминалистике из-за возможности корреляции между хэшами, позволяющей находить похожие данные (например, с другим водяным знаком ).

Анализ

Наихудший результат для хэш-функции можно оценить двумя способами: теоретическим и практическим. Теоретически худшим случаем является вероятность того, что все ключи будут привязаны к одному слоту. В худшем практическом случае ожидается самая длинная пробная последовательность (хэш-функция + метод разрешения коллизий). В этом анализе рассматривается равномерное хеширование, то есть любой ключ будет сопоставлен с любым конкретным слотом с вероятностью 1/ m , что характерно для универсальных хеш-функций.

В то время как Кнут беспокоится о состязательной атаке на системы реального времени, ^[23] Гонне показал, что вероятность такого случая «смехотворно мала». Его представление заключалось в том, что вероятность сопоставления k из n ключей с одним слотом равна где α — коэффициент загрузки, n / m . ^[24] ${\displaystyle {\frac {e^{-\alpha }\alpha ^{k}}{k!}}}$

История

Термин « хэш» предлагает естественную аналогию с его нетехническим значением (разрезать или испортить что-либо), учитывая, как хэш-функции шифруют входные данные для получения выходных данных. ^{[25] : 514} В своем исследовании точного происхождения этого термина Дональд Кнут отмечает, что, хотя Ханс Питер Лун из IBM, по-видимому, был первым, кто использовал концепцию хэш-функции в записке, датированной январем 1953 года, термин Сам по себе появился в опубликованной литературе только в конце 1960-х годов, в « Принципах цифровой компьютерной системы» Герберта Хеллермана , хотя к тому времени это уже был широко распространенный жаргон. ^{[25] : 547–548.}

Смотрите также

• Список хэш-функций
• Поиск ближайшего соседа
• Криптографическая хэш-функция
• Распределенная хеш-таблица
• Идентикон
• Последовательность с низким расхождением
• Таблица транспонирования

Примечания

1. Это полезно в случаях, когда ключи разработаны злоумышленником, например, для атаки DOS.
2. Обычный ASCII — это 7-битная кодировка символов, хотя она часто хранится в 8-битных байтах, при этом старший бит всегда чист (ноль). Следовательно, для простого ASCII байты имеют только 2 ⁷ = 128 допустимых значений, а таблица перевода символов содержит только такое количество записей.
3. Например, для n=15, k=4, t=6, [Кнут] ${\displaystyle S=\{1,2,3,4,5,6,8,10,12,9\}}$
4. Кнут удобно оставляет доказательство этого читателю.
5. Большие системы Unisys.

Рекомендации

1. Аггарвал, Кирти; Верма, Харш К. (19 марта 2015 г.). Hash_RC6 — Алгоритм хеширования переменной длины с использованием RC6. Международная конференция по достижениям в области компьютерной техники и приложений (ICACEA), 2015 г. дои : 10.1109/ICACEA.2015.7164747 . Проверено 24 января 2023 г.
2. «Глоссарий NIST — хэш-дайджест» . Проверено 1 января 2024 г.
3. Кнут, Дональд Э. (1973). Искусство компьютерного программирования, Том. 3. Сортировка и поиск . Ридинг, Массачусетс, США: Аддисон-Уэсли . Бибкод : 1973acp..книга.....К. ISBN 978-0-201-03803-3.
4. Стоукс, Джон (8 июля 2002 г.). «Понимание кэширования и производительности ЦП». Арс Техника . Проверено 6 февраля 2022 г.
5. Менезес, Альфред Дж.; ван Оршот, Пол К.; Ванстон, Скотт А. (1996). Справочник по прикладной криптографии . ЦРК Пресс. ISBN 978-0849385230.
6. Кастро, Хулио Сезар Эрнандес; и другие. (3 февраля 2005 г.). «Строгий тест на случайность критерия лавинности». Математика и компьютеры в моделировании . Эльзевир . 68 (1): 1–7. дои : 10.1016/j.matcom.2004.09.001. S2CID  18086276.
7. Шарупке, Мальте (16 июня 2018 г.). «Хеширование Фибоначчи: оптимизация, о которой мир забыл». Наверное, Танец .
8. Вагнер, Урс; Лугрин, Томас (2023), Малдер, Валентин; Мермуд, Ален; Кредиторы, Винсент; Телленбах, Бернхард (ред.), «Хэш-функции», Тенденции в области защиты данных и технологий шифрования , Cham: Springer Nature Switzerland, стр. 21–24, doi : 10.1007/978-3-031-33386-6_5 , ISBN 978-3-031-33386-6
9. «3. Модель данных — документация Python 3.6.1» . docs.python.org . Проверено 24 марта 2017 г.
10. Седжвик, Роберт (2002). «14. Перемешивание». Алгоритмы на Java (3-е изд.). Эддисон Уэсли. ISBN 978-0201361209.
11. Долев, Шломи; Лахиани, Лимор; Хавив, Иннон (2013). «Уникальное хеширование перестановок». Теоретическая информатика . 475 : 59–65. дои : 10.1016/j.tcs.2012.12.047 .
12. «CS 3110 Лекция 21: Хэш-функции» . Раздел «Мультипликативное хеширование».
13. Зобрист, Альберт Л. (апрель 1970 г.), Новый метод хеширования с применением для игр (PDF) , Tech. Член палаты представителей 88, Мэдисон, Висконсин: факультет компьютерных наук, Университет Висконсина..
14. Ахо, А .; Сетхи, Р. ; Уллман, JD (1986). Составители: принципы, методы и инструменты . Ридинг, Массачусетс: Аддисон-Уэсли . п. 435. ИСБН 0-201-10088-6.
15. Рамакришна, М.В.; Зобель, Джастин (1997). «Производительность на практике функций хеширования строк». Системы баз данных для продвинутых приложений '97 . DASFAA 1997. стр. 215–224. CiteSeerX 10.1.1.18.7520 . дои : 10.1142/9789812819536_0023. ISBN  981-02-3107-5. S2CID  8250194 . Проверено 6 декабря 2021 г.
16. Брайтингер, Франк (май 2014 г.). «Специальная публикация NIST 800-168» (PDF) . Публикации НИСТ . дои : 10.6028/NIST.SP.800-168 . Проверено 11 января 2023 г.
17. Пагани, Фабио; Делл'Амико, Маттео; Бальзаротти, Давиде (13 марта 2018 г.). «За пределами точности и отзыва» (PDF) . Материалы восьмой конференции ACM по безопасности и конфиденциальности данных и приложений . Нью-Йорк, штат Нью-Йорк, США: ACM. стр. 354–365. дои : 10.1145/3176258.3176306. ISBN 9781450356329. Проверено 12 декабря 2022 г.
18. Сарантинос, Николаос; Бензаид, Чафика; Арабиат, Омар (2016). «Судебно-медицинский анализ вредоносных программ: ценность алгоритмов нечеткого хеширования в выявлении сходств». IEEE Trustcom/BigDataSE/ISPA, 2016 г. (PDF) . стр. 1782–1787. doi : 10.1109/TrustCom.2016.0274. ISBN 978-1-5090-3205-1. S2CID  32568938. 10.1109/TrustCom.2016.0274.
19. Корнблюм, Джесси (2006). «Идентификация почти идентичных файлов с использованием контекстно-зависимого кусочного хеширования». Цифровое расследование . 3, Приложение (сентябрь 2006 г.): 91–97. дои : 10.1016/j.diin.2006.06.015 . Проверено 30 июня 2022 г.
20. Оливер, Джонатан; Ченг, Чун; Чен, Янгуй (2013). «TLSH — хэш, чувствительный к местоположению» (PDF) . 2013 Четвертый семинар по киберпреступности и надежным вычислениям . IEEE. стр. 7–13. дои : 10.1109/ctc.2013.9. ISBN 978-1-4799-3076-0. Проверено 12 декабря 2022 г.
21. Булдас, Ахто; Крунмаа, Андрес; Лааноха, Ристо (2013). «Инфраструктура бесключевых подписей: как построить глобальные распределенные хеш-деревья». В Риисе, Нильсон Х.; Голлманн, Д. (ред.). Безопасные ИТ-системы. НордСек 2013 . Конспекты лекций по информатике. Том. 8208. Берлин, Гейдельберг: Springer. дои : 10.1007/978-3-642-41488-6_21. ISBN 978-3-642-41487-9. ISSN  0302-9743. Инфраструктура бесключевых подписей (KSI) — это глобально распределенная система для предоставления услуг по отмене времени и цифровой подписи, поддерживаемой сервером. Создаются глобальные посекундные хэш-деревья и публикуются их корневые хэш-значения. Мы обсуждаем некоторые проблемы качества обслуживания, которые возникают при практической реализации услуги, и представляем решения, позволяющие избежать единых точек сбоя и гарантировать предоставление услуги с разумной и стабильной задержкой. Guardtime AS управляет инфраструктурой KSI уже 5 лет. Мы суммируем, как строится инфраструктура KSI, и уроки, извлеченные за период эксплуатации сервиса.
22. Клингер, Эван; Старквезер, Дэвид. «pHash.org: Дом pHash, библиотеки перцептивного хеширования с открытым исходным кодом». pHash.org . Проверено 5 июля 2018 г. pHash — это программная библиотека с открытым исходным кодом, выпущенная под лицензией GPLv3, которая реализует несколько алгоритмов перцептивного хеширования и предоставляет C-подобный API для использования этих функций в ваших собственных программах. Сам pHash написан на C++.
23. Кнут, Дональд Э. (1975). Искусство компьютерного программирования, Том. 3. Сортировка и поиск . Ридинг, Массачусетс: Аддисон-Уэсли . п. 540.
24. Гонне, Г. (1978). Ожидаемая длина самой длинной пробной последовательности при поиске хэш-кода (технический отчет). Онтарио, Канада: Университет Ватерлоо . CS-RR-78-46.
25. Кнут, Дональд Э. (2000). Искусство компьютерного программирования, Том. 3, Сортировка и поиск (2-е изд., 6-е изд., печать, новое обновленное и переработанное изд.). Бостон [ua]: Аддисон-Уэсли. ISBN 978-0-201-89685-5.

Внешние ссылки

• Вычислить хеш заданного значения Тимо Денк
• Хеш-функция Гоулберна ( PDF ), автор: Маюр Патель
• Построение хеш-функции для поиска текстовых и геометрических данных ( PDF ) Последние тенденции в компьютерах, Том 2, стр. 483–489, Конференция CSCC, Корфу, 2010 г.