Хеш-функция - Hash function

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

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

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

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

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

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

Обзор

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

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

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

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

Хеш-таблицы

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Хеш-функция идентичности

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

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

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

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

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

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

Складной

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

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

Хэш-код в виде средних квадратов создается путем возведения входных данных в квадрат и извлечения соответствующего количества средних цифр или битов. Например, если на входе 123 456 789 и размер хэш-таблицы 10 000, возведение ключа в квадрат дает 1,524157875019e16, поэтому хеш-код будет взят как средние 4 цифры 17-значного числа (без учета старшей цифры) 8750. squares создает разумный хэш-код, если в ключе мало начальных или конечных нулей. Это вариант мультипликативного хеширования, но не такой хороший, потому что произвольный ключ не является хорошим множителем.

Деление хеширования

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

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

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

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

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

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

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

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

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

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

беззнаковый хэш (unsigned K) {return (a * K) >> (w-m);}

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

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

хеш без знака (без знака K) {K ^ = K >> (w-m); return (a * K) >> (ш-м);}

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

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

• 16: а = 40503₁₀
• 32: а = 2654435769₁₀
• 48: а = 173961102589771₁₀^{[Примечания 4]}
• 64: а = 11400714819323198485₁₀^{[Примечания 5]}

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

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

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

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

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

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

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

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

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

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

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

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

Сворачивание символов

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

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

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

Складывание длины слова

Смотрите также: Универсальное хеширование § Хеширующие строки

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

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

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

Прокручивающийся хеш

Основная статья: Прокручивающийся хеш

Смотрите также: Линейный конгруэнтный генератор

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

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

Анализ

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

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

История

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

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

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

Примечания

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

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

1. Кнут Д., 1973, Искусство информатики, Vol. 3, Сортировка и поиск, стр. 527. Эддисон-Уэсли, Рединг, Массачусетс, США
2. Менезеш, Альфред Дж .; van Oorschot, Paul C .; Ванстон, Скотт А. (1996). Справочник по прикладной криптографии. CRC Press. ISBN  978-0849385230.
3. Castro, et.al., 2005, "Тест на случайность строгого лавинного критерия", Mathematics and Computers in Simulation 68 (2005) 1–7, Elsevier,
4. Мальте Шарупке, 2018, «Хеширование Фибоначчи: оптимизация, которую забыл мир (или: лучшая альтернатива целочисленному модулю)»
5. «3. Модель данных - документация Python 3.6.1». docs.python.org. Получено 2017-03-24.
6. Седжвик, Роберт (2002). «14. Хеширование». Алгоритмы на Java (3-е изд.). Эддисон Уэсли. ISBN  978-0201361209.
7. Обычный ASCII - это 7-битная кодировка символов, хотя она часто сохраняется в 8-битных байтах, причем бит наивысшего порядка всегда сброшен (ноль). Следовательно, для простого ASCII байта имеют только 2⁷ = 128 допустимых значений, а таблица преобразования символов содержит только это количество записей.
8. Кнут, Д. 1973, Искусство информатики, Vol. 3, Сортировка и поиск, стр. 512-13. Эддисон-Уэсли, Рединг, Массачусетс, США
9. Кнут, стр. 542-43
10. Кнут, там же.
11. «Уникальное хеширование перестановок». Дои:10.1016 / j.tcs.2012.12.047.
12. «CS 3110 Лекция 21: Хэш-функции». Раздел «Мультипликативное хеширование».
13. Шарупке, Мальте. «Хеширование Фибоначчи: оптимизация, которую забыл мир». вероятноdance.com. wordpress.com.
14. Зобрист, Альберт Л. (Апрель 1970 г.), Новый метод хеширования с приложением для игры (PDF), Тех. Представитель 88, Мэдисон, Висконсин: Департамент компьютерных наук, Университет Висконсина.
15. Ахо, Сетхи, Уллман, 1986, Компиляторы: принципы, методы и инструменты, стр. 435. Аддисон-Уэсли, Рединг, Массачусетс.
16. Производительность на практике функций хеширования строк CiteSeer^Икс: 10.1.1.18.7520
17. «Найти самую длинную подстроку с k уникальными символами в заданной строке». Гики. 2015-03-18. Получено 2020-05-30.
18. Кнут, Д. 1975, Искусство компьютерного программирования, Vol. 3. Сортировка и поиск, стр. 540. Эддисон-Уэсли, Ридинг, Массачусетс
19. Гоннет, Г. 1978, «Ожидаемая длина самой длинной тестовой последовательности при поиске хэш-кода», CS-RR-78-46, Университет Ватерлоо, Онтарио, Канада
20. Кнут, Дональд Э. (2000). Сортировка и поиск (2-е изд., 6. полиграфическое, обновленное и перераб. Ред.). Бостон [u.a.]: Эддисон-Уэсли. п. 514. ISBN  978-0-201-89685-5.
21. Кнут, Дональд Э. (2000). Сортировка и поиск (2-е изд., 6. полиграфическое, обновленное и перераб. Ред.). Бостон [u.a.]: Эддисон-Уэсли. С. 547–548. ISBN  978-0-201-89685-5.

внешняя ссылка

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