hopscotch map
v2.3.1
Библиотека Hopscotch-map — это реализация на C++ быстрой хеш-карты и хэш-набора, использующая открытую адресацию и хеширование в классах для разрешения коллизий. Это структура данных, дружественная к кэшу, обеспечивающая лучшую производительность, чем std::unordered_map в большинстве случаев, и очень похожа на google::dense_hash_map но использует меньше памяти и предоставляет больше функций.
Библиотека предоставляет следующие основные классы: tsl::hopscotch_map , tsl::hopscotch_set , tsl::hopscotch_pg_map и tsl::hopscotch_pg_set . Первые два работают быстрее и используют политику роста степени двойки, последние два вместо этого используют политику простого роста и способны лучше справляться с плохой хэш-функцией. Используйте основную версию, если есть вероятность повторения шаблонов в младших битах вашего хеша (например, вы храните указатели с помощью идентификационной хэш-функции). Подробности см. в разделе GrowthPolicy.
В дополнение к этим классам библиотека также предоставляет tsl::bhopscotch_map , tsl::bhopscotch_set , tsl::bhopscotch_pg_map и tsl::bhopscotch_pg_set . У этих классов есть дополнительное требование к ключу: он должен быть LessThanComparable , но они обеспечивают лучшую асимптотическую верхнюю границу, см. подробности в примере. Тем не менее, если у вас нет особых требований (риск хэш-DoS-атак), tsl::hopscotch_map и tsl::hopscotch_set должны быть достаточными в большинстве случаев и должны быть вашим выбором по умолчанию, поскольку в целом они работают лучше.
Обзор хеширования в классиках и некоторые подробности реализации можно найти здесь.
Сравнительный анализ tsl::hopscotch_map с другими хэш-картами можно найти здесь. На этой странице также даются некоторые советы о том, какую структуру хэш-таблицы следует использовать в вашем случае (полезно, если вы немного запутались в реализации нескольких хэш-таблиц в пространстве имен tsl ).
tsl::hopscotch_map из файла CMakeLists.txt.find с типом, отличным от Key (например, если у вас есть карта, которая использует std::unique_ptr<foo> в качестве ключа, вы можете использовать foo* или std::uintptr_t в качестве ключевого параметра для find без создания std::unique_ptr<foo> , см. пример).precalculated_hash в API).tsl::bhopscotch_map и tsl::bhopscotch_set обеспечивают наихудший случай O(log n) при поиске и удалении, что делает эти классы устойчивыми к атакам типа «отказ в обслуживании» (DoS) из хеш-таблицы (подробности см. в примере).-fno-exceptions в Clang и GCC, без опции /EH в MSVC или просто путем определения TSL_NO_EXCEPTIONS ). std::terminate используется вместо инструкции throw , когда исключения отключены.std::unordered_map и std::unordered_set .std::unordered_map tsl::hopscotch_map пытается иметь интерфейс, похожий на std::unordered_map , но существуют некоторые различия.
erase , делает недействительными все итераторы (подробности см. в API).operator*() и operator->() возвращают ссылку и указатель на const std::pair<Key, T> вместо std::pair<const Key, T> , что делает значение T недоступным для изменения. Чтобы изменить значение, вам нужно вызвать метод value() итератора, чтобы получить изменяемую ссылку. Пример: tsl::hopscotch_map< int , int > map = {{ 1 , 1 }, { 2 , 1 }, { 3 , 1 }};
for ( auto it = map.begin(); it != map.end(); ++it) {
// it->second = 2; // Illegal
it. value () = 2 ; // Ok
}bucket_size , bucket , ...). Эти различия также применимы между std::unordered_set и tsl::hopscotch_set .
Гарантии потокобезопасности и исключений такие же, как и у std::unordered_map/set (т.е. возможно иметь несколько читателей без записи).
Библиотека поддерживает несколько политик роста с помощью параметра шаблона GrowthPolicy . Библиотека предоставляет три политики, но при необходимости вы можете легко реализовать свои собственные.
tsl::(b)hopscotch_map/set . Эта политика сохраняет размер массива сегментов хеш-таблицы равным степени двойки. Это ограничение позволяет политике избежать использования медленной операции по модулю для сопоставления хеша с сегментом. Вместо hash % 2 n используется hash & (2 n - 1) (см. быстрый модуль). Быстро, но это может вызвать множество коллизий из-за плохой хэш-функции, поскольку модуль со степенью двойки в конечном итоге маскирует только наиболее значимые биты.tsl::(b)hopscotch_pg_map/set . Политика сохраняет размер массива сегментов хеш-таблицы простым числом. При сопоставлении хеша с сегментом использование простого числа по модулю приведет к лучшему распределению хешей по сегментам даже при плохой хеш-функции. Чтобы позволить компилятору оптимизировать операцию по модулю, политика использует таблицу поиска с постоянными простыми числами по модулю (подробности см. в API). Медленнее, чем tsl::hh::power_of_two_growth_policy , но более безопасно. Если вы столкнулись с плохой производительностью, проверьте overflow_size() . Если он не равен нулю, возможно, у вас много хеш-коллизий. Либо измените хэш-функцию на что-то более единообразное, либо попробуйте другую политику роста (в основном tsl::hh::prime_growth_policy ). К сожалению, иногда сложно защититься от коллизий (например, DoS-атаки на хеш-карту). При необходимости проверьте также tsl::bhopscotch_map/set , который предлагает наихудший сценарий поиска O(log n) вместо O(n), подробности см. в примере.
Чтобы реализовать собственную политику, вам необходимо реализовать следующий интерфейс.
struct custom_policy {
// Called on hash table construction and rehash, min_bucket_count_in_out is the minimum buckets
// that the hash table needs. The policy can change it to a higher number of buckets if needed
// and the hash table will use this value as bucket count. If 0 bucket is asked, then the value
// must stay at 0.
explicit custom_policy (std:: size_t & min_bucket_count_in_out);
// Return the bucket [0, bucket_count()) to which the hash belongs.
// If bucket_count() is 0, it must always return 0.
std:: size_t bucket_for_hash (std:: size_t hash) const noexcept ;
// Return the number of buckets that should be used on next growth
std:: size_t next_bucket_count () const ;
// Maximum number of buckets supported by the policy
std:: size_t max_bucket_count () const ;
// Reset the growth policy as if the policy was created with a bucket count of 0.
// After a clear, the policy must always return 0 when bucket_for_hash() is called.
void clear () noexcept ;
}Чтобы использовать Hopscotch-map, просто добавьте каталог включения в свой путь включения. Это библиотека только для заголовков .
Если вы используете CMake, вы также можете использовать экспортированную цель tsl::hopscotch_map из CMakeLists.txt с помощью target_link_libraries .
# Example where the hopscotch-map project is stored in a third-party directory
add_subdirectory (third-party/hopscotch-map)
target_link_libraries (your_target PRIVATE tsl::hopscotch_map) Если проект был установлен с помощью make install , вы также можете использовать find_package(tsl-hopscotch-map REQUIRED) вместо add_subdirectory .
Код должен работать с любым компилятором, соответствующим стандарту C++17.
Для запуска тестов вам понадобится библиотека Boost Test и CMake.
git clone https://github.com/Tessil/hopscotch-map.git
cd hopscotch-map/tests
mkdir build
cd build
cmake ..
cmake --build .
./tsl_hopscotch_map_tests API можно найти здесь.
Все методы еще не документированы, но они повторяют поведение методов в std::unordered_map и std::unordered_set , если не указано иное.
# include < cstdint >
# include < iostream >
# include < string >
# include < tsl/hopscotch_map.h >
# include < tsl/hopscotch_set.h >
int main () {
tsl::hopscotch_map<std::string, int > map = {{ " a " , 1 }, { " b " , 2 }};
map[ " c " ] = 3 ;
map[ " d " ] = 4 ;
map. insert ({ " e " , 5 });
map. erase ( " b " );
for ( auto it = map. begin (); it != map. end (); ++it) {
// it->second += 2; // Not valid.
it. value () += 2 ;
}
// {d, 6} {a, 3} {e, 7} {c, 5}
for ( const auto & key_value : map) {
std::cout << " { " << key_value. first << " , " << key_value. second << " } " << std::endl;
}
if (map. find ( " a " ) != map. end ()) {
std::cout << " Found " a " . " << std::endl;
}
const std:: size_t precalculated_hash = std::hash<std::string>()( " a " );
// If we already know the hash beforehand, we can pass it in parameter to speed-up lookups.
if (map. find ( " a " , precalculated_hash) != map. end ()) {
std::cout << " Found " a " with hash " << precalculated_hash << " . " << std::endl;
}
/*
* Calculating the hash and comparing two std::string may be slow.
* We can store the hash of each std::string in the hash map to make
* the inserts and lookups faster by setting StoreHash to true.
*/
tsl::hopscotch_map<std::string, int , std::hash<std::string>,
std::equal_to<std::string>,
std::allocator<std::pair<std::string, int >>,
30 , true > map2;
map2[ " a " ] = 1 ;
map2[ " b " ] = 2 ;
// {a, 1} {b, 2}
for ( const auto & key_value : map2) {
std::cout << " { " << key_value. first << " , " << key_value. second << " } " << std::endl;
}
tsl::hopscotch_set< int > set;
set. insert ({ 1 , 9 , 0 });
set. insert ({ 2 , - 1 , 9 });
// {0} {1} {2} {9} {-1}
for ( const auto & key : set) {
std::cout << " { " << key << " } " << std::endl;
}
} Гетерогенные перегрузки позволяют использовать другие типы, кроме Key для операций поиска и стирания, если используемые типы хешируются и сопоставимы с Key .
Чтобы активировать гетерогенные перегрузки в tsl::hopscotch_map/set , квалифицированный идентификатор KeyEqual::is_transparent должен быть действительным. Это работает так же, как и для std::map::find . Вы можете использовать std::equal_to<> или определить свой собственный объект функции.
И KeyEqual , и Hash должны иметь возможность работать с разными типами.
# include < functional >
# include < iostream >
# include < string >
# include < tsl/hopscotch_map.h >
struct employee {
employee ( int id, std::string name) : m_id(id), m_name(std::move(name)) {
}
// Either we include the comparators in the class and we use `std::equal_to<>`...
friend bool operator ==( const employee& empl, int empl_id) {
return empl. m_id == empl_id;
}
friend bool operator ==( int empl_id, const employee& empl) {
return empl_id == empl. m_id ;
}
friend bool operator ==( const employee& empl1, const employee& empl2) {
return empl1. m_id == empl2. m_id ;
}
int m_id;
std::string m_name;
};
// ... or we implement a separate class to compare employees.
struct equal_employee {
using is_transparent = void ;
bool operator ()( const employee& empl, int empl_id) const {
return empl. m_id == empl_id;
}
bool operator ()( int empl_id, const employee& empl) const {
return empl_id == empl. m_id ;
}
bool operator ()( const employee& empl1, const employee& empl2) const {
return empl1. m_id == empl2. m_id ;
}
};
struct hash_employee {
std:: size_t operator ()( const employee& empl) const {
return std::hash< int >()(empl. m_id );
}
std:: size_t operator ()( int id) const {
return std::hash< int >()(id);
}
};
int main () {
// Use std::equal_to<> which will automatically deduce and forward the parameters
tsl::hopscotch_map<employee, int , hash_employee, std::equal_to<>> map;
map. insert ({ employee ( 1 , " John Doe " ), 2001 });
map. insert ({ employee ( 2 , " Jane Doe " ), 2002 });
map. insert ({ employee ( 3 , " John Smith " ), 2003 });
// John Smith 2003
auto it = map. find ( 3 );
if (it != map. end ()) {
std::cout << it-> first . m_name << " " << it-> second << std::endl;
}
map. erase ( 1 );
// Use a custom KeyEqual which has an is_transparent member type
tsl::hopscotch_map<employee, int , hash_employee, equal_employee> map2;
map2. insert ({ employee ( 4 , " Johnny Doe " ), 2004 });
// 2004
std::cout << map2. at ( 4 ) << std::endl;
} Помимо tsl::hopscotch_map и tsl::hopscotch_set библиотека предоставляет еще две «безопасные» опции: tsl::bhopscotch_map и tsl::bhopscotch_set (все со своими аналогами pg ).
Эти два дополнения имеют наихудшую асимптотическую сложность O(log n) для поиска и удаления и амортизированную наихудшую сложность O(log n) для вставок (амортизированную из-за возможности повторного хэширования, которое будет за O(n)) . Даже если хеш-функция сопоставит все элементы в одну и ту же корзину, O(log n) все равно останется в силе.
Это обеспечивает защиту от атак типа «отказ в обслуживании» (DoS) хеш-таблицы.
Чтобы добиться этого, безопасные версии используют двоичное дерево поиска для переполненных элементов (см. подробности реализации), поэтому элементы должны быть LessThanComparable . Требуется дополнительный параметр шаблона Compare .
# include < chrono >
# include < cstdint >
# include < iostream >
# include < tsl/hopscotch_map.h >
# include < tsl/bhopscotch_map.h >
/*
* Poor hash function which always returns 1 to simulate
* a Deny of Service attack.
*/
struct dos_attack_simulation_hash {
std:: size_t operator ()( int id) const {
return 1 ;
}
};
int main () {
/*
* Slow due to the hash function, insertions are done in O(n).
*/
tsl::hopscotch_map< int , int , dos_attack_simulation_hash> map;
auto start = std::chrono::high_resolution_clock::now ();
for ( int i= 0 ; i < 10000 ; i++) {
map. insert ({i, 0 });
}
auto end = std::chrono::high_resolution_clock::now ();
// 110 ms
auto duration = std::chrono::duration_cast<std::chrono::milliseconds>(end-start);
std::cout << duration. count () << " ms " << std::endl;
/*
* Faster. Even with the poor hash function, insertions end-up to
* be O(log n) in average (and O(n) when a rehash occurs).
*/
tsl::bhopscotch_map< int , int , dos_attack_simulation_hash> map_secure;
start = std::chrono::high_resolution_clock::now ();
for ( int i= 0 ; i < 10000 ; i++) {
map_secure. insert ({i, 0 });
}
end = std::chrono::high_resolution_clock::now ();
// 2 ms
duration = std::chrono::duration_cast<std::chrono::milliseconds>(end-start);
std::cout << duration. count () << " ms " << std::endl;
} Код лицензируется по лицензии MIT, подробности см. в файле LICENSE.
