Студент Кембриджского университета Эндрю Крапивин случайно сделал открытие, которое опровергло гипотезу, считавшуюся неоспоримой 40 лет. Его работа показала, что хеш-таблицы могут работать быстрее, чем предполагалось, что потенциально может ускорить интернет-сервисы.
Хеш-таблицы — это структуры данных, ускоряющие поиск информации. Они используются в интернет-магазинах, почтовых сервисах и телефонных книгах. Однако считалось, что их быстродействие имеет предел. В 1985 году информатик Эндрю Яо, впоследствии ставший лауреатом премии Тьюринга, доказал, что при высокой заполненности таблиц поиск свободной ячейки требует времени, пропорционального их загруженности. То есть если хеш-таблица заполнена на 99%, то, вероятно, придется проверить около 100 разных позиций, чтобы найти свободное место.
До недавних пор это утверждение не оспаривалось, пока Эндрю Крапивин случайно не нашел способ ускорить процесс.
В конце 2021 года будучи на тот момент студентом Ратгерского университета, он наткнулся на статью об уменьшении размеров указателей в памяти компьютера. Вернувшись к ней через несколько лет, он понял, что хранение данных можно оптимизировать. Однако для этого нужно улучшить саму организацию данных, к которым указатели будут направлять.
Исследуя хеш-таблицы, он неожиданно для себя создал их новый тип, работающий значительно быстрее традиционных.
Крапивин обратился к своему преподавателю профессору Мартину Фарах-Колтону, который сначала воспринял идею скептически. Он попросил своего коллегу Уильяма Кузмала из Университета Карнеги — Меллона проверить работу Крапивина, и тот сразу понял, что речь идет о настоящем открытии.
Кузмал сказал Крапивину, что он не просто создал новую хеш-таблицу, а попросту опроверг гипотезу, которую никто не решался оспаривать. Самое поразительное заключается в том, что Крапивин просто не знал о работе Яо. Вероятно, именно поэтому его не сдерживала общепринятая точка зрения.
Теперь Крапивин является аспирантом Кембриджа. Вместе с Фарах-Колтоном и Кузмалом он подготовил статью, доказав, что их метод не только делает поиск быстрее, но и позволяет искать данные за постоянное время, независимо от того, насколько таблица заполнена.
Хотя открытие вряд ли приведет к немедленным изменениям, в перспективе метод Крапивина и его коллег может ускорить многие процессы в интернете.
«Мы никогда не можем предугадать, как теоретическое открытие преобразится в практические результаты. Учитывая, что хеш-таблицы сегодня используются везде – от поисковых систем до баз данных, – любое их усовершенствование может иметь далеко идущие последствия», – отмечает Алекс Конвей из издания Cornell Tech.
