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