Хэш -функция — это любая функция , которую можно использовать для сопоставления данных произвольного размера со значениями фиксированного размера, хотя существуют некоторые хэш-функции, которые поддерживают вывод переменной длины. [1] Значения, возвращаемые хэш-функцией, называются хеш-значениями , хэш-кодами , хэш-дайджестами , дайджестами или просто хэшами . [2] Значения обычно используются для индексации таблицы фиксированного размера, называемой хеш-таблицей . Использование хеш-функции для индексации хеш-таблицы называется хешированием или адресацией рассеянного хранилища .
Хэш-функции и связанные с ними хеш-таблицы используются в приложениях хранения и извлечения данных для доступа к данным за небольшое и почти постоянное время каждого извлечения. Им требуется объем места для хранения, лишь незначительно превышающий общий объем пространства, необходимого для самих данных или записей. Хеширование - это форма доступа к данным, эффективная в вычислительном отношении и пространстве хранения, которая позволяет избежать непостоянного времени доступа к упорядоченным и неупорядоченным спискам и структурированным деревьям, а также часто экспоненциальных требований к хранению при прямом доступе к пространствам состояний ключей большой или переменной длины.
Использование хэш-функций основано на статистических свойствах взаимодействия ключей и функций: поведение в худшем случае невыносимо плохо, но редко, а поведение в среднем случае может быть почти оптимальным (минимальное столкновение ). [3] : 527
Хэш-функции связаны с контрольными суммами (и часто путаются с ними) , контрольными цифрами , отпечатками пальцев , сжатием с потерями , функциями рандомизации , кодами с исправлением ошибок и шифрами . Хотя эти концепции в некоторой степени пересекаются, каждая из них имеет свои собственные применения и требования, а также разрабатывается и оптимизируется по-разному. Хэш-функция отличается от этих понятий главным образом с точки зрения целостности данных .
Хэш-функция принимает в качестве входных данных ключ, который связан с данными или записью и используется для их идентификации в приложении хранения и поиска данных. Ключи могут иметь фиксированную длину, например целое число, или переменную длину, например имя. В некоторых случаях ключом является сама база данных. Выходными данными является хеш-код, используемый для индексации хеш-таблицы, содержащей данные или записи, или указатели на них.
Можно считать, что хеш-функция выполняет три функции:
Хорошая хеш-функция удовлетворяет двум основным свойствам: 1) она должна вычисляться очень быстро; 2) следует минимизировать дублирование выходных значений (коллизии). Хэш-функции полагаются на создание благоприятных распределений вероятностей для своей эффективности, сокращая время доступа почти до постоянного значения. Высокие коэффициенты загрузки таблицы, патологические наборы ключей и плохо спроектированные хеш-функции могут привести к тому, что время доступа будет приближаться к линейному по количеству элементов в таблице. Хэш-функции могут быть разработаны так, чтобы обеспечить наилучшую производительность в наихудшем случае, [Примечания 1] хорошую производительность при высоких коэффициентах загрузки таблицы, а в особых случаях - идеальное (без коллизий) отображение ключей в хеш-коды. Реализация основана на битовых операциях с сохранением четности (XOR и ADD), умножении или делении. Необходимым дополнением к хеш-функции является метод разрешения коллизий, который использует вспомогательную структуру данных, такую как связанные списки , или систематическое исследование таблицы для поиска пустого слота.
Хэш-функции используются вместе с хеш-таблицами для хранения и извлечения элементов данных или записей данных. Хэш-функция преобразует ключ, связанный с каждым элементом данных или записью, в хеш-код, который используется для индексации хеш-таблицы. Когда элемент должен быть добавлен в таблицу, хеш-код может индексировать пустой слот (также называемый ведром), и в этом случае элемент добавляется в таблицу там. Если хеш-код индексирует полный слот, требуется какое-то разрешение коллизий: новый элемент может быть опущен (не добавлен в таблицу) или заменить старый элемент, или он может быть добавлен в таблицу в каком-либо другом месте с помощью указанная процедура. Эта процедура зависит от структуры хеш-таблицы: при цепном хешировании каждый слот является главой связанного списка или цепочки, а элементы, которые конфликтуют в слоте, добавляются в цепочку. Цепочки можно хранить в случайном порядке и искать линейно, в последовательном порядке или в виде списка с самоупорядочением по частоте для ускорения доступа. При хешировании открытого адреса таблица проверяется, начиная с занятого слота, определенным образом, обычно путем линейного зондирования , квадратичного зондирования или двойного хеширования до тех пор, пока не будет обнаружен открытый слот или не будет проверена вся таблица (переполнение). Поиск элемента выполняется по одной и той же процедуре до тех пор, пока элемент не будет найден, не будет найден открытый слот или не будет найдена вся таблица (элемент не находится в таблице).
Хэш-функции также используются для создания кешей для больших наборов данных, хранящихся на медленных носителях. Кэш обычно проще, чем хешированная таблица поиска, поскольку любую коллизию можно разрешить путем отбрасывания или обратной записи более старого из двух конфликтующих элементов. [4]
Хэш-функции являются важным компонентом фильтра Блума , компактной вероятностной структуры данных , которая используется для проверки того, является ли элемент членом множества .
Особый случай хеширования известен как геометрическое хеширование или метод сетки . В этих приложениях набор всех входных данных представляет собой своего рода метрическое пространство , а хеш-функцию можно интерпретировать как разбиение этого пространства на сетку ячеек . Таблица часто представляет собой массив с двумя или более индексами (называемый файлом сетки , индексом сетки , сеткой сегмента и аналогичными именами), а хэш-функция возвращает кортеж индекса . Этот принцип широко используется в компьютерной графике , вычислительной геометрии и многих других дисциплинах для решения многих задач близости на плоскости или в трехмерном пространстве , таких как поиск ближайших пар в наборе точек, похожих фигур в списке фигур, похожие изображения в базе данных изображений и т. д.
Хэш-таблицы также используются для реализации ассоциативных массивов и динамических наборов . [5]
Хорошая хеш-функция должна отображать ожидаемые входные данные как можно более равномерно по всему выходному диапазону. То есть каждое значение хеш-функции в выходном диапазоне должно генерироваться примерно с одинаковой вероятностью . Причина этого последнего требования заключается в том, что стоимость методов, основанных на хешировании, резко возрастает по мере увеличения количества коллизий — пар входных данных, которые сопоставлены с одним и тем же значением хеш-функции. Если некоторые значения хеш-функции встречаются с большей вероятностью, чем другие, большей части операций поиска придется искать в большем наборе конфликтующих записей таблицы.
Этот критерий требует, чтобы значение было распределено равномерно , а не случайно . Хорошая функция рандомизации (за исключением проблем с эффективностью вычислений) обычно является хорошим выбором в качестве хеш-функции, но обратное не обязательно должно быть верным.
Хэш-таблицы часто содержат лишь небольшое подмножество допустимых входных данных. Например, список членов клуба может содержать только около ста имен членов из очень большого набора всех возможных имен. В этих случаях критерий единообразия должен соблюдаться почти для всех типичных подмножеств записей, которые можно найти в таблице, а не только для глобального набора всех возможных записей.
Другими словами, если типичный набор из m записей хешируется в n слотов таблицы, вероятность того, что ведро получит гораздо больше, чем m / n записей, должна быть исчезающе малой. В частности, если m меньше n , очень немногие сегменты должны иметь более одной или двух записей. Небольшое количество столкновений практически неизбежно, даже если n намного больше m — см. задачу о дне рождения .
В особых случаях, когда ключи известны заранее и набор ключей статичен, можно найти хеш-функцию, которая обеспечивает абсолютную (или бесконфликтную) однородность. Такая хеш-функция называется идеальной . Алгоритмического способа создания такой функции не существует — ее поиск является факториальной функцией количества сопоставляемых ключей и количества слотов таблицы, к которым они подключены. Найти идеальную хеш-функцию для более чем очень небольшого набора ключей обычно вычислительно невозможно; результирующая функция, вероятно, будет более сложной в вычислительном отношении, чем стандартная хэш-функция, и обеспечит лишь незначительное преимущество перед функцией с хорошими статистическими свойствами, которая дает минимальное количество коллизий. См. универсальную хэш-функцию .
При тестировании хеш-функции равномерность распределения хеш-значений можно оценить с помощью теста хи-квадрат . Этот тест представляет собой меру согласия: это фактическое распределение элементов в корзинах по сравнению с ожидаемым (или равномерным) распределением элементов. Формула:
где: количество ключей, количество сегментов, количество элементов в сегменте
Отношение в пределах одного доверительного интервала (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]
Хэш-процедура должна быть детерминированной — это означает, что для данного входного значения она всегда должна генерировать одно и то же значение хеш-функции. Другими словами, это должна быть функция хешируемых данных в математическом смысле этого термина. Это требование исключает хэш-функции, которые зависят от внешних переменных параметров, таких как генераторы псевдослучайных чисел или время суток. Он также исключает функции, которые зависят от адреса памяти хешируемого объекта в случаях, когда адрес может измениться во время выполнения (как это может случиться в системах, использующих определенные методы сборки мусора ) , хотя иногда возможно перехеширование элемента.
Детерминизм находится в контексте повторного использования функции. Например, в Python добавлена функция, позволяющая хэш-функциям использовать рандомизированное начальное число, которое генерируется один раз при запуске процесса Python в дополнение к вводу, подлежащему хешированию. [9] Хэш Python ( SipHash ) по-прежнему является допустимой хеш-функцией при использовании в рамках одного запуска. Но если значения сохраняются (например, записываются на диск), их больше нельзя рассматривать как действительные значения хеш-функции, поскольку при следующем запуске случайное значение может отличаться.
Часто желательно, чтобы выходные данные хеш-функции имели фиксированный размер (см. ниже). Если, например, выходные данные ограничены 32-битными целочисленными значениями, хеш-значения можно использовать для индексации в массиве. Такое хеширование обычно используется для ускорения поиска данных. [10] Получение выходных данных фиксированной длины из входных данных переменной длины может быть достигнуто путем разбиения входных данных на фрагменты определенного размера. Хэш-функции, используемые для поиска данных, используют некоторые арифметические выражения, которые итеративно обрабатывают фрагменты входных данных (например, символы в строке) для получения хэш-значения. [10]
Во многих приложениях диапазон хэш-значений может быть разным для каждого запуска программы или может меняться в течение одного и того же запуска (например, когда необходимо расширить хеш-таблицу). В таких ситуациях нужна хеш-функция, которая принимает два параметра — входные данные z и количество n разрешенных хеш-значений.
Обычное решение — вычислить фиксированную хеш-функцию с очень большим диапазоном (скажем, от 0 до 2 32 − 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 8 = 256 записей; в случае символов Юникода таблица будет иметь размер 17×2 16 =1 114 112 записей.
Тот же метод можно использовать для сопоставления двухбуквенных кодов стран , таких как «нас» или «за», с названиями стран (26 2 = 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 соответствуют одному и тому же адресу. Этот метод хорошо работает на практике, поскольку многие наборы ключей уже достаточно случайны, и вероятность того, что набор ключей будет циклическим из-за большого простого числа, мала.
Алгебраическое кодирование — это вариант метода хеширования с делением, который использует деление на полином по модулю 2 вместо целого числа для преобразования n бит в m бит. [3] : 512–513 В этом подходе мы постулируем полином степени . Ключ можно рассматривать как полином . Остаток с использованием полиномиальной арифметики по модулю 2 равен . Затем . Если он сконструирован так, чтобы иметь или меньше ненулевых коэффициентов, то ключи, которые имеют меньше битов, гарантированно не будут конфликтовать.
функция , и , делитель , строится из поля. Кнут приводит пример: для n=15, m=10 и t=7, . Вывод следующий:
Пусть – наименьший набор целых чисел такой, что и . [Примечания 3]
Определите, где и где в этом поле вычисляются коэффициенты . Тогда степень . Поскольку является корнем всякий раз , когда является корнем, из этого следует, что коэффициенты удовлетворяют , поэтому все они равны 0 или 1. Если является любым ненулевым многочленом по модулю 2 с не более чем ненулевыми коэффициентами, то он не кратен модулю 2. [Примечания 4 ] Из этого следует, что соответствующая хэш-функция будет отображать ключи, имеющие менее общих битов, в уникальные индексы. [3] : 542–543.
Обычный результат таков: либо он станет большим, либо станет большим, либо и то, и другое, чтобы схема стала вычислительно осуществимой. Поэтому он больше подходит для аппаратной реализации или реализации микрокода. [3] : 542–543.
См. также уникальное хеширование перестановок, которое обеспечивает гарантированное лучшее время вставки в худшем случае. [11]
Стандартное мультипликативное хеширование использует формулу , которая создает хеш-значение в формате . Значение представляет собой правильно выбранное значение, которое должно быть относительно простым ; он должен быть большим [ необходимы пояснения ] и его двоичное представление должно представлять собой случайную смесь [ необходимо пояснение ] единиц и нулей. Важный практический частный случай возникает, когда и являются степенями 2, а размер машинного слова . В этом случае эта формула принимает вид . Это особенное явление, поскольку в языках программирования низкого уровня арифметические операции по модулю выполняются по умолчанию, а целочисленное деление на степень 2 — это просто сдвиг вправо, поэтому, например, в C эта функция принимает вид
беззнаковый хэш (беззнаковый K){ возврат (a*K) >> (wm);}
и для фиксированного , и это преобразуется в одно целочисленное умножение и сдвиг вправо, что делает его одной из самых быстрых хеш-функций для вычисления.
Мультипликативное хеширование подвержено «распространенной ошибке», которая приводит к плохой диффузии — входные биты с более высоким значением не влияют на выходные биты с меньшим значением. [12] Преобразование на входе, которое сдвигает диапазон оставшихся старших битов вниз и выполняет операцию XOR или добавляет их к ключу до того, как это будет исправлено на этапе умножения. Итоговая функция выглядит так: [7]
беззнаковый хэш (беззнаковый K){ К ^= К >> (шм); возврат (a*K) >> (wm);}
Хеширование Фибоначчи — это форма мультипликативного хеширования, в которой множителем является , где — длина машинного слова, а (фи) — золотое сечение (приблизительно 5/3). Свойством этого множителя является то, что он равномерно распределяет по табличному пространству блоки последовательных ключей относительно любого блока битов в ключе. Последовательные ключи в старших или младших битах ключа (или какого-либо другого поля) встречаются относительно часто. Множители для различной длины слова :
Множитель должен быть нечетным, поэтому младший бит вывода обратим по модулю . Для достижения этой цели последние два значения, приведенные выше, округляются (в большую и меньшую сторону соответственно) более чем на 1/2 младшего бита.
Табулационное хеширование, более широко известное как хеширование Зобриста в честь Альберта Зобриста , американского ученого-компьютерщика, представляет собой метод построения универсальных семейств хэш-функций путем объединения поиска в таблице с операциями XOR. Этот алгоритм оказался очень быстрым и качественным для целей хеширования (особенно хеширования целочисленных ключей). [13]
Зобристское хеширование изначально было введено как средство компактного представления шахматных позиций в компьютерных игровых программах. Для обозначения каждого типа фигур (по шесть для черных и белых) на каждом поле доски было присвоено уникальное случайное число. Таким образом, в начале программы инициализируется таблица размером 64×12 таких чисел. Случайные числа могли быть любой длины, но 64 бита были естественными из-за 64 клеток на доске. Позиция транскрибировалась путем циклического перебора фигур в позиции, индексирования соответствующих случайных чисел (пустые места не включались в расчет) и их совместного выполнения исключающего ИЛИ (начальное значение могло быть 0, идентификационное значение для исключающего ИЛИ или случайное значение). семя). Полученное значение уменьшалось по модулю, свертыванию или какой-либо другой операции для создания индекса хеш-таблицы. Исходный хэш Зобриста сохранялся в таблице как представление позиции.
Позже метод был расширен до хеширования целых чисел путем представления каждого байта в каждой из 4 возможных позиций слова уникальным 32-битным случайным числом. Таким образом, строится таблица из 2 8 ×4 таких случайных чисел. 32-битное хешированное целое число транскрибируется путем последовательного индексирования таблицы со значением каждого байта простого текстового целого числа и выполнения операции XOR загруженных значений вместе (опять же, начальным значением может быть идентификационное значение или случайное начальное число). Естественным расширением 64-битных целых чисел является использование таблицы из 2 8 × 8 64-битных случайных чисел.
У функции такого типа есть несколько хороших теоретических свойств, одно из которых называется независимостью от трех кортежей, что означает, что каждая тройка ключей с равной вероятностью будет сопоставлена с любой тройкой хеш-значений.
Хэш-функция может быть разработана для использования существующей энтропии в ключах. Если ключи имеют начальные или конечные нули или определенные поля, которые не используются, всегда равны нулю или какой-либо другой константе или вообще мало изменяются, то маскирование только изменчивых битов и их хэширование обеспечит лучшую и, возможно, более быструю хэш-функцию. Выбранные делители или множители в схемах деления и мультипликативных схемах могут создавать более однородные хеш-функции, если ключи являются циклическими или имеют другую избыточность.
Когда значения данных представляют собой длинные строки символов (или переменной длины) , такие как личные имена, адреса веб-страниц или почтовые сообщения, их распределение обычно очень неравномерно со сложными зависимостями. Например, текст на любом естественном языке имеет крайне неравномерное распределение символов и пар символов , характерное для этого языка. Для таких данных разумно использовать хэш-функцию, которая зависит от всех символов строки и зависит от каждого символа по-своему. [ нужны разъяснения ]
Упрощенные хэш-функции могут добавлять первые и последние n символов строки вместе с длиной или формировать хеш размером в слово из средних 4 символов строки. Это позволяет избежать перебора (потенциально длинной) строки, но хеш-функции, которые не хешируют все символы строки, могут легко стать линейными из-за избыточности, кластеризации или других патологий в наборе ключей. Такие стратегии могут быть эффективны в качестве пользовательской хэш-функции, если структура ключей такова, что либо середина, концы или другие поля равны нулю, либо какая-то другая инвариантная константа, которая не различает ключи; тогда инвариантные части ключей можно игнорировать.
Парадигматическим примером свертывания по символам является сложение целочисленных значений всех символов в строке. Лучшая идея — умножить общую сумму хеша на константу, обычно на значительное простое число, перед добавлением следующего символа, игнорируя переполнение. Использование исключающего «или» вместо «добавить» также является разумной альтернативой. Последней операцией будет операция по модулю, маске или другой функции, позволяющая уменьшить значение слова до индекса размером с таблицу. Слабость этой процедуры заключается в том, что информация может группироваться в старших или младших битах байтов, и такая кластеризация останется в хешированном результате и вызовет больше коллизий, чем правильный рандомизирующий хеш. Например, байтовые коды ASCII имеют старший бит, равный 0, а печатаемые строки не используют первые 32 байтовых кода, поэтому информация (95-байтовые коды) группируется в оставшихся битах неочевидным образом.
Классический подход, получивший название хэша PJW, основан на работе Питера. Дж. Вайнбергер из ATT Bell Labs в 1970-х годах изначально был разработан для хеширования идентификаторов в таблицы символов компилятора, как указано в «Книге Дракона» . [14] Эта хеш-функция смещает байты на 4 бита перед их сложением. При переносе количества старшие 4 бита сдвигаются и, если они не равны нулю, выполняются операция XOR обратно в младший байт совокупного количества. Результатом является хеш-код размера слова, к которому можно применить операцию уменьшения по модулю или другую операцию для получения окончательного хэш-индекса.
Сегодня, особенно с появлением 64-битных размеров слов, стало доступно гораздо более эффективное хеширование строк переменной длины по частям слов.
Современные микропроцессоры позволят выполнять гораздо более быструю обработку, если 8-битные строки символов хешируются не путем обработки одного символа за раз, а путем интерпретации строки как массива 32-битных или 64-битных целых чисел и хеширования/накопления этих «широких слов». целочисленные значения с помощью арифметических операций (например, умножения на константу и сдвига битов). Последнее слово, которое может иметь незанятые позиции байтов, перед свертыванием в хэш заполняется нулями или указанным «рандомизирующим» значением. Накопленный хеш-код уменьшается с помощью окончательного модуля или другой операции для получения индекса в таблице.
Аналогично тому, как строка символов ASCII или EBCDIC, представляющая десятичное число, преобразуется в числовую величину для вычислений, строка переменной длины может быть преобразована как ( x 0 a k −1 + x 1 a k −2 +...+ Икс k -2 а + Икс k -1 ) . Это просто многочлен по основанию a > 1 , который принимает компоненты ( x 0 , x 1 ,..., x k −1 ) в качестве символов входной строки длины k . Его можно использовать непосредственно в качестве хэш-кода или применить к нему хеш-функцию для сопоставления потенциально большого значения с размером хеш-таблицы. Значение a обычно представляет собой простое число, по крайней мере, достаточно большое, чтобы вместить количество различных символов в наборе символов потенциальных ключей. Хеширование строк с преобразованием системы оснований сводит к минимуму количество коллизий. [15] Доступные размеры данных могут ограничивать максимальную длину строки, которую можно хешировать с помощью этого метода. Например, 128-битное двойное длинное слово будет хешировать только буквенную строку из 26 символов (без учета регистра) с основанием 29; печатаемая строка ASCII ограничена 9 символами с использованием системы счисления 97 и длинного 64-битного слова. Однако буквенные ключи обычно имеют небольшую длину, поскольку ключи должны храниться в хеш-таблице. Строки числовых символов обычно не представляют проблемы; 64 бита могут считать до 10 19 или 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-битных символьных строках, но также используются и другие подходящие хэш-функции.
Наихудший результат для хэш-функции можно оценить двумя способами: теоретическим и практическим. Теоретически худшим случаем является вероятность того, что все ключи будут привязаны к одному слоту. В худшем практическом случае ожидается самая длинная пробная последовательность (хэш-функция + метод разрешения коллизий). В этом анализе рассматривается равномерное хеширование, то есть любой ключ будет сопоставлен с любым конкретным слотом с вероятностью 1/ m , что характерно для универсальных хеш-функций.
В то время как Кнут беспокоится о состязательной атаке на системы реального времени, [23] Гонне показал, что вероятность такого случая «смехотворно мала». Его представление заключалось в том, что вероятность сопоставления k из n ключей с одним слотом равна где α — коэффициент загрузки, n / m . [24]
Термин « хэш» предлагает естественную аналогию с его нетехническим значением (разрезать или испортить что-либо), учитывая, как хэш-функции шифруют входные данные для получения выходных данных. [25] : 514 В своем исследовании точного происхождения этого термина Дональд Кнут отмечает, что, хотя Ханс Питер Лун из IBM, по-видимому, был первым, кто использовал концепцию хэш-функции в записке, датированной январем 1953 года, термин Сам по себе появился в опубликованной литературе только в конце 1960-х годов, в « Принципах цифровой компьютерной системы» Герберта Хеллермана , хотя к тому времени это уже был широко распространенный жаргон. [25] : 547–548.
Инфраструктура бесключевых подписей (KSI) — это глобально распределенная система для предоставления услуг по отмене времени и цифровой подписи, поддерживаемой сервером. Создаются глобальные посекундные хэш-деревья и публикуются их корневые хэш-значения. Мы обсуждаем некоторые проблемы качества обслуживания, которые возникают при практической реализации услуги, и представляем решения, позволяющие избежать единых точек сбоя и гарантировать предоставление услуги с разумной и стабильной задержкой. Guardtime AS управляет инфраструктурой KSI уже 5 лет. Мы суммируем, как строится инфраструктура KSI, и уроки, извлеченные за период эксплуатации сервиса.
pHash — это программная библиотека с открытым исходным кодом, выпущенная под лицензией GPLv3, которая реализует несколько алгоритмов перцептивного хеширования и предоставляет C-подобный API для использования этих функций в ваших собственных программах.
Сам pHash написан на C++.