Молодой учёный-информатик и двое его коллег показали, что поиск в структурах данных, называемых хэш-таблицами, можно осуществить гораздо быстрее, чем считалось ранее
Осенью 2021 года Эндрю Крапивин, студент Ратгерского университета, наткнулся на статью, которая впоследствии изменит его жизнь. В то время Крапивин не придал этому значения. Но два года спустя, когда он наконец выделил время, чтобы просмотреть статью («просто так», как он выразился), его усилия привели к переосмыслению широко используемого инструмента в компьютерных науках.
Название работы — «Крошечные указатели» — относилось к похожим на стрелки сущностям, которые могут направить вас к фрагменту информации или элементу в памяти компьютера. Вскоре Крапивин придумал, как можно ещё сильнее миниатюризировать указатели, чтобы они занимали меньше памяти. Однако для этого ему понадобился лучший способ организации данных, на которые будут указывать указатели.
Он обратился к распространённому подходу к хранению данных, известному как хэш-таблица. Но в процессе работы Крапивин понял, что изобрёл новый тип хэш-таблицы, которая работает быстрее, чем ожидалось — на поиск конкретных элементов требуется меньше времени и шагов.
Мартин Фарач-Колтон, соавтор статьи «Крошечные указатели» и бывший профессор Крапивина в Ратгерсе, поначалу скептически отнёсся к новому дизайну Крапивина. Хэш-таблицы — одна из наиболее тщательно изученных структур данных во всей компьютерной науке; это достижение звучало слишком хорошо, чтобы быть правдой. Но чтобы убедиться в этом, он попросил своего частого соавтора (и соавтора «Крошечных указателей») Уильяма Кушмаула из Университета Карнеги-Меллон проверить изобретение своего студента. Кузмаул отреагировал по-другому. «Ты не просто придумал крутую хэш-таблицу, — вспоминает он, говоря Крапивину. «Ты фактически полностью уничтожил гипотезу 40-летней давности!»
Вместе Крапивин (ныне аспирант Кембриджского университета), Фарач-Колтон (ныне сотрудник Нью-Йоркского университета) и Кушмаул продемонстрировали в статье, опубликованной в январе 2025 года, что новая хэш-таблица действительно может находить элементы быстрее, чем считалось возможным. Тем самым они опровергли гипотезу, которая долгое время считалась верной.
«Это очень важная работа», — говорит Алекс Конвей из Корнельского технологического института в Нью-Йорке. «Хэш-таблицы — одна из старейших структур данных, которые у нас есть. И они по-прежнему являются одним из самых эффективных способов хранения данных». Тем не менее, по его словам, остаются открытые вопросы о том, как они работают. «Эта статья даёт удивительные ответы на некоторые из них».
Хэш-таблицы получили широкое распространение в вычислительной технике отчасти благодаря своей простоте и удобству использования. Они предназначены для того, чтобы пользователи могли делать ровно три вещи: «запрашивать» (искать) элемент, удалять элемент или вставлять его в пустой слот. Первые хэш-таблицы появились ещё в начале 1950-х годов, и с тех пор компьютерные учёные изучают и используют их. Помимо прочего, исследователи хотели выяснить предельную скорость выполнения некоторых из этих операций. Например, насколько быстрым может быть новый поиск или вставка?
Ответ обычно зависит от количества времени, которое требуется для поиска пустого места в хэш-таблице. Это, в свою очередь, обычно зависит от того, насколько заполнена хэш-таблица. Заполненность можно описать в общем процентном соотношении — эта таблица заполнена на 50 %, та — на 90 %, — но исследователи часто имеют дело с гораздо более полными таблицами. Поэтому вместо этого они могут использовать целое число, обозначаемое x, чтобы указать, насколько близка хэш-таблица к 100-процентному заполнению. Если x равно 100, то таблица заполнена на 99%. Если x равно 1000, то таблица заполнена на 99,9%. Эта мера заполненности даёт удобный способ оценить, сколько времени должно занять выполнение таких действий, как запросы или вставки.
Исследователи давно знают, что для некоторых обычных хэш-таблиц ожидаемое время, необходимое для выполнения наихудшей из возможных вставок — помещения элемента, скажем, в последнее оставшееся свободным место — пропорционально x. «Если ваша хэш-таблица заполнена на 99%, — говорит Кушмаул, — то вполне логично, что вам придётся просмотреть около 100 различных позиций, чтобы найти свободный слот».
В статье 1985 года учёный-информатик Эндрю Яо, который впоследствии получил премию А.М. Тьюринга, утверждал, что среди хэш-таблиц с определённым набором свойств лучшим способом найти отдельный элемент или пустое место является случайный перебор потенциальных мест — подход, известный как равномерное зондирование. Он также заявил, что в худшем случае, когда вы ищете последнее оставшееся свободное место, вы никогда не сможете сделать меньше операций, чем x. В течение 40 лет большинство компьютерных учёных полагали, что гипотеза Яо верна.
Крапивина не останавливало общепринятое мнение по той простой причине, что он не знал о нём. «Я сделал это, не зная о гипотезе Яо», — сказал он. Его исследования с крошечными указателями привели к созданию нового типа хэш-таблицы — той, которая не полагается на равномерное зондирование. И для этой новой хэш-таблицы время, необходимое для наихудших запросов и вставок, пропорционально (log x)2 — намного быстрее, чем x. Этот результат прямо противоречит гипотезе Яо. Фарач-Колтон и Кушмаул помогли Крапивину показать, что (log x)2 — это оптимальное, непреодолимое ограничение для популярного класса хэш-таблиц, о котором писал Яо.
«Этот результат прекрасен тем, что в нём рассматривается и решается такая классическая проблема», — сказал Гай Блеллох из Карнеги-Меллона.
«Они не просто опровергли гипотезу Яо, но и нашли лучший из возможных ответов на его вопрос», — говорит Сепехр Ассади из Университета Ватерлоо. «Могло бы пройти ещё 40 лет, прежде чем мы бы узнали правильный ответ».
Помимо опровержения гипотезы Яо, новая статья содержит ещё более поразительный, по мнению многих, результат. Он относится к смежной, хотя и несколько иной ситуации: В 1985 году Яо рассматривал не только наихудшее время выполнения запросов, но и среднее время выполнения всех возможных запросов. Он доказал, что хэш-таблицы с определёнными свойствами — включая те, которые обозначены как «жадные», что означает, что новые элементы должны быть помещены в первое доступное место — никогда не смогут достичь среднего времени лучше, чем log x.
Фарач-Колтон, Крапивин и Кушмаул хотели выяснить, применимо ли это ограничение к нежадным хэш-таблицам. Они показали, что нет, предоставив контрпример — нежадную хэш-таблицу со средним временем запроса, которое намного, намного лучше log x. Фактически, оно вообще не зависит от x. «Вы получаете число, — говорит Фарач-Колтон, — которое является просто константой и не зависит от того, насколько заполнена хэш-таблица». Тот факт, что можно добиться постоянного среднего времени выполнения запроса, независимо от заполненности хэш-таблицы, оказался совершенно неожиданным — даже для самих авторов.
Результаты работы команды могут не найти немедленного применения, но это не главное, говорит Конвей. «Важно лучше понимать подобные структуры данных. Неизвестно, когда такой результат откроет что-то, что позволит вам добиться большего на практике».
