Обновлено: 07.07.2024

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

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

История

Дональд Кнут относит первую систематическую идею хеширования к сотруднику IBM Хансу Петеру Луну (нем. Hans Peter Luhn ), предложившему хеш-кодирование в январе 1953 года.

В 1956 году Арнольд Думи (англ. Arnold Dumey ) в своей работе «Computers and automation» первым представил концепцию хеширования таковой, какой её знает большинство программистов сейчас. Думи рассматривал хеширование, как решение «Проблемы словаря», а также предложил использовать в качестве хеш-адреса остаток деления на простое число. [1]

Первой серьёзной работой, связанной с поиском в больших файлах, была статья Уэсли Питерсона (англ. W. Wesley Peterson ) в IBM Journal of Research and Development 1957 года, в которой он определил открытую адресацию, а также указал на ухудшение производительности при удалении. Спустя шесть лет была опубликована работа Вернера Бухгольца (нем. Werner Buchholz ), в которой проведено обширное исследование хеш-функций. В течение нескольких последующих лет хеширование широко использовалось, однако не было опубликовано никаких значимых работ.

В 1967 году хеширование в современном значении упомянуто в книге Херберта Хеллермана «Принципы цифровых вычислительных систем». В 1968 году Роберт Моррис (англ. Robert Morris ) опубликовал в Communications of the ACM большой обзор по хешированию, эта работа считается ключевой публикацией, вводящей понятие о хешировании в научный оборот и закрепившей ранее применявшийся только в жаргоне специалистов термин «хеш».

До начала 1990-х годов в русскоязычной литературе в качестве эквивалента термину «хеширование» благодаря работам Андрея Ершова использовалось слово «расстановка», а для коллизий использовался термин "конфликт" (Ершов использовал «расстановку» с 1956 года, в русскоязычном издании книги Вирта «Алгоритмы и структуры данных» 1989 года также используется термин «расстановка»). Предлагалось также назвать метод русским словом «окрошка». Однако ни один из этих вариантов не прижился, и в русскоязычной литературе используется преимущественно термин «хеширование». [3]

Виды хеш-функций

Хорошая хеш-функция должна удовлетворять двум свойствам:

1. Быстро вычисляться;
2. Минимизировать количество коллизий

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

В качестве примера «плохой» хеш-функции можно привести функцию с , которая десятизначному натуральном числу сопоставляет три цифры выбранные из середины двадцатизначного квадрата числа . Казалось бы значения хеш-кодов должны равномерно распределиться между «000» и «999», но для реальных данных такой метод подходит лишь в том случае, если ключи не имеют большого количества нулей слева или справа. [3]

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

Хеш-функции, основанные на делении

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

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

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

При правильном выборе такой способ гарантирует отсутствие коллизий между почти одинаковыми ключами. [3]

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

Второй метод состоит в выборе некоторой целой константы , взаимно простой с , где — количество представимых машинным словом значений (в компьютерах IBM PC " />
). Тогда можем взять хеш-функцию вида:

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

Среди преимуществ этих двух методов стоит отметь, что они выгодно используют то, что реальные ключи неслучайны, например в том случае если ключи представляют собой арифметическую прогрессию (допустим последовательность имён «ИМЯ1», «ИМЯ2», «ИМЯ3»). Мультипликативный метод отобразит арифметическую прогрессию в приближенно арифметическую прогрессию различных хеш-значений, что уменьшает количество коллизий по сравнению со случайной ситуацией. [3]

Одной из вариаций данного метода является хеширование Фибоначчи, основанное на свойствах золотого сечения. В качестве здесь выбирается ближайшее к *w" />
целое число, взаимно простое с

Хеширование строк переменной длины

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

Алгоритм можно описать следующим псевдокодом, который получает на вход строку и использует таблицу перестановок

Среди преимуществ алгоритма следует отметить:

• Простоту вычисления;
• Не существует таких входных данных, для которых вероятность коллизии наибольшая;
• Возможность модификации в идеальную хеш-функцию.

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

Идеальное хеширование

Идеальной хеш-функцией (англ. Perfect hash function ) называется такая функция, которая отображает каждый ключ из набора в множество целых чисел без коллизий. В математических терминах это инъективное отображение.

