Наиболее важными алгоритмами в промышленности являются хеширование, хеширование и снова хеширование.

$-$ Udi Manber

Определения

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

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

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

$$ H(S) = H(S') $$

Хеширование

Мы будем использовать значение нашей хеш-функции в качестве индекса массива и записывать элемент в этой позиции. Сначала хеш-функция соотносит каждый ключ (в нашем случае строку S) с большим целым числом. Пусть значение $\alpha$ представляет размер алфавита, используемого для создания строки S. Пусть char (с) будет функцией, которая однозначно отображает каждый символ алфавита в целое число в диапазоне от 0 до а - 1. Функция

$$ H(S) = \alpha^{|S|}+\sum_{i=0}^{|S|-1} \alpha^{|S|-(i+1)} \times char(s_i) $$

однозначно отображает каждую строку в (большое) целое число, рассматривая символы строки как «цифры» системы счисления с основанием а. В результате получатся уникальные идентификационные числа, но они будут настолько большими, что очень быстро превысят количество требуемых ячеек в нашей хеш-таблице (обозначаемое m). Это значение необходимо уменьшить до целого числа в диапазоне от 0 до $m - 1$, для чего выполняется операция получения остатка от деления

$$ H'(S) = H(S)\ \ mod(m). $$

Примеры использования

Пример: Пусть S = "abacab", количество ячеек $m=127$ алфавит состоит из целых трех букв ($\alpha = 3$) a,b,c, причем: $char(a) = 0, char(b) = 1, char(c) = 2$. Тогда

$$ H(S) = 3^6 + 3^5 \cdot 0 + 3^4 \cdot 1 + 3^3 \cdot 0 + 3^2 \cdot 2 + 3 \cdot 0 + 1 = 829\ mod(127) = 67 $$

Пример 2: Пусть при тех же начальных условиях S = "accca". Тогда

$$ H(S) = 3^5 + 3^4 \cdot 0 + 3^3 \cdot 2 + 3^2 \cdot 2 + 3 \cdot 2 + 0 = 321\ mod(127) = 67 $$

Мы встретили такое явление как коллизия.

Коллизия

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

• С использованием цепочек. Цепочка представляет массив из т связных списков (корзин). Список с порядковым номером m содержит все элементы, хешированные в одно и то же значение і. Операции поиска, вставки и удаления сводятся к соответствующим операциям в связных списках. Если и ключей распределены в таблице равномерно, то каждый список будет содержать приблизительно n/m элементов, делая их размер постоянным при m ~ n.

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

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

Операция	Ожидаемой время исполнения	Время исполнения в наихудшем случае
search(L,k)	O(n/m)	O(n)
insert(L,x)	O(1)	O(1)
delete(L,x)	O(1)	O(1)
successor(L,x)	O(n + m)	O(n + m)
predecessor(L,x)	O(n + m)	O(n + m)
minimum(L)	O(n + m)	O(n + m)
maximum(L)	O(n + m)	O(n + m)

Выявления дубликатов с помощью хеширования

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

Некоторые задачи имеют красивое решение при помощи хеширования:

• Является ли документ уникальным? Для большого собрания документов мы можем преобразовать документ в целое число с помощью хеш-функции и сравнить с хеш-кодами других документов. Документ может быть дубликатом только при одинаковом коллизии (одинаковых хеш-значениях). Такие документы можно явно сравнить ввиду их небольшого (теоретически при большом количестве ячеек) количества.

• Является ли документ плагиатом? Решить задачу так же, как прошлую не получится, так как изменение даже одного символа сильно изменит итоговый хеш-код. Однако мы можем создать хеш-таблицу всех подстрок длиной w всех документов в базе данных (для достаточно большого w, чтобы избежать случайных совпадений) и подробней исследовать лишь совпадения хеш-кодов разных документов.

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

Каноникализация

Предположим, что нам нужно найти все слова (имеющие смысл последовательности букв) из словаря, полученного перестановками букв множества S. Например из множества $S = (a,e,k,l)$ можно получить слова lake, kale, leak. Вместо прямой проверки мы создадим хеш-строку каждого слова, предварительно упорядочив буквы внутри. В результате все слова с одинаковым распределением букв хешируются в одной и той же корзине.

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

Литература

[ Скиена 2022 с. 121 - 126]