Фундаментальная проблема хеш-таблиц получила неожиданное решение.
Осенью 2021 года студент Ратгерского университета Эндрю Крапивин наткнулся на научную статью «Tiny Pointers» («Крошечные указатели»), которая впоследствии изменила его жизнь. Тогда начинающий ученый лишь мельком просмотрел публикацию, но спустя два года, когда он решил детально изучить ее «просто ради интереса», это перевернуло один из фундаментальных принципов компьютерной науки.
Изучая статью, Крапивин задумался над тем, как сделать указатели еще компактнее, чтобы они занимали меньше памяти. Эти элементы играют важную роль в работе компьютера: они как дорожные знаки направляют систему к месту хранения данных. Чем меньше места занимает каждый такой «знак», тем эффективнее используется память.
Однако для создания более компактных указателей требовалось по-новому организовать саму информацию, к которой они ведут. Студент обратился к хеш-таблицам — одному из фундаментальных методов хранения данных в компьютерных системах. Хеш-таблица работает как умное оглавление: она не просто хранит определенные материалы, но и позволяет молниеносно находить нужный элемент, удалять его или добавлять новый.
В процессе экспериментов Крапивин случайно изобрел новый тип хеш-таблицы. Ее уникальность заключалась в том, что она находила нужные элементы значительно быстрее существующих вариантов, совершая меньше шагов для поиска.
Мартин Фарач-Колтон, один из авторов исходной статьи про «крошечные указатели» и бывший преподаватель Крапивина, поначалу отнесся к открытию скептически. Хеш-таблицы изучаются с начала 1950-х годов и считаются одной из самых исследованных структур в компьютерной науке. Предложенное улучшение казалось слишком значительным для столь изученной области. Чтобы проверить идею студента, он обратился к коллеге Уильяму Кушмаулу из Университета Карнеги-Меллон.
Реакция Кушмаула поразила всех: оказалось, что Крапивин не просто улучшил хеш-таблицу, а опроверг научное предположение, которому верили 40 лет. В 1985 году известный информатик Эндрю Яо, будущий лауреат премии Тьюринга, выдвинул гипотезу о предельной скорости работы хеш-таблиц определенного типа.
Яо в своей работе утверждал, что наиболее эффективный способ поиска в хеш-таблице – это метод случайного перебора позиций: система проверяет ячейки в произвольном порядке до тех пор, пока не найдет нужный элемент или свободное место. Согласно его теории, время поиска неизбежно растет вместе с заполненностью таблицы. Если выразить заполненность через параметр x (где x=100 означает, что таблица заполнена на 99%, а x=1000 – на 99,9%), то в худшем случае придется проверить количество ячеек, пропорциональное x.
Студент же, работая над улучшением «крошечных указателей», разработал принципиально новый способ организации данных. Вместо случайного перебора его метод использовал особый алгоритм, который определял оптимальные позиции для размещения и поиска элементов. Так даже в самых сложных случаях, при почти полном заполнении таблицы, время операций оказалось пропорционально (log x)², что означает гораздо более медленный рост по сравнению с линейной зависимостью в методе Яо.
То есть при заполненности таблицы на 99,9% (x=1000) классическому методу в худшем случае потребуется проверить около тысячи позиций. Новый алгоритм справится с той же задачей примерно за 100 операций. С ростом заполненности таблицы эта разница становится все более существенной.
Но главный сюрприз ждал впереди. В той же работе 1985 года Яо исследовал среднее время поиска элементов в хеш-таблицах, использующих так называемый «жадный» алгоритм. Этот подход требует помещать новые элементы в первую доступную позицию, как если бы вы заполняли зрительный зал строго по порядку, начиная с первого ряда. Яо доказал, что в таких таблицах среднее время поиска не может быть меньше log x.
Авторы новой работы решили проверить, действует ли это ограничение для хеш-таблиц с другими алгоритмами размещения данных. Они создали версию, где элементы распределялись по более сложным правилам, и получили удивительный результат: среднее время поиска оказалось постоянным – оно вообще не зависело от заполненности таблицы.
«Такой результат стал неожиданностью даже для нас, — рассказал Фарач-Колтон . — Мы и представить не могли, что время поиска может оставаться постоянным независимо от заполненности».
«Это открытие могло бы ускользать от нас еще сорок лет, — добавил Сепехр Ассади из Университета Ватерлоо. — Оно заставляет нас совершенно по-новому взглянуть на возможности хеш-таблиц».
Хотя открытие пока не имеет прямого практического применения, его значение для информатики трудно переоценить. «Глубокое понимание базовых структур данных имеет огромное значение, — отметил Алекс Конвей из Cornell Tech. — Мы никогда не можем предугадать, как теоретическое открытие преобразится в практические результаты. Учитывая, что хеш-таблицы сегодня используются везде — от поисковых систем до баз данных, — любое их усовершенствование может иметь далеко идущие последствия».