Описание

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

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

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

Описание

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

.

Аннотация

• System.Security.Cryptography
• System.Text

Вычисление значения hash

Легко создавать и сравнивать значения hash с помощью криптографических ресурсов, содержащихся в System.Security.Cryptography пространстве имен. Так как все функции hash принимают ввод типа, может потребоваться преобразовать источник в массив byte перед его Byte[] хашированием. Чтобы создать hash для значения строки, выполните следующие действия:

Используйте директиву в пространствах имен и имен, чтобы в коде не требовалось квалифицировать объявления из этих пространств using System System.Security.Cryptography System.Text имен. Эти утверждения необходимо использовать перед любыми другими заявлениями.

Объявите переменную строки для хранения исходных данных и два массива byte (неопределяемого размера) для хранения исходных bytes и полученных значений хаширования.

Используйте метод класса, чтобы преобразовать исходные строки в массив bytes (необходимый в качестве ввода в функцию GetBytes() System.Text.ASCIIEncoding хешинга).

Вычисляйте хаш MD5 для исходных данных, позвонив ComputeHash в экземпляр MD5CryptoServiceProvider класса.

Чтобы вычислить другое значение hash, необходимо создать еще один экземпляр класса.

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

Сравнение двух значений hash

Цели создания хаш из исходных данных:

• Предоставление способа узнать, изменились ли данные с течением времени.
• Сравнение двух значений без работы с фактическими значениями.

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

Ниже создания гексадецимальной строки создайте новое значение хеши на основе новых исходных данных.

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

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

Полное перечисление кода

Ссылки

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

Введение

Начнем с определения. Пусть у нас есть строка s_0..n-1. Полиномиальным хешем этой строки называется число h = hash(s_0..n-1) = s₀ + ps₁ + p 2 s₂ +… + p n-1 s_n-1, где p — некоторое натуральное число (позже будет сказано, какое именно), а s_i — код i-ого символа строки s (почти во всех современных языках он записывается s[i] ).

Хеши обладают тем свойством, что у одинаковых строк хеши обязательно равны. Поэтому основная операция, которую позволяют выполнять хеши — быстрое сравнение двух подстрок на равенство. Конечно, чтобы сравнить 2 строки, мы можем написать подобную функцию (будем считать, что длины строк s и t совпадают и равны n):

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

Сравнение строк с помощью хешей

Теперь посмотрим, как справляются с этой задачей хеши. Так как хеш — это всего лишь число, для их сравнения нам потребуется O(1) времени. Правда, для того, чтобы посчитать хеш одной подстроки наивным способом, требуется O(n) времени. Поэтому потребуется немного повозиться с математическими формулами и научиться находить за O(n) хеши сразу всех подстрок. Давайте сравним подстроки s_L..R и t_X..Y (одинаковой длины). Пользуясь определением хеша, мы можем записать:

Проведем небольшие преобразования в левой части (в правой части все будет происходить аналогично). Запишем хеш подстроки s_0..R, он нам понадобится:

Разобьем это выражение на две части…

… и вынесем из второй скобки множитель p L :

Выражение в первой скобке есть не что иное, как хеш подстроки s_0..L-1, а во второй — хеш нужной нам подстроки s_L..R. Итак, мы получили, что:

Отсюда вытекает следующая формула для hash(s_L..R):

Аналогично, для второй нашей подстроки будет выполнено равенство hash(t_X..Y) = (1 / p X )(hash(t_0..Y) — hash(t_0..X-1)).

Внимательно глядя на эти формулы, можно заметить, что для вычисления хеша любой подстроки нам необходимо знать лишь хеши префиксов этой строки s_0..0, s_0..1, . s_0..n-2, s_0..n-1. А, так как хеш каждого следующего префикса выражается через хеш предыдущего, их несложно посчитать линейным проходом по строке. Все сразу за O(n) времени. Степени числа p тоже надо заранее предпросчитать и сохранить в массиве.

