Хеш-таблица: атака и защита

Калькулятору из прошлой главы понадобились переменные с именами, и глава закончилась вопросом: как словарь находит имя среди миллиона за одну операцию? То, что он это умеет, мы видели в главе 13: поиск во множестве из миллиона элементов занимает столько же, сколько в множестве из десяти тысяч, — сотые доли микросекунды. А вот опыт, который в эту картину не укладывается. Два списка разных целых чисел одинаковой длины. Из каждого строим множество и засекаем время.

Числа во втором списке тоже разные, их столько же, операция та же, а множество строится в тысячи раз дольше. И вдвое больше чисел стоит вчетверо больше времени: так ведут себя квадратичные программы из главы 13. Значит, «одна операция» бывает не всегда. Чтобы понять, когда она бывает, а когда нет, надо узнать, как множество находит элемент.

Подсказка есть в главе 14. Массив отдаёт ячейку по номеру за одно действие: адрес равен началу плюс номер, умноженный на восемь, и миллионная ячейка так же близка, как первая. Если научиться превращать сам ключ — имя, слово, число, кортеж — в номер ячейки, поиск по ключу станет таким же быстрым, как чтение по индексу.

Глава устроена как матч. Сначала защита строит такую картотеку. Потом нападение ищет в ней слабость и находит — так в декабре 2011 года со сцены в Берлине показали, как одним запросом занять сервер на десятки минут. Потом защита чинит. Три раунда, и в конце второго мы разгадаем загадку двух множеств.

IBM, январь 1953. Записка Луна

Раунд 1. Защита: ящики с номерами

Идея Луна такая. Заведём $m$ ящиков с номерами от $0$ до $m - 1$ — обычный список, у которого ячейка по номеру находится мгновенно. Придумаем функцию, которая из ключа делает целое число, и положим запись в ящик номер «это число по модулю $m$». Чтобы найти запись, вычислим тот же номер и заглянем только в один ящик.

Функцию, которая превращает ключ в число, называют хеш-функцией, а само число — хешем ключа. Список ящиков вместе с правилом раскладки — это хеш-таблица, а сами ящики обычно называют корзинами. Вот первая картотека. Хеш-функция у неё самая простая, какую можно придумать для слова: сумма кодов букв. Код буквы возвращает функция ord: у «а» он 1072, у «б» — 1073.

Шесть героев разошлись по восьми корзинам, но не по одному: Пьер делит корзину 0 с Долоховым, а Наташа корзину 7 — с Андреем. Два разных ключа, которым выпала одна корзина, — это коллизия. Наша картотека справляется с ней так, как предлагал Лун: в корзине лежит список записей, и get перебирает его, сравнивая ключи. Такой способ называют методом цепочек. Перебор не страшен, пока цепочки короткие. Беда начнётся, если какая-нибудь из них разрастётся.

В последнем цикле enumerate(buckets) отдаёт пары «номер — элемент», чтобы не заводить счётчик вручную. Поиграйте с картотекой сами: вписывайте ключи, меняйте хеш-функцию и смотрите, куда они падают.

Раунд 1. Нападение: однофамильцы

Нападению даже не нужно стараться: слабое место видно в самой картотеке. Наберите в ней «кот», «ток» и «кто». Сумма кодов не зависит от порядка букв, поэтому все анаграммы (мы собирали их для кроссворда в главе 8) попадают в одну корзину. Чем это грозит на живом тексте, проверим так: разложим словарь «Войны и мира» — 51 787 разных слов — по 65 536 корзинам пятью разными хеш-функциями и посчитаем, сколько корзин занято, какова самая длинная цепочка и сколько сравнений в среднем стоит поиск слова.

Таблица читается как протокол разгрома. Длина слова занимает 29 корзин из шестидесяти пяти тысяч: других длин в книге нет. В самую длинную цепочку попало 7774 слова, и поиск в среднем стоит почти три тысячи сравнений — хуже, чем у отсортированного списка. Первая буква немногим лучше. Сумма кодов выглядит пристойнее, но тоже проваливается: у слов из пяти–восьми букв суммы лежат в узком промежутке от пяти до девяти тысяч, анаграммы совпадают, и занято всего три с половиной тысячи корзин. Цепочки доходят до 142 слов.

