Хеш-таблица

В «Войне и мире» 436 069 слов, из них 47 585 разных. Чтобы посчитать, сколько раз встречается каждое, программа 436 тысяч раз ищет слово в своём словаре. В отсортированном списке на такой поиск уходит около шестнадцати сравнений, в хеш-таблице — одна-две пробы. Ниже 4096 ячеек, и в них по порядку сыплются слова романа: «лев», «толстой», «том», «первый»… Цвет ячейки показывает, сколько проб нужно, чтобы найти лежащее в ней слово. Двигайте заполнение и переключайте способ, которым таблица разрешает коллизии.

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

Идея

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

Хеш-функция отображает ключ в большое число, а номер ячейки — остаток от деления этого числа на размер таблицы m. Если двум разным ключам выпал один номер, это коллизия. Отношение числа ключей n к числу ячеек называют коэффициентом заполнения и обозначают α = n/m. Главный факт про хеш-таблицы: средняя цена поиска зависит от α, а не от n. Таблица на миллиард ключей при α = 0,5 делает на поиск столько же проб, сколько таблица на тысячу.

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

Решение первое: хеш-функция

От хеш-функции требуются три вещи. Равные ключи — равные хеши, всегда: если a == b, то hash(a) == hash(b), иначе таблица положит ключ в одну ячейку, а искать будет в другой. Разные ключи — по возможности разные хеши, разбросанные так, будто их тянули жребием. И скорость: хеш считают при каждом поиске.

Второе требование проваливают самые очевидные функции. Сумма кодов букв даёт одинаковый хеш всем анаграммам: «кот», «ток» и «кто» лягут в одну ячейку. Длина слова занимает считаные номера: в романе нет слов длиннее 24 букв, так что сорок семь тысяч слов набились бы в два десятка ячеек. В главе курса о хешировании пять таких функций проверены на том же словаре «Войны и мира», и плохая от хорошей отличается в тысячи раз по числу сравнений (таблица в главе).

Мы во всех листингах и сценах берём FNV-1a: начинаем с фиксированного 64-битного числа и для каждого байта ключа делаем «исключающее или», а потом умножаем на большое простое. Умножение разносит влияние каждого байта по всем битам, поэтому «кот» и «ток» получают далёкие хеши. Та же функция работает в фильтре Блума этого каталога.

Решение второе: куда девать коллизию

Можно ли обойтись без коллизий, если взять таблицу побольше? Нет: это задача о днях рождения. В таблице из 4096 ячеек, как в сцене, коллизия становится вероятнее, чем её отсутствие, уже на 76-м слове — примерно на 1,18·√m ключах (вывод в «Царице наук»). Значит, нужен способ с ними жить. Способов два.

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

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

• линейное пробирование — следующая ячейка, ещё следующая: i, i + 1, i + 2, …;
• двойное хеширование — шаг тоже берётся из хеша и у разных ключей разный: i, i + s, i + 2s, … В наших листингах s — старшая половина того же 64-битного хеша, сделанная нечётной: при размере-степени двойки такой шаг обходит все ячейки.

Линейное пробирование страдает от первичной кластеризации. Пусть в таблице есть ряд из L занятых ячеек подряд. Новый ключ продлит его, если его домашняя ячейка — любая из этих L или следующая за ними свободная: вероятность (L + 1)/m. Длинный ряд ловит ключи чаще короткого, растёт быстрее и сливается с соседями. На 90 % в сцене самый длинный кластер — 742 ячейки, почти пятая часть таблицы. Двойное хеширование разводит маршруты разных ключей, и кластеры не растут лавиной.

Сколько проб нужно

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

Формулы для двойного хеширования выводятся в две строки. Неудачный поиск смотрит ячейки, пока не встретит пустую; каждая следующая ячейка маршрута занята примерно с вероятностью α, поэтому проб в среднем 1 + α + α² + … = 1/(1 − α). Удачный поиск ключа повторяет путь, которым ключ когда-то вставили, а вставка стоила как неудачный поиск при тогдашнем заполнении x. Усредним 1/(1 − x) по всем x от 0 до α — получится (1/α) · ln(1/(1 − α)).

Квадрат в формуле линейного пробирования — цена кластеров. Её вывел Дональд Кнут в 1963 году, и вывод уже не умещается в абзац: приходится считать, сколькими способами n ключей могут разложиться по кольцу из m ячеек.