• Замечание первое: L (или X) может оказаться равным нулю, и при вычислении hs[L - 1] произойдет выход за границы массива. Однако если L равно нулю, то интересующий нас хеш подстроки s_L..R хранится в точности в hs[R] . Поэтому правильнее вместо hs[L - 1] писать так:
  .
• Замечание второе: даже тип long содержит всего 64 бита (я использую Java), а наши строки могут быть длиной в несколько тысяч, и при вычислении хешей неизбежно произойдет переполнение. Эту проблему решить проще всего: надо закрыть на нее глаза. Ну, или почти закрыть: хеши у нас будут считаться, по сути, по модулю 2 64 (и поэтому не потребуется выполнять операции взятия остатка от деления — красота!). Число p для их подсчета должно быть, во-первых, больше кода самого большого символа в строках, а во-вторых, взаимно простым с модулем (в нашем случае — с 2 64 , т.е. оно должно быть нечетным). Почему так, я здесь рассказывать не буду — об этом можно почитать в книжках по алгебре. Конечно, неизбежно появляется вероятность коллизии, но она крайне мала, поэтому при решении олимпиадных задач можно ей просто пренебречь.
• Замечание третье: так как все операции мы теперь выполняем по модулю, деление для нас недоступно (точнее, доступно, но писать это довольно неэффективно). Поэтому от него надо избавляться. Делается это довольно просто, способом, который в школе называют «пропорцией»: выражение приводится к общему знаменателю, и вместо деления используется умножение:
  

Задачи, решаемые с помощью хешей

1. Сравнение подстрок

Первое, и главное, применение, как уже было сказано, это быстрое сравнение двух подстрок — на нем основываются все остальные алгоритмы с хешами. Код в прошлом разделе довольно громоздкий, поэтому я напишу более удобный код, который будет использоваться в дальнейшем.
Следующая функция вычисляет хеш подстроки s_L..R, умноженный на p L :

Теперь сравнение двух подстрок мы выполняем следующей строчкой:

Умножение на степени числа p можно назвать «приведением к одной степени». Первый хеш был умножен на p L , а второй — на p X — значит, чтобы сравнение происходило корректно, их надо домножить на недостающий множитель.
Примечание: имеет смысл сначала проверить, совпадают ли длины подстрок. Если нет, то строки в принципе не могут быть равны, и тогда можно не проверять вышезаписанное условие.

2. Поиск подстроки в строке за O(n + m)

Хеши позволяют искать подстроку в строке за асимптотически минимальное время. Это делает так называемый алгоритм Рабина-Карпа.
Пусть есть строка s длины n, в которой мы хотим найти все вхождения строки t длины m. Найдем хеш строки t (всей строки целиком) и хеши всех префиксов строки s, а затем будем двигаться по строке s окном длины m, сравнивая подстроки s_i..i+m-1.
Код:

3. Нахождение z-функции за O(n log n)

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

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

Идея следующая: для каждого i = 0, 1, . n-1 будем искать z_i бинарным поиском, т.е. на каждой итерации сокращая интервал возможных значений вдвое. Это корректно, потому что равенство s_0..k-1 = s_i..i+k-1 обязательно выполняется для всех k, меньших z_i, и обязательно не выполняется для больших k.

4. Поиск лексикографически минимального циклического сдвига строки за O(n log n).

Существует алгоритм Дюваля, который позволяет решать эту задачу за O(n), однако я знаю некоторых довольно сильных олимпиадных программистов, которые так и не разобрались в нем. Пока они будут в нем разбираться, мы снова применим хеши.

Алгоритм следующий. Сначала примем саму строку s за лучший (лексикографически минимальный) ответ. Затем для каждого циклического сдвига с помощью бинарного поиска найдем длину максимального общего префикса этого сдвига и текущего лучшего ответа. После этого достаточно сравнить следующие за этим префиксом символы и, если надо, обновить ответ.
Еще заметим, что для удобства здесь рекомендуется приписать строку s к самой себе — не придется делать операции взятия по модулю при обращениям к символам строки s. Будем считать, что это уже сделано.

Примечание: по сути, внутри цикла for написан компаратор, сравнивающий лексикографически два циклических сдвига. Используя его, можно за O(n log 2 n) отсортировать все циклические сдвиги.