Последние две строки — совсем другой мир. Функция poly31 умножает накопленный хеш на 31 и прибавляет код очередной буквы — так считает хеш строки язык Java. Перемножения раскидывают буквы по разным «разрядам», поэтому «кот» и «ток» получают разные хеши, а соседние слова — далёкие. Это та же схема Горнера, которой вычисляют многочлен: хеш — значение многочлена с коэффициентами-буквами в точке 31. Остаток от деления на $2^{32}$ держит число в пределах 32 бит, как в Java. Встроенная функция Python hash справляется не хуже, хотя устроена иначе; к ней мы вернёмся в третьем раунде.

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

Что значит «рассыпаются, как будто жребием», и почему тогда поиск быстрый? Пусть в таблице $m$ корзин и $n$ ключей. Отношение $\alpha = n/m$ называют коэффициентом заполнения: это среднее число ключей на корзину. В таблице выше $\alpha = 51\,787 / 65\,536 \approx 0{,}79$.

Для «Войны и мира» теорема обещает $1 + 0{,}79/2 \approx 1{,}4$ сравнения — столько и вышло у poly31 и hash. Заодно теорема называет условие быстроты: время поиска определяет не $n$, а $\alpha$. Если держать $\alpha$ ограниченным, поиск стоит $O(1)$ при любом числе записей. Значит, когда ключей становится много, корзин тоже должно становиться больше.

Раунд 1. Защита: переезд

Картотека с восемью корзинами навсегда хороша для шести героев и безнадёжна для миллиона абонентов: при $\alpha = 125\,000$ поиск превращается в перебор. Лекарство знакомо по главе 14: когда тесно — переезжать в помещение побольше, например вдвое. Но у хеш-таблицы переезд хитрее, чем у списка. Номер корзины — это хеш по модулю $m$, и когда $m$ меняется, меняются и номера. Запись, лежавшая в корзине 3 из восьми, в таблице из шестнадцати может оказаться в корзине 11. Поэтому при переезде каждую запись раскладывают заново. Соберём картотеку в класс и сравним её с вечными восемью корзинами.

Восемь корзин навсегда — это опять квадрат: вчетверо больше ключей, вчетверо дольше каждый. С переездами цена одного ключа держится почти ровно: ключей в 256 раз больше, а каждый дороже лишь в несколько раз. Этот рост к концу объясняется памятью: большая таблица перестаёт помещаться в быстрый кэш процессора, об этом глава 34. А почему редкие переезды не портят среднюю цену, мы доказали монетками в главе 14: при переезде вдвое каждая вставка заранее откладывает пару монет на будущую раскладку, и вставка стоит $O(1)$ амортизированно. Включите в картотеке выше флажок «расширять» и добавляйте ключи — увидите, как на каждом переезде записи разлетаются по новым корзинам.

Без цепочек: открытая адресация

Словарь и множество Python устроены иначе — так, как придумал Амдал. Цепочек у них нет: в каждой ячейке таблицы лежит не больше одной записи. Если ячейка занята, запись ищет другую по определённому маршруту, а поиск идёт тем же маршрутом, пока не найдёт ключ или пустую ячейку. Это называют открытой адресацией. Возьмём микроскоп из главы 14 и посмотрим, как Python раскладывает числа по таблице множества. Хеш небольшого целого числа — само число, поэтому числу $x$ в таблице из восьми ячеек нужна ячейка $x \bmod 8$.

Тройка и пятёрка легли на свои места. Одиннадцати тоже нужна ячейка 3, но она занята, и 11 оказалось в ячейке 0. Девятнадцать нашло занятыми и 3, и 0 и легло в 1. Маршрут здесь такой: из ячейки $i$ — в ячейку $5i + 1$ по модулю размера таблицы, с поправкой на старшие биты хеша (у маленьких чисел они нули; в больших таблицах множество вдобавок сначала заглядывает в несколько соседних ячеек). Из тройки получается $16 \bmod 8 = 0$, из нуля — 1, дальше 6, 7, 4, 5, 2 — маршрут обходит все восемь ячеек, прежде чем повториться. В картотеке выше переключатель «открытая адресация» показывает простейший маршрут Амдала: следующая ячейка, потом ещё следующая.

У открытой адресации своя цена: в почти полной таблице маршруты становятся длинными, ведь свободных мест мало. Поэтому словарь Python переезжает раньше, чем наша картотека: как только заняты две трети ячеек. Таблица на 8 ячеек держит пять записей, на 16 — десять, на 32 — двадцать одну. Порядок записей, который словарь помнит (мы видели это в главе 8), хранится отдельно: сами записи лежат в обычном массиве по порядку добавления, а хеш-таблица держит только их номера в этом массиве.

