Мы уже пользовались хеш-таблицами

В прошлых уроках мы не раз применяли Dictionary и HashSet. Мы использовали их в поиске повторов, работе с префиксными суммами и представлении детей в Trie. Работает это быстро и удобно: добавляем элементы, проверяем наличие, и при хорошем распределении ключей ожидаемое число проверок остаётся небольшим. Но что именно стоит за этой скоростью, мы до сих пор не разбирали. Пора заглянуть внутрь и посмотреть, как ключ превращается в адрес, по которому его можно быстро найти.

Начнём с наблюдения, которое и лежит в основе всей идеи. Если бы у каждого возможного ключа был свой уникальный номер, а этот номер можно было бы использовать как индекс в массиве, поиск был бы мгновенным: зная номер, сразу обращаемся к нужной ячейке. Но проблема в том, что ключей может быть бесконечно много, а массив всегда конечен. Числа, строки, составные объекты — всё это может быть ключами, и зарезервировать по отдельной ячейке на каждый возможный ключ невозможно. Значит, нужно превратить ключ в число, а затем уложить это число в ограниченный диапазон индексов. Это превращение и называется хешированием.

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

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

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

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

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

Учебная хеш-функция для строк

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

using System;

string[] words = { "cat", "car", "dog", "abc", "cba" };
foreach (string w in words)
{
    uint h = HashAscii(w);
    Console.WriteLine(w + " " + h + " " + (h % 8));
}

uint HashAscii(string s)
{
    if (s == null) throw new ArgumentNullException(nameof(s));
    uint hash = 0;
    foreach (char c in s)
    {
        if (c > 127) throw new ArgumentException("Поддерживаются только ASCII-символы.");
        unchecked
        {
            hash = hash * 31 + c;
        }
    }
    return hash;
}

Вывод:

cat 98262 6
car 98260 4
dog 99644 4
abc 96354 2
cba 98274 2

Проверим расчёты. Функция устроена так: начинаем с нуля, для каждого символа умножаем текущий хеш на 31 и прибавляем код символа. Для «cat»: после 'c' (99) хеш равен 99. После 'a' (97): 99 · 31 + 97 = 3069 + 97 = 3166. После 't' (116): 3166 · 31 + 116 = 98 146 + 116 = 98 262. Совпадает.

Для «car» расчёт похож. 'c' — 99, после первого символа хеш равен 99. 'a' — 97, после второго: 99 · 31 + 97 = 3069 + 97 = 3166. 'r' — 114, после третьего: 3166 · 31 + 114 = 98 146 + 114 = 98 260. Для «dog»: 'd' — 100, после первого хеш равен 100. 'o' — 111, после второго: 100 · 31 + 111 = 3100 + 111 = 3211. 'g' — 103, после третьего: 3211 · 31 + 103 = 99 541 + 103 = 99 644. Итак, «car» даёт 98 260, «dog» — 99 644. Хеши разные, никакого совпадения. Но посмотрим на индексы корзин при capacity 8: 98 260 mod 8 = 4 (поскольку 98 260 = 12 282 · 8 + 4), а 99 644 mod 8 = 4 (99 644 = 12 455 · 8 + 4). Оба попадают в корзину 4, хотя их хеш-коды совершенно разные. Это тоже коллизия — но не совпадение хешей, а совпадение индексов корзин после взятия остатка. Такая коллизия встречается ещё чаще, чем совпадение самих хешей: разные хеш-коды могут давать одинаковый остаток от деления на размер массива. Именно поэтому после вычисления индекса всё равно нужна проверка Equals среди кандидатов в корзине: в корзине 4 окажутся оба слова, «car» и «dog», и таблица должна уметь различить их по содержимому.

Обратим внимание на важное свойство: порядок символов влияет на хеш. «abc» и «cba» содержат одни и те же символы, но получают разные хеши — 96 354 и 98 274. Это преимущество полиномиального хеша перед простой суммой кодов: если бы мы просто складывали символы, «abc» и «cba» дали бы одинаковый результат, а это плохо, потому что разные строки получали бы одинаковый хеш слишком часто.

Но и полиномиальный хеш не исключает коллизий. Вот наглядный пример в ASCII: строки «Aa» и «BB». Код 'A' — 65, 'a' — 97, 'B' — 66. Хеш «Aa»: 65 · 31 + 97 = 2015 + 97 = 2112. Хеш «BB»: 66 · 31 + 66 = 2046 + 66 = 2112. Одинаковые хеши при разных строках. Это коллизия, и она показывает: каким бы хорошим ни был хеш, гарантии уникальности он не даёт. При поиске в таблице нам придётся сравнить оба ключа через Equals и выбрать нужный.

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

Стоимость вычисления хеша зависит от длины ключа. Строка длины L требует O(L) работы: нужно пройти по всем символам. Только после этого мы получаем индекс корзины за O(1) и ищем по кандидатам. Для коротких строк L мала, и всё выглядит мгновенным. Для длинных строк хеширование может занимать заметное время, и это надо учитывать: утверждение «поиск в хеш-таблице за O(1)» подразумевает, что ключи имеют ограниченную длину и хеширование не растёт с размером таблицы. Обычно это условие выполняется, но полезно помнить, что «O(1)» здесь относится к числу элементов в таблице, а не к длине ключа.

Согласованность Equals и хеша

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

Рассмотрим пример. Пусть мы решили, что строки «Cat» и «cat» равны, потому что регистр не важен. Наш учебный хеш это не учитывает: он даст для «Cat» и «cat» разные значения, потому что код 'C' (67) отличается от кода 'c' (99). Если мы используем такой хеш с Equals, который считает эти строки равными, таблица будет работать неправильно: положив «Cat», мы рискуем не найти равный ему по условию ключ «cat». Значит, если Equals игнорирует регистр, хеш-функция тоже должна игнорировать регистр.

Готовые средства C# позволяют задать такое поведение правильно. Например, StringComparer.OrdinalIgnoreCase — это компаратор, который согласованно задаёт равенство и хеширование без учёта регистра. Dictionary можно создать с этим компаратором, и тогда «Cat» и «cat» будут считаться одним ключом. Писать свою функцию для этого не нужно: стандартный компаратор уже согласован внутри себя. Мы не будем разбирать его реализацию, но полезно знать, что такое средство есть, и что согласованность Equals и хеша — обязательное требование, а не пожелание.

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

Проиллюстрируем мысленно. Пусть у нас есть ключ-объект с полем Name, и хеш вычисляется по Name. Мы положили ключ со значением Name = "cat", он попал в корзину 6. Затем мы изменили Name на "dog". Хеш теперь указывает на другую корзину, но запись по-прежнему лежит в корзине 6. При поиске по ключу с Name = "dog" мы пойдём в новую корзину и не найдём там запись. А при поиске по "cat" мы не найдём ключ, потому что его Name теперь "dog". Получается, что запись есть, но найти её нельзя ни по старому, ни по новому значению.

Отсюда правило: ключи должны быть неизменяемыми в той части, которая влияет на хеш и равенство. Значения, связанные с ключом, менять можно: таблица хранит пары «ключ — значение», и значение не участвует в вычислении хеша. Но сам ключ должен оставаться стабильным, пока находится в таблице.

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