Хеш-функции

Что такое отображение

О массивах мы говорили в самом начале курса, и сейчас они нам очень пригодятся. Напомним, что в интерфейсе массива есть две основные операции:

• get(index: int) -> value — получить значение value из ячейки с индексом index;
• set(index: int, value: ValueType) — записать значение value в ячейку с индексом index.

Каждая из этих операций выполняется за $O(1)$. Это очень быстро! Однако у массивов есть одно серьёзное ограничение: хотя в ячейках массива можно расположить объекты любого типа, индексы этих ячеек могут быть исключительно целыми числами.

Но в программе часто возникает необходимость получить объект не по его порядковому номеру, то есть индексу ячейки в массиве, а по какому-то другому признаку, например по названию. Или, как говорят программисты, получить значение (англ. value) по ключу (англ. key).

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

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

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

Такое сопоставление, когда каждому объекту первого множества (множество городов) соответствует ровно один объект второго множества (множество стран), называется «отображением» (англ. map).

На самом деле отображение — это другое название математического термина «функция», или «функциональная зависимость». Чаще всего функции отображают числа (расположенные на оси X) в другие числа (расположенные на оси Y). Для каждого числа из области определения функции можно выписать другое число — значение функции в этой точке.

Массивы — это тоже частный случай отображения: они умеют сопоставлять целому числу любое значение. Например, массив ["яблоко", "груша", "яблоко"] сопоставляет числам 0 и 2 строку яблоко, а числу 1 — строку груша.

Чтобы работать с отображениями, нам требуется похожая на массив структура данных, которая умеет получать и сохранять значения:

• get(key: KeyType) -> value — получить значение value по ключу key;
• set(key: KeyType, value: ValueType) — записать значение value по ключу key.

Но вместо целочисленного индекса она должна допускать ключ произвольного типа.

Интерфейс, описывающий две этих операции, называют Map. А любую структуру, которая реализует этот интерфейс, называют «ассоциативным массивом» (англ. associative array).

Ассоциативные массивы

В большинстве языков программирования ассоциативные массивы встроены в язык.

Чаще всего их называют так же, как интерфейс — Map, «отображение», или используют производные от слова «хеш-таблица»: Hash, HashMap, HashTable и даже просто Table. Эти названия подчёркивают, каким именно способом был реализован интерфейс отображения. Встречаются и другие наименования. Например, в Python ассоциативные массивы называют «словарями» (англ. dictionary).

Есть два популярных способа реализовать или, как говорят программисты, имплементировать отображение. Первый способ, хеш-таблицы, мы рассмотрим в этом спринте. Другой способ основан на деревьях поиска. В некоторых языках встречаются сразу обе реализации. Например, в Java отображения имплементированы двумя отдельными классами: HashMap и TreeMap. В языке C++ им соответствуют классы std::unordered_map и std::map.

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

Наивная реализация ассоциативного массива

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

Но сначала давайте рассмотрим простейший способ реализации ассоциативного массива. Заведём обыкновенный массив или список, в котором записаны пары (key, value).

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

структура Map:
    pairs = []

    метод get(key):
        for pair in pairs:
            if pair.key == key:  # пара с указанным ключом найдена
                return pair.value
        return None

    метод set(key, value):
        for pair in pairs:
            if pair.key == key: # пара с указанным ключом найдена
                # обновить значение в найденной паре
                pair.value = value
                return
        # пара с заданным ключом не найдена
        добавить пару (key, value) в pairs

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

Что такое хеш-таблица и хеш-функция

Хеш-таблица (англ. hash table) — это один из способов реализовать ассоциативный массив, при котором все данные записываются и хранятся в виде пар (key, value) в ячейках обыкновенного массива. Эти ячейки называются корзинами (англ. bucket). Как и в любом массиве, ячейки-корзины пронумерованы. Индекс, или номер корзины, в которую отправляются данные, зависит от ключа. Можно завести специальную функцию, которая по ключу будет вычислять номер корзины.

Как работают хеш-функция и хеш-таблица

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

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

Хеш-функция (англ. hash function) — функция, которая обеспечивает преобразование входных данных в целое число. Для разных типов объектов применяются разные хеш-функции. Результат вычисления хеш-функции называется «хешем» или «хеш-суммой» (англ. hash, hash code или digest).

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

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

Другой пример хеш-функции: мы можем возвращать сумму всех номеров букв, входящих в название фрукта. Тогда для «яблоко» значение функции будет 92, для «груша» — 70, а для «слива» — 46.

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