Перерыв: дни рождения

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

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

около 1 200 около 50 000 около 500 000 около миллиона

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

Совпасть может любая пара ключей, а пар много. У $k$ ключей их $\frac{k(k-1)}{2}$, и каждая пара попадает в одну корзину с вероятностью $\frac1m$. Значит, в среднем коллизий $\frac{k(k-1)}{2m}$, и эта величина доходит до половины, когда $k$ порядка $\sqrt{m}$. Точный расчёт для 365 дней сделан в «Царице наук»; та же формула для любого $m$ показывает, что с вероятностью больше половины совпадение случается уже при $k \approx 1{,}18\sqrt{m}$ ключах. Для 365 дней это 23 человека, для миллиона корзин — 1178 ключей. Проверьте опытом.

Вывод из перерыва трезвый: коллизии неизбежны, и случаются они рано. Даже если хеш — 32-битное число, то есть четыре миллиарда возможных значений, среди 77 тысяч ключей два одинаковых хеша найдутся с вероятностью больше половины. Таблица обязана уметь жить с коллизиями — цепочками или маршрутами. Её быстрота держится на другом: коллизий мало, и они разбросаны равномерно. Запомните это слово — «равномерно». Во втором раунде нападение ударит именно по нему.

Почему ключ не может быть списком

Но сначала вернём один долг. В главе 8 словарь отказался принимать список в роли ключа с ошибкой unhashable type: 'list', а в главе 12 множество отказалось от клеток острова. Теперь видно, что значит это слово: «нехешируемый» — тот, у кого нельзя взять хеш, а значит, нельзя выбрать корзину. Посмотрим, что умеет встроенная функция hash.

Хеш небольшого целого — само число. Исключение одно: hash(-1) равен −2, потому что внутри CPython, написанного на языке C, число −1 занято под сигнал «при вычислении хеша случилась ошибка». Большие числа берутся по модулю $2^{61} - 1$, поэтому у $2^{61} - 1$ хеш ноль. У $1$, $1{,}0$ и True хеши одинаковые: этого требует закон, без которого словарь бы не работал.

Обязано потому, что словарь ищет ключ только в корзине его хеша. Если бы у равных ключей хеши различались, d[1.0] искал бы в одной корзине, а запись с ключом 1 лежала бы в другой, и словарь бы её не нашёл, хотя ключи равны. Поэтому Python и считает 1, 1.0 и True одним ключом: третья строка вывода — словарь из одной записи, в которой первый ключ остался, а значение перезаписано дважды. Хеш кортежа собирается из хешей его элементов. А хеш списка Python отказывается считать вовсе. Вычислить его было бы нетрудно — например, как у кортежа. Опасность в другом, и её можно показать на собственном классе.

Возьмём клетку острова из главы 12. Равенство у неё — по координатам, а чтобы её приняли словарь и множество, нужен ещё метод __hash__. По договору хеша он должен опираться на те же поля, что сравнивает __eq__, — на пару координат. Проще всего взять хеш кортежа из этих полей.

Первая находка радует: Cell(3, 5) в квадратных скобках — новый объект, но он равен ключу, хеш у него тот же, и словарь находит нору. Вторая пугает. Нору Снежка записали под клеткой (10, 10), потом клетку сдвинули. Запись по-прежнему лежит в словаре — последняя строка её печатает, — но найти её нельзя никак. По новому ключу (11, 10) словарь ищет в другой корзине. По старому (10, 10) он приходит в правильную корзину, но лежащий там ключ ему больше не равен. Запись потеряна, хотя её никто не удалял.

То же случилось бы со списком в роли ключа: один append через второй ярлык — и запись пропала. Поэтому в Python хешируемыми сделаны только неизменяемые встроенные типы: числа, строки, кортежи из хешируемых, frozenset — замороженное множество. А для своих классов правило такое: пишете __eq__ — пишите и __hash__ из тех же полей, и не меняйте эти поля, пока объект лежит в словаре или множестве. Кстати, если написать __eq__ без __hash__, Python сам отберёт у класса хеш — именно поэтому клетка из главы 12 оказалась нехешируемой.

Раунд 2. Нападение: Берлин, 2011

Защита построила картотеку, где поиск стоит $1 + \alpha/2$ сравнения. Но в теореме было условие: ключи рассыпаются по корзинам как по жребию. А ключи пишут люди, и среди них бывает противник.

