hopscotch map
v2.3.1
Die Hopscotch-Map-Bibliothek ist eine C++-Implementierung einer schnellen Hash-Map und eines Hash-Sets, die offene Adressierung und Hopscotch-Hashing zur Auflösung von Kollisionen verwendet. Es handelt sich um eine Cache-freundliche Datenstruktur, die in den meisten Fällen eine bessere Leistung als std::unordered_map bietet und google::dense_hash_map sehr ähnlich ist, jedoch weniger Speicher verbraucht und mehr Funktionalitäten bietet.
Die Bibliothek stellt die folgenden Hauptklassen bereit: tsl::hopscotch_map , tsl::hopscotch_set , tsl::hopscotch_pg_map und tsl::hopscotch_pg_set . Die ersten beiden sind schneller und nutzen eine Zweierpotenz-Wachstumspolitik, die letzten beiden nutzen stattdessen eine Prime-Wachstumspolitik und kommen besser mit einer schlechten Hash-Funktion zurecht. Verwenden Sie die Prime-Version, wenn die Möglichkeit besteht, dass sich Muster in den unteren Bits Ihres Hashs wiederholen (z. B. wenn Sie Zeiger mit einer Identitäts-Hash-Funktion speichern). Weitere Informationen finden Sie unter GrowthPolicy.
Zusätzlich zu diesen Klassen stellt die Bibliothek auch tsl::bhopscotch_map , tsl::bhopscotch_set , tsl::bhopscotch_pg_map und tsl::bhopscotch_pg_set bereit. Diese Klassen stellen eine zusätzliche Anforderung an den Schlüssel, er muss LessThanComparable sein, sie bieten jedoch eine bessere asymptotische Obergrenze, siehe Details im Beispiel. Wenn Sie jedoch keine besonderen Anforderungen haben (Risiko von Hash-DoS-Angriffen), sollten tsl::hopscotch_map und tsl::hopscotch_set in den meisten Fällen ausreichend sein und Ihre Standardauswahl sein, da sie im Allgemeinen eine bessere Leistung erbringen.
Eine Übersicht über Hopscotch-Hashing und einige Implementierungsdetails finden Sie hier.
Ein Benchmark von tsl::hopscotch_map im Vergleich zu anderen Hash-Maps finden Sie hier. Auf dieser Seite finden Sie auch einige Ratschläge dazu, welche Hash-Tabellenstruktur Sie für Ihren Anwendungsfall ausprobieren sollten (nützlich, wenn Sie sich mit den Implementierungen mehrerer Hash-Tabellen im tsl -Namespace etwas auskennen).
tsl::hopscotch_map aus CMakeLists.txt verwenden.find mit einem anderen Typ als Key ermöglichen (z. B. wenn Sie eine Karte haben, die std::unique_ptr<foo> als Schlüssel verwendet, können Sie „ foo* oder std::uintptr_t als Schlüsselparameter verwenden find ohne einen std::unique_ptr<foo> zu konstruieren, siehe Beispiel).precalculated_hash in der API).tsl::bhopscotch_map und tsl::bhopscotch_set bieten einen Worst-Case von O(log n) bei Suchvorgängen und Löschungen, wodurch diese Klassen resistent gegen Hash-Tabellen-Deny-of-Service-Angriffe (DoS) sind (siehe Details im Beispiel).-fno-exceptions in Clang und GCC, ohne /EH -Option in MSVC oder einfach durch Definition TSL_NO_EXCEPTIONS ). std::terminate wird als Ersatz für die throw -Anweisung verwendet, wenn Ausnahmen deaktiviert sind.std::unordered_map und std::unordered_set sehr ähnlich ist.std::unordered_map tsl::hopscotch_map versucht, eine ähnliche Schnittstelle wie std::unordered_map zu haben, es bestehen jedoch einige Unterschiede.
erase , alle Iteratoren ungültig (Einzelheiten finden Sie in der API).operator*() und operator->() eine Referenz und einen Zeiger auf const std::pair<Key, T> anstelle von std::pair<const Key, T> zurück, sodass der Wert T nicht änderbar ist. Um den Wert zu ändern, müssen Sie die value() Methode des Iterators aufrufen, um eine veränderbare Referenz zu erhalten. Beispiel: 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 , ...). Diese Unterschiede gelten auch zwischen std::unordered_set und tsl::hopscotch_set .
Thread-Sicherheits- und Ausnahmegarantien sind die gleichen wie bei std::unordered_map/set (dh es ist möglich, mehrere Leser ohne Schreiber zu haben).
Die Bibliothek unterstützt mehrere Wachstumsrichtlinien über den Vorlagenparameter GrowthPolicy . Die Bibliothek stellt drei Richtlinien zur Verfügung, Sie können jedoch bei Bedarf problemlos Ihre eigenen implementieren.
tsl::(b)hopscotch_map/set verwendete Standardrichtlinie. Diese Richtlinie hält die Größe des Bucket-Arrays der Hash-Tabelle auf eine Zweierpotenz. Diese Einschränkung ermöglicht es der Richtlinie, die Verwendung der langsamen Modulo-Operation zum Zuordnen eines Hashs zu einem Bucket zu vermeiden. Statt hash % 2 n verwendet sie hash & (2 n - 1) (siehe schnelles Modulo). Schnell, aber dies kann zu vielen Kollisionen mit einer schlechten Hash-Funktion führen, da das Modulo mit einer Zweierpotenz am Ende nur die höchstwertigen Bits maskiert.tsl::(b)hopscotch_pg_map/set verwendete Standardrichtlinie. Die Richtlinie hält die Größe des Bucket-Arrays der Hash-Tabelle auf einer Primzahl. Wenn Sie einen Hash einem Bucket zuordnen, führt die Verwendung einer Primzahl als Modulo zu einer besseren Verteilung der Hashes über die Buckets, selbst bei einer schlechten Hash-Funktion. Damit der Compiler die Modulo-Operation optimieren kann, verwendet die Richtlinie eine Nachschlagetabelle mit konstanten Primzahlen-Modulos (Einzelheiten siehe API). Langsamer als tsl::hh::power_of_two_growth_policy , aber sicherer. Wenn die Leistung schlecht ist, überprüfen Sie overflow_size() . Wenn es nicht Null ist, kann es zu vielen Hash-Kollisionen kommen. Ändern Sie entweder die Hash-Funktion für etwas Einheitlicheres oder versuchen Sie es mit einer anderen Wachstumsrichtlinie (hauptsächlich tsl::hh::prime_growth_policy ). Leider ist es manchmal schwierig, sich vor Kollisionen (z. B. DoS-Angriff auf die Hash-Map) zu schützen. Überprüfen Sie bei Bedarf auch tsl::bhopscotch_map/set , das ein Worst-Case-Szenario von O(log n) bei Suchvorgängen anstelle von O(n) bietet, siehe Details im Beispiel.
Um Ihre eigene Richtlinie zu implementieren, müssen Sie die folgende Schnittstelle implementieren.
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 ;
}Um hopscotch-map zu verwenden, fügen Sie einfach das Include-Verzeichnis zu Ihrem Include-Pfad hinzu. Es handelt sich um eine reine Header- Bibliothek.
Wenn Sie CMake verwenden, können Sie auch das exportierte Ziel tsl::hopscotch_map aus CMakeLists.txt mit target_link_libraries verwenden.
# 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) Wenn das Projekt über make install installiert wurde, können Sie auch find_package(tsl-hopscotch-map REQUIRED) anstelle von add_subdirectory verwenden.
Der Code sollte mit jedem C++17-Standard-kompatiblen Compiler funktionieren.
Zum Ausführen der Tests benötigen Sie die Boost-Testbibliothek und 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 Die API finden Sie hier.
Alle Methoden sind noch nicht dokumentiert, aber sie replizieren das Verhalten derjenigen in std::unordered_map und std::unordered_set , sofern nicht anders angegeben.
# 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;
}
} Heterogene Überladungen ermöglichen die Verwendung anderer Typen als Key für Such- und Löschvorgänge, sofern die verwendeten Typen hashbar und mit Key vergleichbar sind.
Um die heterogenen Überladungen in tsl::hopscotch_map/set zu aktivieren, muss die qualifizierte ID KeyEqual::is_transparent gültig sein. Es funktioniert genauso wie für std::map::find . Sie können entweder std::equal_to<> verwenden oder Ihr eigenes Funktionsobjekt definieren.
Sowohl KeyEqual als auch Hash müssen in der Lage sein, mit den verschiedenen Typen umzugehen.
# 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;
} Zusätzlich zu tsl::hopscotch_map und tsl::hopscotch_set bietet die Bibliothek zwei weitere „sichere“ Optionen: tsl::bhopscotch_map und tsl::bhopscotch_set (alle mit ihren pg -Gegenstücken).
Diese beiden Additionen haben im schlimmsten Fall eine asymptotische Komplexität von O(log n) für Suchvorgänge und Löschungen und eine amortisierte Worst-Case-Komplexität von O(log n) für Einfügungen (amortisiert aufgrund der Möglichkeit einer erneuten Aufbereitung, die in O(n) wäre). . Selbst wenn die Hash-Funktion alle Elemente demselben Bucket zuordnet, würde O(log n) immer noch gelten.
Dies bietet Sicherheit gegen Hash-Table-Deny-of-Service-Angriffe (DoS).
Um dies zu erreichen, verwenden die sicheren Versionen einen binären Suchbaum für die überflogenen Elemente (siehe Implementierungsdetails) und benötigen daher die Elemente LessThanComparable . Es ist ein zusätzlicher Parameter Compare erforderlich.
# 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;
} Der Code ist unter der MIT-Lizenz lizenziert. Weitere Informationen finden Sie in der LICENSE-Datei.