Отображение из ключа в значение разделилось на три независимых отображения. 1. Сначала хеш-функция отображает ключ в число, то есть в хеш. 2. Затем этот хеш преобразуется в индекс корзины. 3. И, наконец, из массива корзин мы находим нужную корзину по её индексу. В ней-то и хранится значение, которое возвращается пользователю.

Что такое коллизии

Ситуация, когда хеш-функция для разных входных данных выдаёт одно и то же значение, называется «коллизией».

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

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

Выбор размера хеш-таблицы и вычисление номера корзины

Вычисление номера корзины методом деления

Самый простой способ получить номер корзины $\mathrm{bucket}(k)$ для целого ключа $k$ — взять остаток от деления ключа $k$ на число корзин $M$. Остаток от деления обозначается $k \bmod M$ и произносится «$k$ по модулю $M$». В языках программирования остаток от деления вычисляется оператором %.

Любое целое число $k$ может быть представлено в форме $k = j\cdot M + r$, где все числа — целые, а $r \in[0,M)$. Число $r$ и называется остатком от деления.

Такое определение нам удобно, поскольку остатки от деления целого числа на $M$ могут принимать целые значения в диапазоне от $0$ до $(M-1)$, и это ровно те же числа, которые могут служить номерами корзин в хеш-таблице длины $M$.

Будьте аккуратны! В разных языках программирования остаток от деления по-разному работает с отрицательными числами (см. подробности). Не всегда это происходит так же, как математическая операция взятия по модулю. Например, выражение $-13 % 5$ в одних языках даст $2$, в других $-3$. Если не учесть эти нюансы, можно получить отрицательный номер корзины.

Выбор числа корзин

В качестве $M$ нужно брать простое число. То есть такое, которое делится без остатка только на себя и на 1.

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

Чем больше делителей у $M$, тем чаще такие закономерности будут приводить к коллизиям. И наоборот, простое значение $M$ уменьшает число коллизий, ведь у простого числа всего два делителя.

Для любого числа корзин можно придумать такую киллер-последовательность из ключей, из-за которой случится много коллизий. Но если делителей у M много, велик шанс наткнуться на такую последовательность случайно. А когда M — большое простое число, это маловероятно.

Вычисление номера корзины методом умножения

Ещё один популярный способ, применяемый для вычисления номера ячейки — метод умножения. Для вычисления нам снова потребуется целое число. На этот раз мы его сразу обозначим буквой $h$, чтобы подчеркнуть, что это хеш ключа. Пусть количество корзин равно $M$. Также зададим константу $\alpha \in (0,1)$.

Тогда $\mathrm{bucket}(h) = \left [ M \cdot \left { h \cdot \alpha \right } \right ]$ , где $\left [ x \right ]$ — обозначает целую часть числа $x$, $\left { x \right }$ — его дробную часть.

Алгоритм построения хеш-функции с использованием метода умножения:

• Домножаем хеш ключа $h$ на выбранную константу $\alpha$.
• Берём от результата дробную часть. Получается некоторое значение из диапазона $[0,1)$. Важно, что эти значения для разных ключей будут равномерно рассеяны.
• Домножаем полученное значение на размер таблицы $M$. Числа получаются распределёнными в диапазоне $[0, M)$
• Берём от результата целую часть. С равными вероятностями получаются числа от $0$ до $(M−1)$ — это и будут номера корзин. Корзины будут заполняться равномерно, это поможет нам уменьшить число коллизий.

Дональд Кнут провёл исследования и выяснил, что хеш-функция получается хорошей, если в качестве $\alpha$ брать число, обратное золотому сечению. $$ \displaystyle \alpha = \phi^{-1} = \left ( \frac{\sqrt 5 -1}{2} \right ) = 0.6180339887... $$

Свойства хеш-функций

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

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

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

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

