Когда в 2021 году начинающий компьютерный специалист из Университета Ратгерса, Эндрю Крапивин, решил «просто ради развлечения» прочитать научную статью «Tiny Pointers», он и представить не мог, что это изменит не только его дальнейшую карьеру, но и всю концепцию работы с хеш-таблицами, существующую последние 40 лет. Обычно фундаментальные догмы в информатике поколебать непросто – эти структуры давно изучены вдоль и поперёк. Однако Крапивин сумел обнаружить способ, благодаря которому операции поиска и вставки могут выполняться гораздо быстрее, чем считалось возможным.
Почему хеш-таблицы так важны
Хеш-таблицы – один из краеугольных камней компьютерных наук. Они позволяют:
🔑 хранить данные;
🔑 искать нужные элементы;
🔑 добавлять и удалять записи за (обычно) амортизированное O(1) время.
Но в действительности «одна операция за константу» – это скорее удобная абстракция. На практике при высоком заполнении хеш-таблицы время на поиск свободного места или конкретного элемента может расти. Если мы говорим, что таблица заполнена на 99%, это означает, что свободные ячейки можно пересчитать на пальцах, и найти одну из них становится всё сложнее.
“Крошечные указатели” и идея миниатюризации
Изначально статья «Tiny Pointers - Миниатюрные указатели» (авторы – Мартин Фарач-Колтон и Уильям Кузмаул) была посвящена экономии памяти за счёт компактных указателей (pointers), которые указывают на расположение элемента в памяти. Однако Крапивин:
🧩 обратил внимание, что, если ещё больше уменьшить размер этих «стрелочек», можно выиграть в скорости;
🧩 придумал способ переорганизации данных, которым эти указатели пользуются;
🧩 заметил, что его новый тип хеш-таблицы ведёт себя вовсе не так, как классические реализации.
Когда он показал прототип своему бывшему научному руководителю Мартину Фарач-Колтону, тот, по собственному признанию, сначала не поверил в эффективность найденного решения. Слишком много ученых и специалистов последние десятилетия изучали хеш-таблицы, чтобы кто-то «просто так» открыл нечто фундаментально новое.
Опровержение 40-летней гипотезы
В 1985 году лауреат премии Тьюринга Эндрю Яо высказал предположение (так называемая «гипотеза Яо»), что при очень высоком заполнении хеш-таблиц, если использовать определённый класс «равномерных» методов проб (uniform probing), невозможно выйти за определённые пределы по времени выполнения операций. Говоря упрощённо, при 99% заполнении (или даже 99.9%) приходится в среднем перебирать пропорционально величине xx позиций (где xx показывает, насколько таблица близка к 100% заполнению).
Новая работа Крапивина совместно с Фарач-Колтоном и Кузмаулом продемонстрировала, что можно не следовать механизму равномерного пробирования. Итог: время операции поиска и вставки (в худшем случае!) становится пропорционально (𝑙𝑜𝑔 𝑥)², что значительно быстрее гипотетически предсказанного Яо линейного роста. Более того, исследователи доказали, что (𝑙𝑜𝑔 𝑥)² – это и есть оптимальная оценка для рассматриваемого класса хеш-таблиц. Фактически, они «обнулили» гипотезу, устоявшую более 40 лет.
Ещё более удивительное открытие
Новые хеш-таблицы могут работать:
🔥 среднестатистически быстрее, чем «логарифмическое» время, которое Яо доказал для «жадных» (greedy) вариантов размещения элементов;
🔥 в некоторых случаях – с постоянным (константным) средним временем доступа, которое никак не зависит от того, насколько плотно таблица забита.
Это прозвучало как сенсация даже для самих авторов. Представьте: 99.9% заполнения, а среднее время поиска элемента примерно то же, что и при 10% заполнении!
Технические детали реализации
Как же это возможно? Основная идея:
💡 Нестандартная схема «проб»: вместо равномерного (uniform) просмотра потенциальных позиций, используется особый алгоритм, позволяющий «пропускать» заведомо занятые или «нужные» слоты.
💡 Минимизация памяти под «указатели»: «крошечные указатели» экономят пространство, что даёт «бонус» при работе процессорных кешей. Меньше кеш-промахов – быстрее поиск.
💡 Гибкое размещение элементов: в отличие от жадного подхода, позволяющего заполнять ячейку, как только найдётся первая свободная, новая стратегия может анализировать дополнительные варианты (своего рода «разведка»), делая размещение более «равномерным».
На аппаратном уровне это может приводить к заметному выигрышу в микросекундах для каждой операции, а в большом масштабе (миллионы обращений в секунду) такая экономия способна вылиться в существенный прирост производительности серверов.
Личное мнение автора
На мой взгляд, самое впечатляющее здесь не только то, что молодому учёному-аспиранту удалось «переписать» классическую теорию, но и то, что он сделал это в процессе, казалось бы, побочного исследования компактных указателей. Это напоминает, как во многих прорывах – путь к серьёзному открытию пролегает не через прямой поиск, а через интерес к казалось бы второстепенной задаче. Любопытство иногда оказывается движущей силой более мощной, чем целенаправленное планирование.
Конечно, до реальной интеграции таких «супербыстрых» хеш-таблиц в промышленные базы данных ещё предстоит изучить массу практических нюансов. Вдобавок, всегда сохраняются вопросы устойчивости и предсказуемости поведения при разных паттернах нагрузки. Однако сам факт столь серьёзного смещения границ «максимально возможной скорости» демонстрирует, что в нашей области ещё довольно простора для неожиданных открытий. И это воодушевляет!
Ссылка на новость
🔗 Основная новость:
Undergraduate Upends a 40-Year-Old Data Science Conjecture
Возможно, благодаря этому открытию мы ещё станем свидетелями совершенно новых подходов к работе с большими данными. Ведь каждый раз, когда мы ломаем устоявшуюся теорию, мы открываем себе дорогу к неизведанным областям и возможностям!