Для poly31, хеша Java, подобрать ключи с одинаковым хешем — почти школьная задача. Хеш двухбуквенной строки — $31 \cdot c_1 + c_2$, где $c_1$, $c_2$ — коды букв. Если первую букву сдвинуть на единицу вперёд, а вторую — на 31 назад, сумма не изменится. Код «а» — 1072, «я» — 1103, «б» — 1073:

$$h(\text{ая}) = 31 \cdot 1072 + 1103 = 34\,335 = 31 \cdot 1073 + 1072 = h(\text{ба}).$$

Дальше работает схема Горнера: хеш длинной строки зависит от её начала только через хеш начала. Поэтому «ая» можно заменить на «ба» в любом месте строки, и хеш не изменится. Из $k$ блоков, каждый из которых — «ая» или «ба», получается $2^k$ разных строк с одним хешем: восемь блоков — 256 строк, двадцать — больше миллиона. В докладе для Java взяли такую же пару, только латинскую: Ey и FZ. Попробуйте сами найти пару в кузнице.

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

Функция itertools.product перебирает все сочетания: product(["ая", "ба"], repeat=3) даёт восемь троек от («ая», «ая», «ая») до («ба», «ба», «ба»), а "".join склеивает каждую в строку. Обычные ключи дорожают вдвое на каждом удвоении, подобранные — почти вчетверо: все они в одной корзине, и $i$-я вставка просматривает $i - 1$ предшественников. Это сумма $0 + 1 + \ldots + (n-1) = \frac{n(n-1)}{2}$ из главы 13 — квадрат, на который GTA тратила полторы минуты загрузки. Только здесь его вызвали нарочно. Последняя строка прикидывает, сколько займут 200 тысяч ключей, как в докладе: минуты на один запрос.

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

Встроенное множество строками «ая» и «ба» не возьмёшь: хеш строк у него устроен иначе, об этом третий раунд. Зато теперь можно разгадать загадку из начала главы. Хеш целого числа Python не перемешивает: это остаток от деления на $p = 2^{61} - 1$. Так проще и быстрее, и так легко выполнить договор хеша для 1 и 1.0. Второй список в загадке — числа $0, p, 2p, 3p, \ldots$

У всех чисел второго списка хеш ноль. Все шестнадцать тысяч хотят одну и ту же ячейку и ищут свободную одним и тем же маршрутом: $i$-е число проходит мимо всех $i - 1$ предшественников. Тот же квадрат, что в нашей картотеке, только во встроенном множестве. Бояться множеств из-за этого не стоит, но помнить надо: если программа складывает в словарь или множество то, что прислал посторонний человек, — числа из запроса, имена полей, слова из письма, — время её работы выбирает он. Самая простая защита та, что PHP выпустил через две недели после доклада: ограничить количество. С версии 5.3.9 PHP по умолчанию принимает не больше тысячи полей в одном запросе.

Раунд 3. Защита: соль

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

Соль в начале не помогла ничем: все восемь подобранных строк по-прежнему в одной корзине, при любой соли. И понятно почему: «ая» и «ба» дают одинаковую прибавку к хешу, что бы ни было накоплено до них. Соль, которая только сдвигает все хеши, ничего не перемешивает. Вторая попытка — сделать секретом само основание, на которое умножаем: вместо 31 взять случайное число из огромного промежутка, а считать по модулю большого простого $p$. Теперь «ая» и «ба» совпадают, только если $1072 \cdot b + 1103 = 1073 \cdot b + 1072$, то есть если основание $b$ равно 31. При случайном $b$ восемь строк разбежались по восьми корзинам. Можно доказать, что так будет для любых двух строк, какие бы ни выбрал нападающий.

Для строк из 24 букв и $p = 2^{61} - 1$ это около одного шанса на $10^{17}$. Нападающий может прислать какие угодно ключи, но не знает основания — и не может угадать, какие из них столкнутся. Правда, у этой защиты есть щель: противник видит, как ведёт себя таблица, — в каком порядке сервер возвращает ключи, сколько времени отвечает, — и по таким наблюдениям иногда удаётся вычислить секрет. Поэтому в рабочих хеш-функциях соль прячут внутрь функции, которую считают криптографически стойкой: по её ответам секрет не восстановить даже тому, кто видит миллионы хешей. Так и сложилась история Python.

Проверьте сами. Запустите ячейку дважды и сравните хеши.