• Детерминизм. Для одного и того же ключа функция всегда должна возвращать одинаковое значение. Если в функции будет браться случайное значение, то повторное её применение может выдать новый индекс ячейки, а значит, мы не сможем получить искомые данные из хеш-таблицы. Хорошая функция при повторном вызове выполняет те же действия, что и при первичном. Например, взятие числа по модулю другого числа — детерминированная функция, так как результат всегда будет одинаковым.
• Эффективность. Хеш-функция должна вычисляться достаточно быстро. Сложность операции поиска в хеш-таблице складывается из сложности вычисления хеша и сложности поиска данных по хешу. Важно, чтобы оба процесса выполнялись эффективно.
• Ограниченность. Результат вычисления функции должен принадлежать определённому диапазону, который соответствует размеру хеш-таблицы. Поэтому обычно сначала вычисляют хеш-функцию, которая возвращает произвольное число. А потом этот результат берут по модулю $M$ (размер хеш-таблицы). Таким образом, любой ключ будет находиться в интервале от $0$ до $M-1$, а значит, мы никогда не обратимся к индексу, который не соответствует ни одной из корзин.
• Равномерность. Данные должны быть распределены по хеш-таблице равномерно. То есть каждое выходное значение — равновероятно. Равновероятно — это значит, что если мы запустим функцию для каждого элемента из большого списка разных объектов, то в результате получим примерно равное число ответов функции для каждого значения от $0$ до $M-1$. В противном случае в какие-то ячейки мы будем пытаться записать значение чаще, чем в другие. И это замедлит обращение к хеш-таблице. Пример неравномерной функции — получение среднесуточной температуры по городу и дате, так как большую часть времени температура держится на одном и том же уровне, а аномальные морозы или жара случаются редко.

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

• Лавинность. При незначительном изменении входных данных выходное значение должно меняться значительно. При хешировании паролей нелавинная функция проще взламывается. Если злоумышленник знает, что $h(aa) = 22$, а $h(bb) = 33$, то он может предположить такой $password$, что $h(password) = 44$. Перебрав небольшое число вариантов, злоумышленник сможет подобрать пароль по его хешу.
• Необратимость. Невозможно восстановить ключ по значению функции. Например, при регистрации на сайте пользователь вводит свой пароль, к которому применяется хеш-функция. Полученный хеш записывается в базу данных — в ячейку, соответствующую данному пользователю. Каждый раз, когда пользователь вводит пароль, к нему применяется та же функция. Так как алгоритм получения хеша от строки пароля в обоих случаях одинаковый, новый хеш совпадёт с записью в базе данных, если пользователь ввёл свой исходный пароль. Даже если злоумышленник получит доступ к данным в базе, у него не должно быть возможности восстановить пароль.

Построение хеш-функций для строк

Теперь давайте рассмотрим, как вычисляются хеш-функций для строк. Для этого есть специальный алгоритм, который называется «полиномиальным хешированием» (от слова «полином» — многочлен). Хеш строки $s$ вычисляется по формуле: $$ h(s)=\left(s_{1} q^{n-1}+s_{2} q^{n-2}+\cdots+s_{n-1} q+s_{n}\right) \bmod R $$ Где $s_i$ — код $i$-го символа (например, ASCII-код), $n$ — длина строки, а $R$ и $q$ — выбранные константы.

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

Выбор числа $R$ зависит от типа переменной, в которой хранятся хеши. Например, для беззнаковых 4-байтовых целых чисел удобно выбрать $R=2^{32}$. Для 8-байтовых чисел можно взять $R=2^{64}$.

Если строки длинные, выбор величины $q$ не так важен — в сумму будут входить значения $q$ в достаточно больших степенях. Но ради универсальности лучше и в этом случае взять большое число. Число $q$ должно быть не только большим, но и простым.

Помните, мы говорили, что индекс корзины вычисляется взятием остатка от деления значения хеша на число корзин? Чем меньше общих делителей у $q$, $M$ и $R$, тем реже будут возникать коллизии. В качестве $R$ мы уже договорились использовать $2^{32}$, поэтому любое нечётное число не будет иметь с $R$ общих делителей.

Число $M$ будет меняться в зависимости от размера хеш-таблицы. При вычислении хеш-функции этот размер ещё не известен. Из-за этого мы не можем гарантировать, что параметр вычисления хеш-функции $q$ и число корзин $M$ будут взаимно простыми. Но выбор большого простого числа в качестве $q$ делает вероятность наличия нетривиальных общих делителей очень небольшой, ведь у простого числа нет делителей, кроме самого этого числа и единицы. Как мы говорили, $M$ обычно тоже делают простым, поэтому общие делители могут получиться, только когда $M=q$.

Поисковый индекс

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

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

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

Отображение, которое каждому объекту ставит в соответствие его расположение, называют «поисковым индексом».

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

Этот способ позволит нам сразу получить нужную позицию — это, конечно, хорошо. Но он очень неэффективный. Ведь подстрок в тексте может быть столько, сколько существует способов выбрать две границы: $N\cdot(N-1)/ 2$, где $N$ — длина текста. Значит, в хеш-таблицу нужно добавить $O(N^2)$ пар (key, value). Поскольку ключами являются подстроки, каждая такая пара займёт в среднем $O(N)$ памяти. Получается, что всего при такой реализации придётся потратить $O(N^3)$ памяти.

Поэтому с большими текстами такая реализация не сработает.

...