std::unordered_map слишком медленный для меня. Я хочу что-то быстрее! Какие библиотеки или независимые источники реализуют альтернативные, более быстрые хеш-таблицы с подобным (или лучшим) интерфейсом?

Требования:

• Свободное
• Бесплатное
• Некоторое тестирование, подтверждающее заявления об эффективности
• Неизменяемая пользовательская база

hopscotch

• Форма: Только заголовки
• Лицензия: MIT (Бесплатно и Свободно)
• Результаты производительности: здесь
• Git репозиторий: tessil/hopscotch-map

Hopscotch также довольно производителен. Я нашел его, когда искал что-то подобное, что использовал ранее в небольшом проекте, где он показал гораздо лучшую производительность по сравнению с std::unordered_map. Я не проводил тесты производительности в сравнении с другими конкурентами.

Библиотека только с заголовками доступна на GitHub по приведенной выше ссылке. Библиотека также предоставляет реализации других алгоритмов хеш-таблиц. Создатель утверждает, что она использует меньше памяти, чем Google’s dense_hash_map, но имеет аналогичную производительность. Но, как видно из других постов здесь, новые реализации хеш-таблиц регулярно появляются. Согласно посту, который я читал, hopscotch должен быть быстрее, чем ska::flat_hash_map. В любом случае, она намного быстрее, чем карты в std.

Если вы можете пожертвовать такими гарантиями, как стабильность ссылок, вы можете использовать

ska::flat_hash_map от Мальте Скарупке

Основные характеристики:

• Открытая адресация
• Линейное пробирование
• Хеширование Робин Гуда
• Количество слотов – простое число (но предоставляется возможность использовать степени двойки)
• С верхним пределом на количество проб

Также есть обсуждение этого на YouTube, проведенное Мальте Скарупке на C++ Now 2018:

Вы можете сделать лучше, чем std::unordered_map: Новые улучшения производительности хеш-таблицы

и блог-посты на его личном блоге, где вы также можете найти изображение с тестами производительности ниже:

• https://probablydance.com/2017/02/26/i-wrote-the-fastest-hashtable/
• https://probablydance.com/2018/05/28/a-new-fast-hash-table-in-response-to-googles-new-fast-hash-table/

patchmap

• открытый исходный код
• бесплатная поддержка от меня
• обширные тесты производительности и разреженные модульные тесты
• почти идеально имитирует интерфейс std::unordered_map
• открытая адресация с использованием линейного пробирования с псевдослучайным порядком (похожим на хеширование Робин Гуда)

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

patchmap: 🔴                khash: × 
bytell: +                   google::sparse_hash_map: ○ 
google::dense_hash_map: ⬟   ska::flat_hash_map: △ 
std::unordered_map: ◇       sparsepp: ◻     
Judy array: ◆               F14ValueMap: ▲ 
chaining+sorting: •         robin_hood::unordered_map: ▽  
absl::flat_hash_map: ⬠      tsl::sparse_hash_map: ★ 
emilib2::HashMap: ▩ 

Успешные поиски, вероятно, являются наиболее частой операцией, которую должна выполнять хеш-таблица, но вставка, удаление и неудачные поиски тесты производительности не меняют общую картину кардинально. Patchmap не самый быстрый. Самой быстрой хеш-таблицей будет та, что использует много памяти, быстрый и хороший хеш и простую открытую адресацию и схему пробирования, такую как линейное пробирование. Она также не самая эффективная по памяти, хотя псевдослучайный порядок может быть согласован с этим режимом, жертвуя скоростью. Тем не менее, она предлагает маленький продукт пространства и времени, сопоставимый с bytell, оба лишь незначительно лучше, чем absl::flat_hash_map.

Существовала страница с тестированием хеш-таблиц на incise.org.

Согласно этому, лучшая производительность – по скорости, а не по памяти – у Google’s Dense Hash Map: C++11 репозиторий, оригинальный репозиторий.

Примечание: Указанные репозитории называются “sparsehash”, но на самом деле содержат как разреженные, так и плотные хеш-таблицы, а также разреженные и плотные хеш-множества.