Пересмотр алгоритмов хеш-таблиц: студент опроверг 40-летнюю гипотезу

В мире алгоритмов произошло знаменательное событие, которое может изменить наше понимание хеш-таблиц. Эндрю Крапивин (студент Ратгерского университета), опроверг гипотезу, которую учёные считали верной на протяжении 40 лет.

Работа хеш-таблицы основана на хеш-функции, которая преобразует ключ в числовой индекс, указывающий на место в массиве, где хранится или должно храниться значение. Проблема возникает, когда разные ключи дают одинаковый индекс — это явление называется коллизией.

Существует два основных метода решения проблемы коллизий:

- Метод цепочек (chaining) — при коллизии элементы с одинаковым хеш-значением помещаются в связный список или другую вспомогательную структуру данных. Этот метод требует дополнительной памяти для хранения указателей.
- Открытая адресация (open addressing) — использует только один массив без дополнительных структур. При коллизии алгоритм ищет другую свободную ячейку в массиве по определённой стратегии.

Открытая адресация имеет ряд преимуществ:

- Более эффективное использование памяти без накладных расходов на указатели
- Лучшая локальность данных, что улучшает производительность кэша процессора
- Отсутствие необходимости в динамическом выделении памяти
- Предсказуемые характеристики производительности

Классические стратегии поиска в открытой адресации

В хеш-таблицах с открытой адресацией используются различные стратегии для определения последовательности проверки ячеек при коллизии:

Линейное пробирование — последовательная проверка следующих ячеек (h(key) + 1, h(key) + 2, ...)
Квадратичное пробирование — проверка ячеек с квадратичным смещением (h(key) + 1², h(key) + 2², ...)
Двойное хеширование — использование второй хеш-функции для определения шага
Случайное пробирование — применение псевдослучайной последовательности для выбора следующей ячейки

Гипотеза Яо и её опровержение

В 1985 году Эндрю Яо, будущий лауреат премии Тьюринга, сформулировал гипотезу, согласно которой в хеш-таблицах с определённым набором свойств оптимальной стратегией поиска элемента или свободного места является случайное пробирование. Он также утверждал, что в наихудшем случае, когда таблица почти полностью заполнена (на 99%), для поиска последнего свободного места потребуется время, пропорциональное степени заполненности (x).

Эндрю Крапивин, работая над совершенно другим проектом, случайно создал новый тип хеш-таблицы, который не использовал случайное пробирование. Неожиданным результатом стало то, что для этой новой хеш-таблицы время, необходимое для наихудшего случая, оказалось пропорциональным не x, а (log x)² — что значительно эффективнее.

Дополнительное открытие о "нежадных" хеш-таблицах

Продолжая исследования с коллегами Мартином Фарач-Колтоном и Уильямом Кушмаулем, Крапивин сделал еще одно важное открытие, касающееся другого аспекта хеш-таблиц.

Яо в своей работе 1985 года доказал, что для так называемых "жадных" хеш-таблиц (где новый элемент всегда помещается в первую доступную ячейку) среднее время поиска не может быть лучше log x. Это было математически доказанное ограничение для данного класса хеш-таблиц.

Крапивин и его коллеги решили исследовать, действует ли это ограничение для "нежадных" хеш-таблиц — тех, в которых новый элемент может быть помещен не обязательно в первую доступную ячейку. Они обнаружили, что для определенного типа "нежадных" хеш-таблиц среднее время поиска может быть постоянным и вообще не зависеть от степени заполненности таблицы.

Значение открытия

Хотя непосредственные практические применения этих теоретических прорывов могут не проявиться немедленно, их фундаментальное значение трудно переоценить. Хеш-таблицы используются повсеместно, и улучшение их производительности, особенно при высокой заполненности, может привести к существенной оптимизации многих систем.

🫥 Cross Join
⠀