5. Поиск всех палиндромов в строке за O(n log n).

Опять же, существует решение этой задачи за O(n). И опять мы будем решать ее с помощью хешей.

Подстрока s_L..R называется палиндромом, если s_L = s_R, s_L+1 = s_R-1, и т.д. Если выражаться русским языком, то это означает, что она читается одинаково как слева направо, так и справа налево.

Возможно, вы уже знаете или догадались, при чем тут хеши. Помимо массива h[] , содержащего хеши для подстрок s_0..0, s_0..1, . s_0..n-2, s_0..n-1, посчитаем второй массив rh[] (для «перевернутой» строки), который будем обходить справа налево. Он будет содержать соответственно хеши s_0..n-1, s_1..n-1, . s_n-2..n-1, s_n-1..n-1:

Должно уже быть понятно, как за O(1) определять, является ли строка палиндромом. Я напишу функцию getRevHash(), аналогичную getHash(), а потом приведу необходимое условие сравнения. Вы можете самостоятельно убедиться в правильности этого выражения, проделав математические выкладки, подобные тем, что приводились в начале статьи.

Теперь рассмотрим позицию i в строке. Пусть существует палиндром нечетной длины d с центром в позиции i (в случае четной длины — с центром между позициями i-1 и i). Если обрезать с его краев по одному символу, он останется палиндромом. И так можно продолжать, пока его длина не станет равной нулю.
Таким образом, нам достаточно для каждой позиции хранить 2 значения: сколько существует палиндромов нечетной длины с центром в позиции i, и сколько существует палиндромов четной длины с центром между позициями i-1 и i. Обратите внимание, что эти 2 значения абсолютно независимы друг от друга, и обрабатывать их надо отдельно.

Применим, как и ранее, бинарный поиск:

Теперь можно, к примеру, найти общее количество всех палиндромов в строке, или длину максимального палиндрома. Длина максимального нечетного палиндрома с центром в позиции i считается как 2 * oddCount[i] - 1 , а максимального четного палиндрома — 2 * evenCount[i] .
Еще раз напомню, что нужно быть внимательнее с палиндромами четной и нечетной длины — как правило, их надо обрабатывать независимо друг от друга.

Хеши в матрицах

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

Теперь вместо числа p и массива pow у нас будут два различных числа p, q и два массива pow1 , pow2 : по одному числу и по одному массиву в каждом направлении: по вертикали и горизонтали.

Хешем матрицы a_{0..n-1, 0..m-1} будем называть сумму по всем i = 0, . n-1, j = 0. m-1 величин p i q j a_ij.

Теперь научимся считать хеши подматриц, содержащих левый верхний элемент a₀₀. Очевидно, что hash(a_{0..0, 0..0}) = a₀₀. Почти так же очевидно, что для всех j = 1. m-1 hash(a_{0..0, 0..j}) = hash(a_{0..0, 0..j-1}) + q j a_0j, для всех i = 1. n-1 hash(a_{0..i, 0..0}) = hash(a_{0..i-1, 0..0}) + p i a_i0. Это напрямую вытекает из одномерного случая.

Как посчитать хеш подматрицы a_{0..i, 0..j}? Можно догадаться, что hash(a_{0..i, 0..j}) = hash(a_{0..i-1, 0..j}) + hash(a_{0..i, 0..j-1}) — hash(a_{0..i-1, 0..j-1}) + p i q j a_ij. Эту формулу можно получить из следующих соображений: сложим все слагаемые (хеш, напомню, это сумма нескольких слагаемых), составляющие хеш подматриц a_{0..i-1, 0..j} и a_{0..i, 0..j-1}. При этом мы два раза учли слагаемые, составляющие подматрицу a_{0..i-1, 0..j-1}, так что вычтем их, чтобы они учитывались один раз. Теперь не хватает только элемента a_ij, умноженного на соответствующие степени p и q.

Примерно из тех же соображений, что и в первой части статьи (вы уже заметили причастность формулы включений-исключений?) строится функция для вычисления хеша произвольной подматрицы a_{x1..x2, y1..y2}:

Эта функция возвращает хеш подматрицы a_{x1..x2, y1..y2}, умноженный на величину p x1 q y1 .

