Хеш-функция

Эта статья требует дополнительных ссылок для проверки . Пожалуйста, помогите улучшить эту статью , добавив цитаты из надежных источников . Материал, не полученный от источника, может быть оспорен и удален. Поиск источников:  «Функция хеширования»  -  новости  · газеты  · книги  · научный сотрудник  · JSTOR ( июль 2010 г. ) ( Узнайте, как и когда удалить этот шаблон сообщения )

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

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

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

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

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

Обзор [ править ]

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

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

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

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

Хеш-таблицы [ править ]

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

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

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

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

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

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

Свойства [ править ]

Единообразие [ править ]

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

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

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

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

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

Тестирование и измерения [ править ]

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

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

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

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

Эффективность [ править ]

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

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

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

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

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

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

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

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

Применимость [ править ]

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

Детерминированный [ править ]

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

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

Определенный диапазон [ править ]

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

Диапазон переменных [ править ]

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

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

Диапазон переменных с минимальным перемещением (динамическая хеш-функция) [ править ]

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

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

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

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

Нормализация данных [ править ]

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

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

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

Хэш-функция идентификации [ править ]

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

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

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

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

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

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

Складывание [ править ]

Хеш-код складывания создается путем деления входных данных на 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 создает разумный хэш-код, если в ключе мало начальных или конечных нулей. Это вариант мультипликативного хеширования, но не такой хороший, потому что произвольный ключ не является хорошим множителем.

Хеширование деления [ править ]

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

Алгебраическое кодирование [ править ]

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

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}$

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

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

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

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

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

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

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

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

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

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

Хеширование Фибоначчи [ править ]

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

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

Zobrist хеширование [ править ]

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

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

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

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

Индивидуальная хеш-функция [ править ]

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

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

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

Середина и концы [ править ]

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

Складывание символов [ править ]

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

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

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

Складывание длины слова [ править ]

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

Хеширование преобразования Radix [ править ]

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

Скользящий хеш [ править ]

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

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

Анализ [ править ]

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

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

История [ править ]

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

См. Также [ править ]

Поищите хеш в Викисловаре, бесплатном словаре.

Примечания [ править ]

Ссылки [ править ]

Внешние ссылки [ править ]

Поищите хеш в Викисловаре, бесплатном словаре.

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