Первая строка меняется от запуска к запуску: соль выбирается заново при каждом старте интерпретатора. Вторая подтверждает, что в песочнице работает SipHash-1-3 со 128 битами соли. Дальше ячейка запускает четыре отдельных интерпретатора Python, передавая каждому переменную окружения PYTHONHASHSEED: модуль subprocess запускает другую программу и забирает её вывод, а sys.executable — путь к самому интерпретатору. При random у каждого запуска своя соль: другой хеш и другой порядок в множестве. При 0 соль выключена, и хеш одинаковый. Так делают, когда нужно воспроизвести ошибку, которая зависит от порядка.

Соль — не единственный ответ. Java пошла другим путём: в Java 8 (2014) цепочка, которая выросла слишком длинной (больше восьми записей), превращается в сбалансированное дерево поиска. Тогда даже в корзине, куда нападающий собрал все ключи, вместо $n$ сравнений поиск стоит около $\log n$. Что это за деревья и почему они не вырождаются, — следующая глава. В итоге у защиты три линии: соль, чтобы противник не мог подобрать коллизии; ограничение, чтобы он не мог прислать миллион ключей; и устройство, у которого даже худший случай не катастрофа.

Задачи

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

Напишите класс HashMap — хеш-таблицу с цепочками. Атрибут buckets — список корзин, каждая корзина — список пар (ключ, значение); новая таблица начинается с восьми пустых корзин. Запись с ключом key лежит в корзине hash(key) % len(self.buckets). Методы: put(key, value) — положить или заменить значение; get(key, default=None) — значение или default, если ключа нет; len(m) — число записей; key in m — есть ли ключ. Когда записей становится больше, чем корзин, таблица переезжает во вдвое большую. Тесты проверяют, что каждая запись лежит в своей корзине, что корзин не меньше, чем записей, и что двести тысяч ключей кладутся и находятся быстрее трёх секунд. Встроенными dict и set внутри класса не пользуйтесь — это не проверяется, но тогда задача теряет смысл.

key in m Python превращает в вызов m.__contains__(key), а len(m) — в m.__len__(). Это те же специальные методы, что в главе 12. Подумайте, как отличить «ключа нет» от «ключ есть, а значение — None».

В конце put, если self.size > len(self.buckets), создайте вдвое больше пустых корзин и разложите в них все старые записи заново. Дописать пустые корзины в конец списка мало: от длины списка зависит номер корзины, и старые записи окажутся не там, где их будут искать.

Переезд перебирает все записи, но случается всё реже: после переезда с $m$ на $2m$ корзин следующий наступит только через $m$ вставок. Это те же монетки, что у динамического массива, и вставка стоит $O(1)$ амортизированно. __contains__ нельзя написать как self.get(key) is not None: ключ со значением None такая проверка сочтёт отсутствующим.

В PHP 5 хеш строки считался функцией, которую в докладе 2011 года называли DJBX33A: начать с 5381, на каждой букве умножать на 33 и прибавлять её код. Напишите collide(k) — список из k разных строк с одинаковым хешем djb33. Строки должны походить на имена полей формы: только латинские буквы (a–z, A–Z) и не длиннее 40 символов. Тесты просят до пяти тысяч строк и дают на это секунду. Перебирать случайные строки в надежде на совпадение бесполезно: хеш 32-битный, и даже по парадоксу дней рождения первая коллизия ждёт вас где-то на восьмидесятитысячной строке, а нужны тысячи строк с одним и тем же хешем.

Начните с двух двухбуквенных строк с одинаковым хешем — как «ая» и «ба» для умножения на 31. Для 33 первую букву надо сдвинуть на единицу вперёд, а вторую — на 33 назад. Строчная латинская буква минус 33 — почти всегда заглавная: код «b» — 98, а 98 − 33 = 65 — это «A».

Вместо счёта в уме можно поручить поиск словарю: переберите все двухбуквенные строки из латинских букв (их $52^2 = 2704$) и складывайте их в словарь «хеш → строка». Как только хеш уже встречался — пара найдена.

Дальше — блоки, как в кузнице: itertools.product([x, y], repeat=n) даёт $2^n$ строк. Возьмите $n$ такое, чтобы $2^n \ge k$, и верните первые $k$.