А сравнение двух подматриц a_{ax1..ax2, ay1..ay2} и a_{bx1..bx2, by1..by2} выполняется с помощью следующего выражения:

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

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

• Быстро считается — за линейное от размера объекта время;
• Имеет не очень большие значения — влезающие в 64 бита;
• «Детерминированно-случайная» — если хэш может принимать \(n\) различных значений, то вероятность того, что хэши от двух случайных объектов совпадут, равна примерно \(\frac\) .

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

Для некоторых задач удобнее работать с хэшами, чем с самими объектами. Пусть даны \(n\) строк длины \(m\) , и нас просят \(q\) раз проверять произвольные две на равенство. Вместо наивной проверки за \(O(q \cdot n \cdot m)\) , мы можем посчитать хэши всех строк, сохранить, и во время ответа на запрос сравнивать два числа, а не две строки.

Применения в реальной жизни

• Чек-суммы. Простой и быстрый способ проверить целостность большого передаваемого файла — посчитать хэш-функцию на стороне отправителя и на стороне получателя и сравнить.
• Хэш-таблица. Класс unordered_set из STL можно реализовать так: заведём \(n\) изначально пустых односвязных списков. Возьмем какую-нибудь хэш-функцию \(f\) с областью значений \([0, n)\) . При обработке .insert(x) мы будем добавлять элемент \(x\) в \(f(x)\) -тый список. При ответе на .find(x) мы будем проверять, лежит ли \(x\) -тый элемент в \(f(x)\) -том списке. Благодаря «равномерности» хэш-функции, после \(k\) добавлений ожидаемое количество сравнений будет равно \(\frac\) = \(O(1)\) при правильном выборе \(n\) .
• Мемоизация. В динамическом программировании нам иногда надо работать с состояниями, которые непонятно как кодировать, чтобы «разгладить» в массив. Пример: шахматные позиции. В таком случае нужно писать динамику рекурсивно и хранить подсчитанные значения в хэш-таблице, а для идентификации состояния использовать его хэш.
• Проверка на изоморфизм. Если нам нужно проверить, что какие-нибудь сложные структуры (например, деревья) совпадают, то мы можем придумать для них хэш-функцию и сравнивать их хэши аналогично примеру со строками.
• Криптография. Правильнее и безопаснее хранить хэши паролей в базе данных вместо самих паролей — хэш-функцию нельзя однозначно восстановить.
• Поиск в многомерных пространствах. Детерминированный поиск ближайшей точки среди \(m\) точек в \(n\) -мерном пространстве быстро не решается. Однако можно придумать хэш-функцию, присваивающую лежащим рядом элементам одинаковые хэши, и делать поиск только среди элементов с тем же хэшом, что у запроса.

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

Сегодня же мы остановимся на строках.

Полиномиальное хэширование

Лайфхак: пока вы не выучили все детерминированные строковые алгоритмы, научитесь пользоваться хэшами.

Будем считать, что строка — это последовательность чисел от \(1\) до \(m\) (размер алфавита). В C++ char это на самом деле тоже число, поэтому можно вычитать из символов минимальный код и кастовать в число: int x = (int) (c - 'a' + 1) .

Определим прямой полиномиальный хэш строки как значение следующего многочлена:

\[ h_f = (s_0 + s_1 k + s_2 k^2 + \ldots + s_n k^n) \mod p \]

Здесь \(k\) — произвольное число больше размера алфавита, а \(p\) — достаточно большой модуль, вообще говоря, не обязательно простой.

Его можно посчитать за линейное время, поддерживая переменную, равную нужной в данный момент степени \(k\) :

Можем ещё определить обратный полиномиальный хэш:

\[ h_b = (s_0 k^n + s_1 k^ + \ldots + s_n) \mod p \]

Его преимущество в том, что можно написать на одну строчку кода меньше:

Автору проще думать об обычных многочленах, поэтому он будет везде использовать прямой полиномиальный хэш и обозначать его просто буквой \(h\) .

Зачем это нужно?

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

