Хэш-функция

«хеш-ссылка» перенаправляется сюда. Информацию о виртуальной машине Haxe см. в HashLink .

«Хеш-код» перенаправляется сюда. Информацию о соревновании по программированию см. в разделе Hash Code (соревнование по программированию) .

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

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

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

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

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

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

Обзор

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

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

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

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

Хэш-таблицы

Основная статья: Хэш-таблица

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Основная статья: Универсальное хеширование

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

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

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

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

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

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

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

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

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

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

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

Во многих приложениях диапазон хэш-значений может быть разным для каждого запуска программы или может меняться в течение одного и того же запуска (например, когда необходимо расширить хеш-таблицу). В таких ситуациях нужна хеш-функция, которая принимает два параметра — входные данные 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 или ISO Latin 1 ), в таблице всего 2 ⁸ = 256 записей; в случае символов Юникода таблица будет иметь размер 17×2. ¹⁶ = 1 114 112 записей.

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

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

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

Складной

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

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

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

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

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

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

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

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

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

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

Обычный результат таков: либо $n$ станет большим, или $t$ станет большим, или и то, и другое, чтобы схема была вычислительно осуществимой. Поэтому он больше подходит для аппаратной реализации или реализации микрокода.

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

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

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

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

unsigned hash(unsigned K)
{ 
   return (a*K) >> (w-m);
}

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

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

unsigned hash(unsigned K)
{
   K ^= K >> (w-m); 
   return (a*K) >> (w-m);
}

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

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

• 16: а = 9Е37 ₁₆ = 40 503 ₁₀
• 32: а = 9Е37 79В9 ₁₆ = 2 654 435 769 ₁₀
• 48: а = 9Е37 79В9 7F4B ₁₆ = 173 961 102 589 771 ₁₀
• 64: а = 9E37 79B9 7F4A 7C15 ₁₆ = 11 400 714 819 323 198 485 ₁₀

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

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

Основные статьи: Табулационное хеширование и хеширование Зобриста

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

См. также: Универсальное хеширование § Строки хеширования.

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

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

Аналогично тому, как строка символов ASCII или EBCDIC, представляющая десятичное число, преобразуется в числовую величину для вычислений, строка переменной длины может быть преобразована как ( x ₀ a ^{к -1} + х ₁ а ^{к -2} +...+ Икс _{k -2} а + Икс _{k -1} ) . Это просто многочлен по основанию a > 1 , который принимает компоненты ( x ₀ , x ₁ ,..., x _{k −1} ) в качестве символов входной строки длины k . Его можно использовать непосредственно в качестве хэш-кода или применить к нему хеш-функцию для сопоставления потенциально большого значения с размером хеш-таблицы. Значение a обычно представляет собой простое число, по крайней мере, достаточно большое, чтобы вместить количество различных символов в наборе символов потенциальных ключей. Хеширование строк с преобразованием системы оснований сводит к минимуму количество коллизий. Доступные размеры данных могут ограничивать максимальную длину строки, которую можно хешировать с помощью этого метода. Например, 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 — количество вхождений подстроки.

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

Нечеткий хэш

Этот раздел представляет собой отрывок из статьи «Нечеткое хеширование» . [ редактировать ]

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

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

Этот раздел представляет собой отрывок из книги «Перцептивное хеширование» . [ редактировать ]

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

Анализ

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

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

История

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

См. также

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

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

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