Словарь находит пару за несколько десятков шагов — первой ему попадается пара «ab» и «bA». Это тот же приём, что в задаче о паре на сумму из главы 13: вместо того чтобы сравнивать каждую строку с каждой, спрашиваем у таблицы, не было ли уже такого хеша. Хеш-таблицей ломаем хеш-таблицу. Пять тысяч строк — это 13 блоков по две буквы, 26 символов, а 200 тысяч, как в докладе, — 18 блоков. От такой атаки DJBX33A не спасает и случайное начальное значение вместо 5381: эквивалентные блоки дают одинаковую прибавку при любом накопленном хеше, как «ая» и «ба» в разделе о соли.

Робот-пылесос записывает свой путь в журнал JSON — список точек [x, y]; после json.loads каждая точка — список из двух чисел. Напишите first_repeat(points): номер первой точки, в которой робот уже бывал раньше, или −1, если он нигде не был дважды. Например, для [[0, 0], [1, 0], [1, 1], [0, 1], [0, 0], [1, 0]] ответ 4: в точку [0, 0] робот вернулся на четвёртом шаге (нумерация с нуля). Сам журнал менять нельзя. В тестах путь бывает длиной двести тысяч точек.

Заготовка верна, но p in seen перебирает список: для пути из двухсот тысяч точек это двадцать миллиардов сравнений. Нужно множество.

Множество не примет точку-список: unhashable type: 'list'. Превратите точку в кортеж: tuple(p). Это та же пара координат, только неизменяемая.

Здесь в трёх строках вся история про ключи: списки нехешируемы, потому что изменяемы, а кортеж с теми же числами хешируется и годится в ключ. Данные из JSON и из сети почти всегда приходят списками, так что tuple(...) перед множеством — обычный рабочий приём. Время — $O(n)$.

Банк раскладывает номера карт по m ящикам картотеки — например, по файлам на диске. Напишите bucket(number, m): номер ящика от 0 до m - 1 для номера карты — строки из шестнадцати цифр, иногда с пробелами. Пробелы на ящик не влияют. Ящик номера не должен меняться от запуска к запуску: картотека живёт на диске годами. И ящики должны заполняться равномерно — тесты раскладывают десятки тысяч номеров карт с верной контрольной цифрой по 10, 97 и 1000 ящикам. В заготовке хеш-функцией служит сумма Луна из главы 5. Запустите тесты и разберитесь, что с ней не так.

Вспомните, что значит «номер карты верен» в главе 5: его сумма Луна делится на 10. В какой ящик при m = 10 попадут все верные номера?

И при других m сумме Луна не хватает размаха: у шестнадцати цифр она не больше 144, так что из тысячи ящиков по меньшей мере 855 останутся пустыми. Хешировать нужно сам номер, все его цифры. Встроенный hash от строки не подойдёт: с солью ящик будет меняться при каждом запуске.

Номер из одних цифр — обычное число. Остаток от деления самого номера на m зависит от всех его цифр сразу.

Сумма Луна — прекрасная контрольная сумма и никудышный хеш, и по одной и той же причине. Её придумали так, чтобы у всех верных номеров она давала одно и то же — ноль по модулю 10, — а хеш-функция должна разбрасывать ключи как можно сильнее. Контрольная цифра нарочно связывает цифры номера, и любая функция, которая «замечает» эту связь, сваливает номера в кучу. Остаток от самого номера связь не замечает и не зависит от соли, поэтому картотека переживёт перезапуск. А вот poly31 по цифрам, такой хороший на словах «Войны и мира», на номерах одного выпуска подряд спотыкается: из тысячи ящиков полторы сотни остаются пустыми, а в самом полном втрое больше среднего. Хеш-функцию проверяют на тех ключах, которые ей придётся раскладывать.

Куда дальше

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

Чтобы найти слова от «мир» до «мирный» или слово, которое по алфавиту идёт сразу за «наташа», словарю пришлось перебрать все пятьдесят тысяч ключей: хеш «мира» ничего не говорит о том, где лежит «мирный». Тысяча таких вопросов — уже секунды. Отсортированный список отвечал бы быстро, но каждое новое слово в нём пришлось бы вставлять в середину, сдвигая хвост, — это $O(n)$ из главы 14. Хеш-таблица не умеет «все имена от А до В» и «следующий по алфавиту». Нужна структура, которая хранит ключи по порядку, ищет почти так же быстро, как хеш-таблица, и при этом дёшево принимает новые ключи. Её придумали в 1962 году в Москве два математика. Она растёт, как дерево, и её, как дерево, приходится подрезать. Об этом — следующая глава.