Вот что получилось на настоящих словах романа. Это вывод листинга novel из раздела с кодом; в скобках — формулы:

load  method   hit, formula   miss, formula  longest
 75%  linear   2.66 ( 2.50)   10.38 (  8.50)      144
 75%  double   1.85 ( 1.85)    3.98 (  4.00)       24
 75%  chains   1.39 ( 1.38)    0.75 (  0.75)        5
 90%  linear   8.17 ( 5.50)  109.19 ( 50.40)      742
 90%  double   2.52 ( 2.56)   10.12 (  9.99)       95
 90%  chains   1.47 ( 1.45)    0.90 (  0.90)        5

Цепочки и двойное хеширование совпадают с формулами до сотых. Линейное пробирование на 90 % промахнулось в полтора-два раза, и дело не в хеш-функции: на случайных числах вместо слов разброс такой же. Формула описывает среднее по всем возможным раскладкам, а на конкретной таблице один огромный кластер может съесть пятую часть ячеек и удвоить цену. Чем ближе α к единице, тем меньше линейное пробирование предсказуемо.

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

Решение третье: когда переезжать

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

Цепочки терпят высокое заполнение, открытая адресация — нет; самые смелые пороги у Swiss Tables, которые сравнивают сразу по восемь-шестнадцать ячеек одной командой процессора. Сам переезд дорогой: номер ячейки — хеш по модулю размера, поэтому при новом размере каждый ключ надо разложить заново. Но если размер каждый раз удваивается, переезды стоят в сумме меньше 2n перекладываний на n вставок — та же арифметика, что у динамического массива. Поэтому вставка стоит O(1) амортизированно: редкий дорогой переезд размазывается по многим дешёвым вставкам.

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

Решение четвёртое: как удалять

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

«Кутузов» живёт в ячейке 6, хотя его дом — 5: когда его вставляли, ячейку 5 уже занял «николай». Стоит её очистить, и поиск «кутузова» начинает с ячейки 5, видит пустоту и отвечает «нет». Ключ в таблице есть, а найти его нельзя. Два способа это исправить:

• Надгробие. На место ключа ставят метку «здесь был ключ». Поиск её перешагивает, вставка может занять. Так удаляет словарь Python. Минус: надгробия копятся, удлиняют маршруты, и таблицу время от времени перестраивают с нуля.
• Сдвиг назад, только для линейного пробирования. После удаления идём по кластеру дальше и переносим в дыру первый ключ, чей маршрут от дома проходит через неё; потом то же с новой дырой, пока не встретится пустая ячейка. Таблица остаётся такой, будто удалённого ключа никогда не было. Это алгоритм R из третьего тома «Искусства программирования» Кнута, его и реализует листинг.

Код

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

В таблице из восьми корзин «наташа» и «николай» делят корзину 4, «пьер» и «андрей» — корзину 7. После переезда в шестнадцать корзин обе пары так и остались вместе: у их хешей совпадают не только три, но и четыре младших бита. А «наполеон», добавленный последним, попал в корзину 10 к «соне».

Теперь открытая адресация с линейным пробированием. Ключи и значения лежат в двух параллельных массивах, пустая ячейка — None в Python и пустая строка в Go. Удаление в remove — сдвиг назад из предыдущего раздела, а демо показывает, что было бы, если ячейку просто стереть.

И таблицы на всём романе. Программа читает «Войну и мир» с сервера, где исполняется код, выбирает первые 20 000 разных слов в порядке появления и кладёт их в таблицы из 4096 ячеек тремя способами при заполнении 50, 75, 90 и 95 %. Неудачный поиск меряется на словах с 10 001-го по 20 000-е: в таблицу они не попадают никогда. Это те же числа, что показывает первая сцена.

Сколько это стоит

Среднее O(1) держится на двух условиях: хеши разбросаны равномерно, а α ограничено константой. Худший случай — все ключи в одной ячейке, и таблица превращается в список. Память — O(n), но с запасом: треть или четверть ячеек пустует нарочно, у цепочек к каждому ключу добавляется указатель.

Порядка в хеш-таблице нет. Найти ближайшее слово по алфавиту, все ключи от «а» до «б» или минимум она не может, кроме как перебрав всё. Если такие запросы нужны, берут дерево поиска или отсортированный массив с двоичным поиском: они ищут за O(log n), но помнят порядок. Ниже замер: поиск существующих ключей в случайном порядке в словаре и двоичным поиском в отсортированном списке, на таблицах от тысячи до миллиона ключей.

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

