hopscotch-map, быстрая реализация хеш-таблицы на C++ с методом открытой адресации

Библиотека hopscotch-map, это C++ реализация быстрых хеш-таблиц (maps и sets) с использованием методов открытой адресации и hopscotch-hashing для разрешения коллизий. Структура данных оптимизирована для работы с кешем процессора и в большинстве случаев показывает лучшую производительность, чем std::unordered_map, при этом используя меньше памяти, чем google::dense_hash_map, и предоставляя больше функциональности.

Библиотека предоставляет основные классы: tsl::hopscotch_map и tsl::hopscotch_set (используют степени двойки для роста), а также tsl::hopscotch_pg_map и tsl::hopscotch_pg_set (используют простые числа). Последняя пара лучше справляется с плохими функциями хеширования благодаря более равномерному распределению. Дополнительно есть вариант tsl::bhopscotch_* с гарантией O(log n) для поиска и удаления, устойчивый к DoS-атакам на хеш-таблицу. Однако стандартные tsl::hopscotch_* в большинстве случаев достаточны и показывают лучшую общую производительность.

Библиотека реализована как header-only и поддерживает: гетерогенные поиски (поиск по типу, отличному от ключа), хранение значений хешей для ускорения поиска, move-only и не-default-constructible ключи/значения, отключение исключений (работает с флагом -fno-exceptions), работу с предварительно вычисленными хешами для поиска. API близок к std::unordered_map, но с некоторыми отличиями: итераторы при вставке инвалидируются иначе, значения в map не являются модифицируемыми через operator*, требуется вызов метода value() для изменения. Поддерживаются несколько политик роста таблицы (степени двойки по умолчанию, простые числа, произвольный множитель роста), позволяющих выбирать оптимальную для конкретного случая.

Ключевые факты

Hopscotch-map показывает лучшую производительность чем std::unordered_map благодаря оптимизации для кеша процессора и использованию открытой адресации
Header-only C++ библиотека на C++17 с поддержкой гетерогенных поисков и move-only типов
Варианты с простыми числами (pg_) обеспечивают лучшее распределение при плохих функциях хеширования, bhopscotch_ гарантируют O(log n) для защиты от DoS-атак
Поддерживаемые функции: хранение хешей на вставку, предварительно вычисленные хеши для поиска, работа без исключений, полный API совместимый с std::unordered_map
Несколько политик роста таблицы (степени двойки, простые числа, произвольный множитель) для оптимизации под разные сценарии и функции хеширования

Почему это важно

Хеш-таблицы, критичная структура данных в системном программировании и высоконагруженных приложениях. Методы их реализации напрямую влияют на производительность: неправильный выбор может привести к деградации до O(n) при коллизиях. Hopscotch-hashing, известный метод открытой адресации, обеспечивающий амортизированную O(1) гарантию и хорошую локальность памяти. Опубликование производственной C++ библиотеки с benchmarks и поддержкой различных вариантов (включая защиту от DoS) показывает актуальность проблемы оптимизации для разработчиков инфраструктуры и системного ПО.

Кому это важно

Разработчикам систем на C++, которым требуется высокая производительность: авторам БД, кешей, сетевого ПО, компиляторов, инструментов обработки данных. Особенно релевантно для проектов, где std::unordered_map становится узким местом или где критична защита от DoS атак (например, при работе с untrusted input). Библиотека также полезна как reference implementation для изучения методов оптимизации хеш-таблиц.

Как это применить

Для проектов на C++17 hopscotch-map подключается как header-only библиотека через #include путь или CMake-target. При миграции с std::unordered_map нужно учитывать различия в поведении итераторов и требование вызывать value() для изменения значений. При выборе между вариантами: использовать стандартный hopscotch_map как default, переходить на pg_* если есть подозрение на плохую функцию хеширования (паттерны в младших битах), на bhopscotch_* если критична защита от DoS-атак. Для медленных хеш-функций включить параметр StoreHash=true. Benchmark и примеры с гетерогенными поисками приложены в репозитории.

Можно ли доверять

Библиотека разработана Tessil (https://github.com/Tessil/hopscotch-map), автором нескольких популярных C++ контейнеров. Hopscotch-hashing, научно обоснованный метод, описанный в academic literature. Код header-only, поэтому легко аудировать. Benchmarks приложены и показывают сравнение с другими реализациями. Поддержка многих C++ компиляторов (GCC, Clang, MSVC) и возможность работы без исключений указывает на production-ready статус. Однако, как и любая специализированная структура, требует профилирования на конкретных данных перед mass-adoption.

Риски и подводные камни

Итератор-инвалидация при вставке (кроме erase) может быть неожиданной для привыкших к std::unordered_map, требует тестирования кода. Move-only типы должны иметь nothrow move-конструктор, нарушение этого потребует модификации. API не поддерживает некоторые методы std::unordered_map (bucket_size, bucket), что может потребовать рефакторинга при миграции. При плохой функции хеширования и использовании power_of_two policy возможна высокая коллизионность (см. overflow_size()). Отсутствие поддержки потокобезопасности означает необходимость внешней синхронизации при многопоточном доступе, как в std::unordered_map.

««Быстрая хеш-таблица, см. benchmark для цифр»»

— README библиотеки hopscotch-map