Молодой математик из США опроверг теорию, которая считалась незыблемой 40 лет

Каждый раз, когда вы открываете список контактов в телефоне, ищете товар в интернет-магазине или проверяете электронную почту, быстро извлекать нужную информацию вам помогают особые структуры данных — хеш-таблицы. Именно благодаря им современный интернет, по сути, работает так, как мы привыкли. Но у быстродействия хеш-таблиц, как считалось, есть предел. Случайное открытие молодого аспиранта Эндрю Крапивина перевернуло представление о возможностях этого инструмента. Научный журналист и автор телеграм-канала «Лайфлонг муки» Илья Кабанов объясняет, как устроены хеш-таблицы, чем важен успех Крапивина и повлияет ли он на эффективность работы с данными в будущем, передает meduza.io

Для начала — чуть подробнее о том, что такое хеш-таблицы и зачем они нужны

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

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

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

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

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

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

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

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

Цель разработчиков — уменьшить сложность поиска, особенно в условиях, когда таблица почти полностью заполнена. В обывательских терминах мы бы определяли заполненность в процентах — скажем, таблица заполнена на 50% или 80%. В свою очередь исследователи используют величину x, чтобы показать, насколько таблица близка к 100% заполнения. Если x равен 100, то таблица заполнена на 99%, а если x равен 1000, то на 99,9%.

В своей работе 1985 года информатик Эндрю Яо, позже ставший лауреатом премии Тьюринга, доказал, что для хеш-таблиц с открытой адресацией лучший способ поиска элемента или пустой ячейки — это случайный перебор возможных мест. Такой подход называется универсальным хешированием. Яо также предположил, что в худшем случае, когда необходимо найти последнюю свободную ячейку, нельзя обойтись без затрат времени, пропорциональных x. Если хеш-таблица заполнена на 99%, то, вероятно, придется проверить около 100 разных позиций, чтобы найти свободное место.

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

Что именно смог доказать Крапивин и почему открытие оказалось случайным

В конце 2021 года на тот момент студент Ратгерского университета Эндрю Крапивин (в своей недавней презентации исследователь представляется именно так; в 2020 году в беседе с жившим в Украине дедом он называл себя Андреем) случайно наткнулся на публикацию про уменьшение размеров указателей в памяти компьютера. Через несколько лет он вернулся к этой статье, перечитал ее и понял, что можно добиться того, что указатели будут занимать еще меньше памяти. Однако для этого нужно улучшить саму организацию данных, к которым указатели будут направлять.

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

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

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

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

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