Где ломается: атака коллизиями

Всё сказанное о скорости опиралось на то, что хеши ведут себя как случайные. А если ключи выбирает противник? Формула хеша строк в Java открыта: s[0]·31ⁿ⁻¹ + … + s[n−1] по модулю 2³². У строк «Aa» и «BB» хеш одинаковый: 65·31 + 97 = 66·31 + 66 = 2112. А раз хеш склейки двух строк — это хеш первой, умноженный на 31 в степени длины второй, плюс хеш второй, то любая строка из одиннадцати блоков «Aa» и «BB» получает один и тот же хеш. Таких строк 2¹¹ = 2048.

2048 слов романа разошлись по 1024 корзинам, самая длинная цепочка — 10, и вставка всех стоила 2138 сравнений ключей. 2048 ключей атакующего легли в одну корзину, и каждый новый ключ сравнивают со всеми прежними: 2048·2047/2 = 2 096 128 сравнений, в тысячу раз больше. Вдвое больше ключей — вчетверо больше работы: атака превращает O(n) в O(n²).

Это не учебная угроза. В 2003 году Скотт Кросби и Дэн Уоллак показали такие атаки на Perl и прокси-сервер Squid. В декабре 2011 года Александр Клинк и Юлиан Вельде на конгрессе Chaos Communication Congress показали, что параметры HTTP-запроса во многих популярных веб-платформах — PHP, Java, Python, Ruby, движок JavaScript V8 — складываются в хеш-таблицу с известной хеш-функцией. Запрос в мегабайт с десятками тысяч подобранных параметров занимал ядро процессора на десятки секунд и даже минуты.

Защит три, и в ходу все.

• Секретное зерно. Хеш-функция зависит от случайного числа, которое программа выбирает при запуске и никому не показывает; подобрать коллизии, не зная его, нельзя. Для этого нужна функция, по выходам которой зерно не вычислить, — SipHash. Python включил случайное зерно для строк по умолчанию в версии 3.3 и перешёл на SipHash в 3.4, Rust использует SipHash-1-3 по умолчанию, у каждой карты в Go своё случайное зерно. Переключите в сцене «Секретное зерно»: те же ключи атакующего рассыпаются по корзинам.
• Деревья в корзинах. С Java 8 цепочка HashMap длиннее восьми (если корзин в таблице не меньше 64) превращается в красно-чёрное дерево, и даже при полной коллизии поиск стоит O(log n), а не O(n). Режим «Деревья» в сцене считает сравнения по этому правилу.
• Лимиты. PHP 5.3.9 в январе 2012 года просто ограничил число параметров запроса настройкой max_input_vars.

Как устроены настоящие таблицы

Swiss Table придумали в Google и показали в 2017 году. В отдельном массиве лежит по байту на ячейку: свободна она, удалена или занята, и тогда в байте семь битов хеша ключа. Поиск сравнивает свои семь битов сразу с шестнадцатью байтами (в Go — с восемью) одной командой процессора и заглядывает только в ячейки, где совпало. Ключи сравниваются редко, и заполнение 7/8 перестаёт быть страшным. Есть и другие приёмы для высокого заполнения: хеширование Робин Гуда, где ключ, ушедший далеко от дома, отбирает ячейку у ключа, ушедшего недалеко, и кукушкино хеширование с поиском ровно за две пробы.

История

В январе 1953 года Ханс Петер Лун написал во внутренней записке IBM, что номер ящика можно вычислять из ключа, а записи, которым выпал один ящик, связывать в цепочку. Через год Джин Амдал, Элейн Макгроу (тогда Бёме) и Артур Сэмюэл писали ассемблер для IBM 701 и придумали класть запись в соседнюю свободную ячейку — линейное пробирование. Независимо к нему пришёл Андрей Ершов, когда писал программирующую программу для БЭСМ, и опубликовал его в 1958 году. Подробно эта история рассказана в главе курса.

Летом 1963 года молодой Дональд Кнут вывел формулу для среднего числа проб линейного пробирования — ту самую, с квадратом. Позже он называл эту заметку своим первым анализом алгоритма, а с неё нередко отсчитывают анализ алгоритмов как отдельную область.

Задачи

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