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