Например, если нужно посчитать хэш от конкатенации строк \(a\) и \(b\) (т. е. \(b\) приписали в конец строки \(a\) ), то можно просто хэш \(b\) домножить на \(k^<|a|>\) и сложить с хэшом \(a\) :

Удалить префикс строки можно так:

А суффикс — ещё проще:

В задачах нам часто понадобится домножать \(k\) в какой-то степени, поэтому имеет смысл предпосчитать все нужные степени и сохранить в массиве:

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

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

Деление по модулю возможно делать только при некоторых k и mod (а именно — при взаимно простых). В любом случае, писать его долго, и мы это делать не хотим.

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

Теперь мы можем просто вызывать эту функцию от двух отрезков и сравнивать числовое значение, отвечая на запрос за \(O(1)\) .

Упражнение. Напишите то же самое, но используя обратный полиномиальный хэш — этот способ тоже имеет право на существование, и местами он даже проще. Обратный хэш подстроки принято считать и использовать в стандартном виде из определения, поскольку там нет необходимости в делении.

Лайфхак. Если взять обратный полиномиальный хэш короткой строки на небольшом алфавите с \(k=10\) , то числовое значение хэша строки будет наглядно соотноситься с самой строкой:

Этим удобно пользоваться при дебаге.

Примеры задач

Количество разных подстрок. Посчитаем хэши от всех подстрок за \(O(n^2)\) и добавим их все в std::set . Чтобы получить ответ, просто вызовем set.size() .

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

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

Палиндромность подстроки. Можно посчитать два массива — обратные хэши и прямые. Проверка на палиндром будет заключаться в сравнении значений hash_substring() на первом массиве и на втором.

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

Хранение строк в декартовом дереве

Если для вас всё вышеперечисленное тривиально: можно делать много клёвых вещей, если «оборачивать» строки в декартово дерево. В вершине дерева можно хранить символ, а также хэш подстроки, соответствующей её поддереву. Чтобы поддерживать хэш, нужно просто добавить в upd() пересчёт хэша от конкатенации трёх строк — левого сына, своего собственного символа и правого сына.

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

Если нам не нужно обрабатывать запросы вставки и удаления символов, а, например, только изменения, то можно использовать и дерево отрезков вместо декартова.

Вероятность ошибки и почему это всё вообще работает

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

Событие, когда два хэша совпали, а не должны, называется коллизией. Пусть мы решаем задачу определения количества различных подстрок — мы добавляем в set \(O(n^2)\) различных случайных значений в промежутке \([0, m)\) . Понятно, что если произойдет коллизия, то мы какую-то строку не учтем и получим WA. Насколько большим следует делать \(m\) , чтобы не бояться такого?

Выбор констант

Практическое правило: если вам нужно хранить \(n\) различных хэшей, то безопасный модуль — это число порядка \(10 \cdot n^2\) . Обоснование — см. парадокс дней рождений.

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

Можно также брать модуль \(2^\) . У него есть несколько преимуществ:

• Он большой — второй модуль точно не понадобится.
• С ним ни о каких переполнениях заботиться не нужно — если все хранить в unsigned long long , процессор сам автоматически сделает эти взятия остатков при переполнении.
• С ним хэширование будет быстрее — раз переполнение происходит на уровне процессора, можно не выполнять долгую операцию % .

Всё с этим модулем было прекрасно, пока не придумали тест против него. Однако, его добавляют далеко не на все контесты — имейте это в виду.

В выборе же \(k\) ограничения не такие серьезные:

• Она должна быть чуть больше размера словаря — иначе можно изменить две соседние буквы и получить коллизию.
• Она должна быть взаимно проста с модулем — иначе в какой-то момент всё может занулиться.

Главное — чтобы значения \(k\) и модуля не знал человек, который генерирует тесты.

Парадокс дней рождений

В группе, состоящей из 23 или более человек, вероятность совпадения дней рождения хотя бы у двух людей превышает 50%.

Более общее утверждение: в мультимножество нужно добавить \(\Theta(\sqrt)\) случайных чисел от 1 до n, чтобы какие-то два совпали.

Первое доказательство (для любителей матана). Пусть \(f(n, d)\) это вероятность того, что в группе из \(n\) человек ни у кого не совпали дни рождения. Будем считать, что дни рождения распределены независимо и равномерно в промежутке от \(1\) до \(d\) .

