классики

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

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

Библиотека только для заголовков доступна на GitHub по ссылке выше. Библиотека также предоставляет реализации других алгоритмов отображения хэшей. Создатель утверждает, что он использует меньше памяти, чем Google, dense_hash_mapно имеет аналогичную производительность. Но, как вы можете видеть из других сообщений здесь, новые реализации хеш-карт появляются довольно постоянно. Согласно сообщению, которое я прочитал, классики должны быть быстрее, чем 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/

На incise.org есть страница перестрелки хеш-таблиц .

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

Примечание. Репозитории, на которые ссылаются, называются «sparsehash», но на самом деле содержат карты разреженных и плотных хэшей, а также наборы разреженных и плотных хэшей.

карта патчей

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

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

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: ▩ 

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