Хеш-функции

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

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

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

Понятие отображения

В интерфейсе массива, рассмотренном в главе про структуры данных, имеются две основные операции:

  • 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).

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

class NaiveMap:
    def __init__(self):
        self.pairs = []

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

    def set(self, key, value):
        for i, (stored_key, _) in enumerate(self.pairs):
            if stored_key == key:  # пара с указанным ключом найдена
                # обновить значение в найденной паре
                self.pairs[i] = (key, value)
                return
        # пара с заданным ключом не найдена
        self.pairs.append((key, value))

Такая реализация является медленной: на поиск элемента уходит в среднем \(O(n)\) операций.

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

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

Принцип работы хеш-функции и хеш-таблицы

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

Эта проблема решается хешированием, для которого необходима хеш-функция.

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

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

   ключ      первая буква   хеш
   ────      ────────────   ───
   яблоко         я          33
   груша          г           4
   слива          с          19

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

   корзины
   ┌────┬───────────────────┐
   │  4 │ груша: 120 кг     │  ← сюда попадает «груша»
   ├────┼───────────────────┤
   │ 19 │ слива: 45 кг      │
   ├────┼───────────────────┤
   │ 33 │ яблоко: 300 кг    │
   └────┴───────────────────┘

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

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

Пусть корзин \( M = 11 \), а хеш вычисляется второй функцией — суммой номеров букв. Для «груши» она даёт 70, и остаток \( 70 \bmod 11 = 4 \):

   ключ  ──[хеш-функция]──▶  хеш  ──[% M]──▶  номер корзины  ──▶  значение
  «груша»                     70              70 % 11 = 4          120 кг

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

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

Коллизии

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

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

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

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

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

Коэффициент заполнения и перехеширование

Условие «корзин достаточно» выражается числом. Отношение количества ключей в таблице к количеству корзин называют коэффициентом заполнения (англ. load factor): пока он мал, цепочки коротки и почти все корзины пусты, а когда он приближается к единице, ключи теснятся и каждая операция сопровождается перебором.

Как только коэффициент превышает порог, выбранный реализацией (в CPython у словаря это две трети, у множества — три пятых), заводится новый массив корзин, в несколько раз больший прежнего, и все ключи раскладываются по нему заново: номер корзины вычисляется по модулю \(M\), а \(M\) изменилось. Эту перестройку называют перехешированием (англ. rehashing).

Стоит она \(O(n)\), но происходит редко и с каждым разом всё реже, поскольку таблица растёт не на одну корзину, а кратно. Та же арифметика рассмотрена в главе «Основные структуры данных» под заголовком «Реаллокация в динамических массивах»: редкие дорогие перестройки, распределённые по множеству дешёвых операций, дают амортизированную \(O(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 \bmod 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\). В противном случае в некоторые ячейки запись будет производиться чаще, чем в остальные, и обращение к таблице замедлится. Пример неравномерной функции — среднесуточная температура по городу и дате: большую часть времени она держится на одном уровне, а аномальные морозы или жара случаются редко.

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

  • Лавинность. При незначительном изменении входных данных выходное значение должно меняться значительно. При хешировании паролей функция, лишённая лавинности, взламывается проще. Если злоумышленнику известно, что \(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\), \(M\) и \(R\), тем реже коллизии. В качестве \(R\) выше было условлено использовать \(2^{32}\), поэтому любое нечётное число не будет иметь с \(R\) общих делителей.

Число \(M\) меняется вслед за размером хеш-таблицы, ещё не известным в момент вычисления хеша, поэтому нельзя гарантировать, что заданное заранее \(q\) и число корзин \(M\) окажутся взаимно простыми. Однако большое простое \(q\) делает нетривиальные общие делители маловероятными, поскольку у простого числа нет делителей, кроме него самого и единицы. \(M\) обычно также выбирают простым, поэтому общие делители появятся, только когда \(M=q\).

Реализация хеш-таблицы на цепочках

Возьмём одиннадцать корзин — число простое и небольшое, чтобы коллизии были заметны, — а хеш будем вычислять суммой номеров букв, как в примере со складом:

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


def letters_hash(key):
    # Хеш — сумма номеров букв, входящих в ключ
    return sum(ALPHABET.index(letter) + 1 for letter in key)


class HashMap:
    def __init__(self, buckets_count=11):
        # В каждой корзине лежит список пар: это и есть метод цепочек
        self.buckets = [[] for _ in range(buckets_count)]

    def _bucket(self, key):
        # Хеш превращается в номер корзины остатком от деления
        return self.buckets[letters_hash(key) % len(self.buckets)]

    def get(self, key):
        # Перебираем цепочку, привязанную к корзине, а не всю таблицу
        for stored_key, value in self._bucket(key):
            if stored_key == key:
                return value
        return None

    def set(self, key, value):
        bucket = self._bucket(key)
        for i, (stored_key, _) in enumerate(bucket):
            if stored_key == key:
                bucket[i] = (key, value)
                return
        bucket.append((key, value))

У «груши» сумма номеров букв равна 70, и остаток \( 70 \bmod 11 = 4 \), а у «яблока» сумма 92, и остаток \( 92 \bmod 11 = 4 \) — тот же. Это коллизия: два ключа делят одну корзину и хранятся в ней списком:

warehouse = HashMap()
warehouse.set('груша', 120)
warehouse.set('яблоко', 300)

print(letters_hash('груша') % 11)   # 4
print(letters_hash('яблоко') % 11)  # 4
print(warehouse.buckets[4])         # [('груша', 120), ('яблоко', 300)]
print(warehouse.get('яблоко'))      # 300

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

bucket_index = hash('груша') % 11

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

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

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

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

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

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

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

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

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

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

Резюме

  • Хеш-таблица превращает поиск по ключу в вычисление: хеш-функция вычисляет по ключу число, остаток от деления этого числа на количество корзин даёт номер ячейки, а далее работает обычный массив.
  • Коллизии неизбежны у любой хеш-функции, и разрешаются они либо методом цепочек, когда в корзине хранится список пар, либо открытой адресацией, когда пара помещается в ближайшую свободную ячейку.
  • Ожидаемая \(O(1)\) обеспечивается двумя условиями: хеш-функция распределяет ключи равномерно, а корзин достаточно. Второе обеспечивается перехешированием, стоящим \(O(n)\) на редких перестройках и потому не ухудшающим среднюю стоимость.
  • От хеш-функции требуются детерминизм, эффективность, ограниченность и равномерность, а от криптографической — дополнительно лавинность и необратимость.
  • Число корзин выбирается простым, чтобы закономерности, скрытые во входных ключах, не приводили раз за разом в одну ячейку.
  • Строки хешируются полиномиально, по модулю большого числа \(R\), выбранного взаимно простым с основанием \(q\) и числом корзин.
  • Поисковый индекс представляет собой ту же хеш-таблицу, где ключом служит слово, а значением — список его позиций; на нём основан и полнотекстовый поиск в базах данных.