\[ f(n, d) = (1-\frac) \times (1-\frac) \times . \times (1-\frac) \]

Попытаемся оценить \(f\) :

Из последнего выражения более-менее понятно, что вероятность \(\frac\) достигается при \(n \approx \sqrt\) и в этой точке изменяется очень быстро.

Второе доказательство (для любителей теорвера). Введем \(\frac\) индикаторов — по одному для каждой пары людей \((i, j)\) — каждый будет равен единице, если дни рождения совпали. Ожидание и вероятность каждого индикатора равна \(\frac\) .

Обозначим за \(X\) число совпавших дней рождений. Его ожидание равно сумме ожиданий этих индикаторов, то есть \(\frac \cdot \frac\) .

Отсюда понятно, что если \(d = \Theta(n^2)\) , то ожидание равно константе, а если \(d\) асимптотически больше или меньше, то \(X\) стремится нулю или бесконечности соответственно.

Примечание: формально, из этого явно не следует, что вероятности тоже стремятся к 0 и 1.

Бонус: «мета-задача»

Дана произвольная строка, по которой известным только авторам задачи способом генерируется ответ yes/no. В задаче 100 тестов. У вас есть 20 попыток отослать решение. В качестве фидбэка вам доступны вердикты на каждом тесте. Вердиктов всего два: OK (ответ совпал) и WA. Попытки поделить на ноль, выделить терабайт памяти и подобное тоже считаются как WA.

Хеширование

Выше мы вывели ряд списковых структур, позволяющих программе-клиенту осуществлять поиск и выборку данных. В каждой такой структуре метод Find выполняет обход списка и ищет элемент данных, совпадающий с ключом. При этом эффективность поиска зависит от структуры списка. В случае последовательного списка метод Find гарантированно просматривает O(n) элементов, в то время как в случае бинарных поисковых деревьев и при бинарном поиске обеспечивается более высокая эффективность O(log 2 n).

В идеале нам хотелось бы выбирать данные за время O(1). В этом случае число необходимых сравнений не зависит от количества элементов данных. Выборка элемента осуществляется за время O(1) при использовании в качестве индекса в массиве некоторого ключа. Например, блюда из меню в закусочной в целях упрощения бухгалтерского учета обозначаются номерами. Какой-нибудь деликатес типа «бастурма, маринованная в водке» в базе данных обозначается просто №2. Владельцу закусочной остается лишь сопоставить ключ 2 с записью в списке (рисунок 25).

Мы знаем и другие примеры. Файл клиентов пункта проката видеокассет содержит семизначные номера телефонов. Номер телефона используется в качестве ключа для доступа к конкретной записи файла клиентов.

Ключи не обязательно должны быть числовыми. Например, формируемая компилятором таблица символов (symbol table) содержит все используемые в программе идентификаторы вместе с сопутствующей каждому из них информацией. Ключом для доступа к конкретной записи является сам идентификатор.

Ключи и хеш-функция

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

В большинстве приложений ключ обеспечивает косвенную ссылку на данные. Ключ отображается во множество целых чисел посредством хеш-функции (hash function). Полученное в результате значение затем используется для доступа к данным. Давайте исследуем эту идею. Предположим, есть множество записей с целочисленными ключами. Хеш-функция HF отображает ключ в целочисленный индекс из диапазона 0. n-1. С хеш-функцией связана так называемая хеш-таблица (hash table), ячейки которой пронумерованы от 0 до n-1 и хранят сами данные или ссылки на данные.

Предположим, Key – положительное целое, а HF(Key) – значение младшей цифры числа Key. Тогда диапазон индексов равен 0-9. Например, если Key = 49, HF(Key) = HF(49) = 9. Эта хеш-функция в качестве возвращаемого значение использует остаток от деления на 10.

Часто отображение, осуществляемое хеш-функцией, является отображением «многие к одному» и приводит к коллизиям (collisions). Например, выше мы видим HF(49) = HF(29) = 9. При возникновении коллизии два или более ключа ассоциируются с одной и той же ячейкой хеш-таблицы. Поскольку два ключа не могут занимать одну и ту же ячейку в таблице, мы должны разработать стратегию разрешения коллизий.

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

