Хэш -функция — это любая функция , которая может использоваться для преобразования данных произвольного размера в значения фиксированного размера, хотя существуют некоторые хэш-функции, которые поддерживают вывод переменной длины. [1] Значения, возвращаемые хэш-функцией, называются хэш-значениями , хэш-кодами , хэш-дайджестами , дайджестами или просто хэшами . [2] Значения обычно используются для индексации таблицы фиксированного размера, называемой хэш-таблицей . Использование хэш-функции для индексации хэш-таблицы называется хэшированием или адресацией с разбросанным хранением .
Хэш-функции и связанные с ними хэш-таблицы используются в приложениях хранения и извлечения данных для доступа к данным за небольшое и почти постоянное время на извлечение. Они требуют объем дискового пространства, лишь немного превышающий общее пространство, необходимое для самих данных или записей. Хеширование — это вычислительно- и дисковое пространство эффективной формы доступа к данным, которая позволяет избежать непостоянного времени доступа упорядоченных и неупорядоченных списков и структурированных деревьев, а также часто экспоненциальных требований к хранению прямого доступа к пространствам состояний больших или переменных по длине ключей.
Использование хэш-функций основано на статистических свойствах взаимодействия ключей и функций: наихудшее поведение недопустимо плохо, но встречается редко, а среднее поведение может быть почти оптимальным (минимальное столкновение ). [3] : 527
Хэш-функции связаны (и часто путаются) с контрольными суммами , контрольными цифрами , отпечатками пальцев , сжатием с потерями , функциями рандомизации , кодами исправления ошибок и шифрами . Хотя эти концепции в некоторой степени пересекаются, каждая из них имеет свои собственные области применения и требования и разработана и оптимизирована по-разному. Хэш-функция отличается от этих концепций в основном с точки зрения целостности данных . Хэш-таблицы могут использовать некриптографические хэш-функции , в то время как криптографические хэш-функции используются в кибербезопасности для защиты конфиденциальных данных, таких как пароли.
В хэш-таблице хэш-функция принимает ключ в качестве входных данных, который связан с данными или записью и используется для идентификации его в приложении хранения и извлечения данных. Ключи могут быть фиксированной длины, как целое число, или переменной длины, как имя. В некоторых случаях ключом является сам этот объект. Выходными данными является хэш-код, используемый для индексации хэш-таблицы, содержащей данные или записи, или указатели на них.
Можно считать, что хеш-функция выполняет три функции:
Хорошая хэш-функция удовлетворяет двум основным свойствам: она должна быть очень быстрой для вычисления и должна минимизировать дублирование выходных значений ( коллизии ). Хэш-функции полагаются на генерацию благоприятных распределений вероятностей для своей эффективности, сокращая время доступа до почти постоянного значения. Высокие факторы загрузки таблицы, патологические наборы ключей и плохо спроектированные хэш-функции могут привести к тому, что время доступа будет приближаться к линейному по количеству элементов в таблице. Хэш-функции могут быть разработаны для обеспечения наилучшей производительности в худшем случае, [Примечание 1] хорошей производительности при высоких факторах загрузки таблицы и в особых случаях идеального (без коллизий) отображения ключей в хэш-коды. Реализация основана на сохраняющих четность битовых операциях (XOR и ADD), умножении или делении. Необходимым дополнением к хэш-функции является метод разрешения коллизий, который использует вспомогательную структуру данных, такую как связанные списки , или систематическое зондирование таблицы для поиска пустого слота.
Хэш-функции используются совместно с хэш-таблицами для хранения и извлечения элементов данных или записей данных. Хэш-функция преобразует ключ, связанный с каждым элементом данных или записью, в хэш-код, который используется для индексации хэш-таблицы. Когда элемент должен быть добавлен в таблицу, хэш-код может индексировать пустой слот (также называемый сегментом), в этом случае элемент добавляется в таблицу туда. Если хэш-код индексирует полный слот, то требуется некое разрешение коллизий: новый элемент может быть пропущен (не добавлен в таблицу), или заменен старым элементом, или добавлен в таблицу в каком-то другом месте с помощью указанной процедуры. Эта процедура зависит от структуры хэш-таблицы. В цепочечном хэшировании каждый слот является головой связанного списка или цепочки, и элементы, которые сталкиваются в слоте, добавляются в цепочку. Цепочки могут храниться в случайном порядке и искаться линейно, или в последовательном порядке, или как самоупорядочивающийся список по частоте для ускорения доступа. При хешировании открытого адреса таблица проверяется, начиная с занятого слота, указанным способом, обычно линейным зондированием , квадратичным зондированием или двойным хешированием , пока не будет найден открытый слот или не будет проверена вся таблица (переполнение). Поиск элемента следует той же процедуре, пока элемент не будет найден, открытый слот не будет найден или пока не будет просмотрена вся таблица (элемент отсутствует в таблице).
Хэш-функции также используются для создания кэшей для больших наборов данных, хранящихся на медленных носителях. Кэш, как правило, проще, чем хэшированная таблица поиска, поскольку любое столкновение может быть разрешено путем отбрасывания или записи обратно более старого из двух конфликтующих элементов. [4]
Хэш-функции являются неотъемлемой частью фильтра Блума — вероятностной структуры данных , которая эффективно использует память и используется для проверки принадлежности элемента множеству .
Особый случай хеширования известен как геометрическое хеширование или метод сетки . В этих приложениях набор всех входных данных представляет собой некое метрическое пространство , а функция хеширования может быть интерпретирована как разбиение этого пространства на сетку ячеек . Таблица часто представляет собой массив с двумя или более индексами (называемый файлом сетки , индексом сетки , сеткой бакета и аналогичными именами), а функция хеширования возвращает кортеж индекса . Этот принцип широко используется в компьютерной графике , вычислительной геометрии и многих других дисциплинах для решения многих задач близости на плоскости или в трехмерном пространстве , таких как поиск ближайших пар в наборе точек, похожих фигур в списке фигур, похожих изображений в базе данных изображений и так далее.
Хэш-таблицы также используются для реализации ассоциативных массивов и динамических наборов . [5]
Хорошая хэш-функция должна отображать ожидаемые входы как можно более равномерно по всему диапазону выходных данных. То есть каждое значение хэша в диапазоне выходных данных должно генерироваться примерно с одинаковой вероятностью . Причина этого последнего требования заключается в том, что стоимость методов на основе хэширования резко возрастает по мере увеличения числа коллизий — пар входов, сопоставленных с одним и тем же значением хэша. Если некоторые значения хэша встречаются чаще, чем другие, то большая часть операций поиска должна будет выполнять поиск по большему набору сталкивающихся записей таблицы.
Этот критерий требует только, чтобы значение было равномерно распределено , а не случайно в каком-либо смысле. Хорошая рандомизирующая функция (исключая проблемы вычислительной эффективности) обычно является хорошим выбором в качестве хэш-функции, но обратное не обязательно должно быть верным.
Хеш-таблицы часто содержат только небольшое подмножество допустимых входных данных. Например, список членов клуба может содержать только около сотни имен членов из очень большого набора всех возможных имен. В этих случаях критерий единообразия должен соблюдаться почти для всех типичных подмножеств записей, которые могут быть найдены в таблице, а не только для глобального набора всех возможных записей.
Другими словами, если типичный набор из m записей хэшируется в n слотов таблицы, то вероятность того, что ведро получит намного больше, чем m / n записей, должна быть исчезающе мала. В частности, если m < n , то очень немногие ведра должны иметь больше одной или двух записей. Небольшое количество коллизий практически неизбежно, даже если n намного больше m — см. задачу о днях рождения .
В особых случаях, когда ключи известны заранее и набор ключей статичен, можно найти хэш-функцию, которая достигает абсолютной (или бесколлизионной) однородности. Такая хэш-функция называется идеальной . Не существует алгоритмического способа построения такой функции — поиск одной из них является факториальной функцией количества ключей, которые должны быть сопоставлены, по сравнению с количеством ячеек таблицы, в которые они сопоставлены. Нахождение идеальной хэш-функции для более чем очень малого набора ключей обычно вычислительно неосуществимо; полученная функция, вероятно, будет более вычислительно сложной, чем стандартная хэш-функция, и обеспечивает лишь незначительное преимущество перед функцией с хорошими статистическими свойствами, которая дает минимальное количество коллизий. См. универсальная хэш-функция .
При тестировании хэш-функции равномерность распределения хэш-значений можно оценить с помощью теста хи-квадрат . Этот тест является мерой соответствия: это фактическое распределение элементов в корзинах по сравнению с ожидаемым (или равномерным) распределением элементов. Формула имеет вид
где n — количество ключей, m — количество сегментов, а b j — количество элементов в сегменте 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 (ключ) / 2 b . Мы можем заменить деление (возможно, более быстрым) сдвигом бита вправо : n P (ключ) >> 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 записей; в случае символов Unicode таблица будет иметь 17 × 2 16 =1 114 112 записей.
Тот же метод можно использовать для сопоставления двухбуквенных кодов стран , таких как «us» или «za», с названиями стран (26 · 2 = 676 записей в таблице), пятизначных почтовых индексов, таких как 13083, с названиями городов (100 000 записей) и т. д. Недопустимые значения данных (например, код страны «xx» или почтовый индекс 00000) могут быть оставлены неопределенными в таблице или сопоставлены с некоторым подходящим «нулевым» значением.
Если ключи равномерно или достаточно равномерно распределены по ключевому пространству, так что значения ключей по сути случайны, то их можно считать уже «хэшированными». В этом случае любое количество любых битов в ключе может быть извлечено и сопоставлено как индекс в хэш-таблице. Например, простая хэш-функция может маскировать m наименее значимых битов и использовать результат как индекс в хэш-таблице размером 2 m .
Складывающийся хэш-код создается путем деления входных данных на секции по m бит, где 2 m — размер таблицы, и использования сохраняющей четность побитовой операции, такой как 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 (mod M ) . Размер таблицы обычно равен степени 2. Это дает распределение из {0, M − 1} . Это дает хорошие результаты для большого количества наборов ключей. Существенным недостатком хеширования деления является то, что деление микропрограммируется на большинстве современных архитектур (включая x86 ) и может быть в 10 раз медленнее умножения. Вторым недостатком является то, что оно не разбивает кластеризованные ключи. Например, ключи 123000, 456000, 789000 и т. д. по модулю 1000 все отображаются на один и тот же адрес. Эта техника хорошо работает на практике, поскольку многие наборы ключей уже достаточно случайны, и вероятность того, что набор ключей будет циклическим по большому простому числу, мала.
Алгебраическое кодирование — это вариант метода деления хеширования, который использует деление на многочлен по модулю 2 вместо целого числа для отображения n бит в m бит. [3] : 512–513 В этом подходе M = 2 m , и мы постулируем многочлен m -й степени Z ( x ) = x m + ζ m −1 x m −1 + ⋯ + ζ 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 ) mod 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 , m , t ) = (15,10,7), получаем Z ( x ) = x 10 + x 8 + x 5 + x 4 + x 2 + x + 1 . Вывод следующий:
Пусть S будет наименьшим набором целых чисел, таким, что {1,2,…, t } ⊆ S и (2 j mod n ) ∈ S ∀ j ∈ S . [Примечания 3]
Определим , где α ∈ n GF(2 k ) и где коэффициенты P ( x ) вычисляются в этом поле. Тогда степень P ( x ) = | S | . Поскольку α 2 j является корнем P ( x ) всякий раз, когда α j является корнем, то отсюда следует, что коэффициенты p i P ( x ) удовлетворяют p2
я= p i , поэтому все они равны 0 или 1. Если R ( x ) = r n −1 x n −1 + ⋯ + r 1 x + r 0 — любой ненулевой многочлен по модулю 2 с не более чем t ненулевыми коэффициентами, то R ( x ) не является кратным P ( x ) по модулю 2. [Примечания 4] Из этого следует, что соответствующая хеш-функция будет отображать ключи с меньшим, чем t общими битами, в уникальные индексы. [3] : 542–543
Обычным результатом является то, что либо n станет большим, либо t станет большим, или и то, и другое, чтобы схема была вычислительно осуществимой. Поэтому она больше подходит для аппаратной или микрокодовой реализации. [3] : 542–543
Уникальное хеширование перестановок имеет гарантированно лучшее время вставки в худшем случае. [11]
Стандартное мультипликативное хеширование использует формулу h a ( K ) = ⌊ ( aK mod W ) / ( W / M ) ⌋ , которая создает хеш-значение в {0, …, M − 1} . Значение a — это соответствующим образом выбранное значение, которое должно быть относительно простым с W ; оно должно быть большим, [ необходимо разъяснение ] и его двоичное представление — случайная смесь [ необходимо разъяснение ] единиц и нулей. Важный практический особый случай возникает, когда W = 2 w и M = 2 m являются степенями 2, а w — размером машинного слова . В этом случае эта формула становится h a ( K ) = ⌊ ( aK mod 2 w ) / 2 w − m ⌋ . Это особенность, поскольку арифметика по модулю 2 w выполняется по умолчанию в языках программирования низкого уровня, а целочисленное деление на степень 2 — это просто сдвиг вправо, поэтому, например, в C эта функция становится
беззнаковый хэш(беззнаковый K) { возврат (a*K) >> (wm);}а для фиксированных m и w это преобразуется в одно целочисленное умножение и сдвиг вправо, что делает ее одной из самых быстрых для вычисления хеш-функций.
Мультипликативное хеширование подвержено «распространенной ошибке», которая приводит к плохой диффузии — входные биты с более высоким значением не влияют на выходные биты с более низким значением. [12] Трансмутация на входе, которая сдвигает диапазон сохраненных верхних битов вниз и выполняет XOR или ADD с ключом до того, как шаг умножения исправит это. Результирующая функция выглядит следующим образом: [7]
беззнаковый хэш(беззнаковый K) { К ^= К >> (вм); возврат (a*K) >> (wm);}Хеширование Фибоначчи — это форма мультипликативного хеширования, в которой множитель равен 2 w / ϕ , где w — длина машинного слова, а ϕ (фи) — золотое сечение (приблизительно 1,618). Свойство этого множителя заключается в том, что он равномерно распределяет по табличному пространству блоки последовательных ключей относительно любого блока битов в ключе. Последовательные ключи в пределах старших или младших битов ключа (или некоторого другого поля) встречаются относительно часто. Множители для различных длин слов следующие:
Множитель должен быть нечетным, поэтому младший бит выходного значения является обратимым по модулю 2 w . Последние два значения, приведенные выше, округлены (вверх и вниз соответственно) более чем на 1/2 младшего бита, чтобы достичь этого.
Табуляционное хеширование, более известное как хеширование Зобриста в честь Альберта Зобриста , представляет собой метод построения универсальных семейств хеш-функций путем объединения табличного поиска с операциями XOR. Этот алгоритм оказался очень быстрым и высококачественным для целей хеширования (особенно хеширования ключей с целыми числами). [13]
Хеширование Зобриста изначально было введено как средство компактного представления шахматных позиций в программах для компьютерных игр. Для представления каждого типа фигур (по шесть для черных и белых) на каждой клетке доски назначалось уникальное случайное число. Таким образом, таблица из 64×12 таких чисел инициализируется в начале программы. Случайные числа могут быть любой длины, но 64 бита были естественными из-за 64 клеток на доске. Позиция транскрибировалась путем циклического перебора фигур в позиции, индексирования соответствующих случайных чисел (пустые клетки не включались в расчет) и их объединения с помощью операции XOR (начальное значение могло быть 0 (тождественное значение для XOR) или случайным начальным числом). Полученное значение уменьшалось с помощью модуля, свертывания или какой-либо другой операции для получения индекса хеш-таблицы. Исходный хеш Зобриста сохранялся в таблице как представление позиции.
Позже метод был расширен до хеширования целых чисел путем представления каждого байта в каждой из 4 возможных позиций в слове уникальным 32-битным случайным числом. Таким образом, строится таблица из 2 8 × 4 случайных чисел. 32-битное хешированное целое число транскрибируется путем последовательного индексирования таблицы значением каждого байта текстового целого числа и выполнения операции XOR загруженных значений (опять же, начальное значение может быть значением идентичности или случайным начальным числом). Естественное расширение до 64-битных целых чисел заключается в использовании таблицы из 2 8 × 8 64-битных случайных чисел.
Этот тип функции обладает некоторыми интересными теоретическими свойствами, одно из которых называется независимостью от 3-х кортежей , что означает, что каждый кортеж из 3 ключей с равной вероятностью может быть сопоставлен любому кортежу из 3-х хэш-значений.
Хэш-функция может быть разработана для использования существующей энтропии в ключах. Если ключи имеют начальные или конечные нули или определенные поля, которые не используются, всегда равны нулю или какой-либо другой константе, или вообще мало изменяются, то маскирование только изменчивых битов и хэширование на них обеспечит лучшую и, возможно, более быструю хэш-функцию. Выбранные делители или множители в схемах деления и умножения могут сделать более однородные хэш-функции, если ключи цикличны или имеют другие избыточности.
Когда значения данных представляют собой длинные (или переменной длины) строки символов — например, личные имена, адреса веб-страниц или почтовые сообщения — их распределение обычно очень неравномерно, со сложными зависимостями. Например, текст на любом естественном языке имеет крайне неравномерное распределение символов и пар символов , характерных для языка. Для таких данных разумно использовать хэш-функцию, которая зависит от всех символов строки — и зависит от каждого символа по-разному. [ требуется разъяснение ]
Упрощенные хэш-функции могут добавлять первые и последние n символов строки вместе с длиной или формировать хэш размером со слово из средних 4 символов строки. Это экономит итерации по (потенциально длинной) строке, но хэш-функции, которые не хэшируют все символы строки, могут легко стать линейными из-за избыточности, кластеризации или других патологий в наборе ключей. Такие стратегии могут быть эффективными в качестве пользовательской хэш-функции, если структура ключей такова, что либо середина, концы, либо другие поля равны нулю или некоторой другой инвариантной константе, которая не различает ключи; тогда инвариантные части ключей можно игнорировать.
Парадигматическим примером сворачивания по символам является сложение целочисленных значений всех символов в строке. Лучшей идеей является умножение суммы хэша на константу, обычно на значительное простое число, перед добавлением следующего символа, игнорируя переполнение. Использование исключающего ИЛИ вместо сложения также является правдоподобной альтернативой. Конечной операцией будет модуль, маска или другая функция для уменьшения значения слова до индекса размера таблицы. Слабость этой процедуры заключается в том, что информация может группироваться в верхних или нижних битах байтов; эта кластеризация останется в хэшированном результате и вызовет больше коллизий, чем правильный рандомизирующий хэш. Например, байт-коды ASCII имеют верхний бит 0, а печатаемые строки не используют первые 32 байт-кода, поэтому информация (95 байт-кодов) группируется в оставшихся битах неочевидным образом.
Классический подход, названный хэшем PJW , основанный на работе Питера Дж. Вайнбергера в Bell Labs в 1970-х годах, изначально был разработан для хэширования идентификаторов в таблицы символов компилятора, как указано в «Книге Дракона» . [14] Эта хэш-функция смещает байты на 4 бита перед их сложением. Когда количество заканчивается, старшие 4 бита сдвигаются и, если они не равны нулю, возвращаются обратно в младший байт кумулятивного количества с помощью операции xor. Результатом является хэш-код размером со слово, к которому можно применить операцию по модулю или другую операцию сокращения для получения окончательного индекса хэша.
Сегодня, особенно с появлением 64-битных размеров слов, доступно гораздо более эффективное хеширование строк переменной длины по фрагментам слов.
Современные микропроцессоры позволят производить гораздо более быструю обработку, если 8-битные строки символов не будут хэшироваться путем обработки одного символа за раз, а будут интерпретироваться как массив 32-битных или 64-битных целых чисел и хэшироваться/накапливаться эти целые значения "широкого слова" с помощью арифметических операций (например, умножения на константу и сдвига битов). Конечное слово, которое может иметь незанятые позиции байтов, заполняется нулями или указанным рандомизирующим значением перед тем, как быть сложенным в хэш. Накопленный хэш-код уменьшается с помощью конечного модуля или другой операции для получения индекса в таблице.
Аналогично тому, как строка символов ASCII или EBCDIC, представляющая десятичное число, преобразуется в числовую величину для вычисления, строка переменной длины может быть преобразована как x k −1 a k −1 + x k −2 a k −2 + ⋯ + x 1 a + x 0 . Это просто многочлен по основанию 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 — количество вхождений подстроки. [16] [ каков выбор h? ]
Наиболее известным алгоритмом этого типа является алгоритм Рабина-Карпа с производительностью в лучшем и среднем случае O ( n + mk ) и в худшем случае O ( n · k ) (справедливости ради, худший случай здесь является серьезно патологическим: и текстовая строка, и подстрока состоят из повторяющегося одного символа, например, t ="AAAAAAAAAAAA" и s ="AAA"). Хэш-функция, используемая для алгоритма, обычно является отпечатком Рабина , разработанным для предотвращения коллизий в 8-битных строках символов, но используются и другие подходящие хэш-функции.
Результаты худшего случая для хэш-функции можно оценить двумя способами: теоретическим и практическим. Теоретически худший случай — это вероятность того, что все ключи сопоставляются с одним слотом. Практический худший случай — это ожидаемая самая длинная последовательность проб (хэш-функция + метод разрешения коллизий). Этот анализ рассматривает равномерное хэширование, то есть любой ключ будет сопоставляться с любым конкретным слотом с вероятностью 1/ m , что является характеристикой универсальных хэш-функций.
В то время как Кнут беспокоится о состязательной атаке на системы реального времени, [24] Гонне показал, что вероятность такого случая «смехотворно мала». Его представление состояло в том, что вероятность отображения k из n ключей в один слот составляет α k / ( e α k !) , где α — коэффициент загрузки, n / m . [25]
Термин хэш предлагает естественную аналогию с его нетехническим значением (измельчать или создавать беспорядок из чего-либо), учитывая, как хэш-функции перемешивают свои входные данные, чтобы получить свой вывод. [26] : 514 В своем исследовании точного происхождения термина Дональд Кнут отмечает, что, хотя Ганс Петер Лун из IBM, по-видимому, был первым, кто использовал концепцию хэш-функции в служебной записке от января 1953 года, сам термин не появлялся в опубликованной литературе до конца 1960-х годов, в работе Герберта Хеллермана « Принципы цифровых компьютерных систем» , хотя к тому времени он уже был широко распространенным жаргоном. [26] : 547–548
Инфраструктура бесключевых подписей (KSI) — это глобально распределенная система для предоставления услуг временной отметки и цифровой подписи с поддержкой сервера. Создаются глобальные деревья хэшей с посекундной частотой и публикуются их корневые хэш-значения. Мы обсуждаем некоторые проблемы качества обслуживания, возникающие при практической реализации сервиса, и представляем решения для избежания отдельных точек отказа и обеспечения обслуживания с разумной и стабильной задержкой. Guardtime AS эксплуатирует инфраструктуру KSI в течение 5 лет. Мы описываем, как строится инфраструктура KSI, и извлекаем уроки за период эксплуатации сервиса.
pHash — это библиотека программного обеспечения с открытым исходным кодом, выпущенная по лицензии GPLv3, которая реализует несколько алгоритмов перцептивного хэширования и предоставляет API-интерфейс на языке C для использования этих функций в ваших собственных программах. Сам pHash написан на C++.
