Библиотека hopscotch-map от Tessil — это быстрая реализация хеш-таблицы и хеш-сета на C++ с открытой адресацией и 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_map, tsl::bhopscotch_set и их pg-аналоги. Им для ключа нужен LessThanComparable, зато они дают верхнюю границу O(log n) на поиск и удаление, что защищает от DoS-атак.
Отличие от std::unordered_map в том, что любая модификация, кроме erase, инвалидирует все итераторы, ссылки и указатели. Операторы * и -> возвращают const std::pair, менять значение можно только через метод value(). Move-only типам нужен nothrow-конструктор перемещения. Нет поддержки bucket-методов.
Библиотека header-only. Можно хранить хеш вместе со значением (параметр StoreHash) для ускорения рехеширования. Если хеш известен заранее, его можно передать в find — это ускоряет поиск. Гетерогенные ключи работают при наличии is_transparent.
Политики роста — power_of_two_growth_policy (дефолтная, быстрая, без модуля), prime_growth_policy (лучше для плохих хешей) и mod_growth_policy (гибкая, с кастомизируемым множителем). Если много коллизий — смотрите overflow_size().
Для сборки используйте CMake (цель tsl::hopscotch_map) или просто подключите include. Требуется C++17. Тесты на Boost Test. Лицензия MIT.