Хеш-функции

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

Наиболее часто используется метод деления (division method), требующий двух шагов. Сперва ключ должен быть преобразован в целое число, а затем полученное значение вписывается в диапазон 0. n-1 с помощью оператора получения остатка. На практике метод деления используется в большинстве приложений, работающих с хешированием.

Предположим, что ключ – пятизначное число. Хеш-функция извлекает две младшие цифры. Например, если это число равно 56389, то HF(56389) = 89. Две младшие цифры являются остатком от деления на 100.

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

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

Эта хеш-функция приводит к коллизии при одинаковых первом и последнем символах строки. Например, строки «start» и «slant» будут отображаться в индекс 29. Так же ведет себя хеш-функция, суммирующая все символы строки.

Строки «bad» и «dab» преобразуются в один и тот же индекс. Лучшие результаты дает хеш-функция, производящая перемешивание битов в символах.

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

Другие методы хеширования

Метод середины квадрата (midsquare technique) предусматривает преобразование ключа в целое число, возведение его в квадрат и возвращение в качестве значения функции последовательности битов, извлеченных из середины полученного числа. Предположим, что ключ есть целое 32-битное число. Тогда следующая хеш-функция извлекает средние 10 бит возведенного в квадрат ключа.

При мультипликативном методе (multiplicative method) используется случайное действительное число f в диапазоне от 0<f<1. Дробная часть произведения f * key лежит в диапазоне от 0 до 1. Если это произведение умножить на n (размер хеш-таблицы), то целая часть полученного произведения даст значение хеш-функции в диапазоне 0. n-1.

Разрешение коллизий

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

Открытая адресация с линейным перебором

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

Проиллюстрируем линейный перебор на примере семи записей.

Предположим, что данные имеют тип DataRecord и хранятся в 11-элементной таблице.

В качестве хеш-функции HF используется остаток от деления на 11, принимающий значения в диапазоне 0-10.

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

Хеширование первых пяти ключей дает пять различных индексов, по которым эти ключи запоминаются в таблице. Например, HF() = 10, и этот элемент попадает в Table[10]. Первая коллизия возникает между ключами 89 и 45, так как оба они отображаются в индекс 1.

Элемент данных идет первым в списке и занимает позицию Table[1]. При попытке записать оказывается, что место Table[1] уже занято. Тогда начинается последовательный перебор ячеек таблицы с целью нахождения свободного места. В данном случае это Table[2]. На ключе 76 эффективность алгоритма сильно падает. Этот ключ хешируется в индекс 10 – место, уже занятое. В процессе перебора осуществляется просмотр еще пяти ячеек, прежде чем будет найдено свободное место в Table[4]. Общее число проб для размещения в таблице всех элементов списка равно 13, т.е. в среднем 1,9 проб на элемент.

Метод цепочек

При другом подходе к хешированию таблица рассматривается как массив связанных списков или деревьев. Каждый такой список называется блоком (bucket) и содержит записи, отображаемые хеш-функцией в один и тот же табличный адрес. Эта стратегия разрешения коллизий называется методом цепочек (chaining with separate lists) .

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

Проиллюстрируем метод цепочек на семи записях типа DataRecord и хеш-функции HF.

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

Заметьте, что если считать пробой вставку нового узла, то их общее число при вставке семи элементов равно 9, т.е. в среднем 1,3 пробы на элемент данных.

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

Класс HashTable

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

Мы также рассмотрим класс HashTableIterator, облегчающий обработку данных в хеш-таблице. Объект типа HashTableIterator находит важное применение при сортировке и доступе к данным.

Но сначала приведем листинги классов Array и LinkedList, используемых в классе HashTable. Особо пояснять мы их не будем, поскольку их обсуждение не входит в задачи этой статьи.

Читайте также:

  
• Установить заземление в частном доме донэлектромонтаж ру
  
• Поверните руль и нажмите старт показывает компьютер
  
• Изменить время создания файла powershell
  
• Как подключить трекер к компьютеру
  
• Невозможно открыть файл install log