Himmel und Hölle

• Formular: Nur Kopfzeile
• Lizenz: MIT (kostenlos und kostenlos)
• Ergebnisse der Leistungsbenchmarks: hier
• Git-Repository: tessil/hopscotch-map

Hopscotch ist auch ziemlich leistungsfähig. Ich habe es gefunden, als ich nach etwas Ähnlichem gesucht habe. Ich habe bisher einmal ein kleineres Projekt verwendet, bei dem es eine weitaus bessere Leistung hatte als std::unordered_map. Leistungstests im Vergleich zu den anderen Konkurrenten habe ich nicht durchgeführt.

Die reine Header-Bibliothek ist auf GitHub unter dem obigen Link verfügbar. Die Bibliothek bietet auch Implementierungen anderer Hash-Map-Algorithmen. Der Ersteller behauptet, dass es weniger Speicher verbraucht als Google, dense_hash_mapaber eine ähnliche Leistung hat. Aber wie Sie aus anderen Beiträgen hier sehen können, tauchen ziemlich kontinuierlich neue Hash-Map-Implementierungen auf. Laut einem Beitrag, den ich gelesen habe, soll Hopscotch schneller sein als die ska::flat_hash_map. Auf jeden Fall ist es viel schneller als die Karten in std.

Wenn Sie Garantien wie Referenzstabilität opfern können, können Sie verwenden

ska::flat_hash_mapvon Malte Skarupke

Die Hauptmerkmale sind:

• Adressierung öffnen
• Lineares Sondieren
• Robin-Hood-Hashing
• Primzahlenanzahl der Slots (aber eine Option zur Verwendung von Zweierpotenzen ist vorhanden)
• Mit einer Obergrenze für die Anzahl der Sonden

Auf YouTube gibt es dazu auch einen Vortrag von Malte Skarupke bei C++ Now 2018:

Sie können Besseres tun als std::unordered_map: Neue Verbesserungen der Leistung von Hash-Tabellen

und Blogposts in seinem persönlichen Blog, wo Sie auch das Benchmark-Bild unten finden können:

• 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/

Es gibt eine Hash-Table-Shootout- Seite auf incise.org.

Demnach ist die beste Leistung – in Bezug auf Geschwindigkeit, nicht Speicher – mit Googles Dense Hash Map: C++11 repository , original repository .

Hinweis: Die verknüpften Repositories heißen "sparsehash", enthalten aber tatsächlich sowohl die Sparse- als auch die Dense-Hash-Maps sowie die Sparse- und Dense-Hash-Sets.

Patchkarte

• Open Source
• kostenlose Unterstützung von mir
• umfangreiche Leistungstests und spärliche Unit-Tests
• fast perfekt imitiert die Schnittstelle vonstd::unordered_map
• Offene Adressierung mit linearer Sondierung mit Pseudozufallsreihenfolge (ähnlich Robin-Hood-Hashing)

Ich hatte ein ähnliches Problem, ich brauche eine Hash-Tabelle, die nicht nur schneller, sondern auch speichereffizienter ist, deshalb habe ich die Patchmap erstellt. Die relevanteste Statistik bei der Beurteilung der Leistung einer Hash-Tabelle ist der Raum-Zeit-Kompromiss. Sowohl Zeit als auch Speicher sind kostspielige Ressourcen, also sollten Sie sie sparen, aber der bevorzugte Kompromiss kann unterschiedlich sein.

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

Erfolgreiche Lookups sind wahrscheinlich die am weitesten verbreitete Operation, die eine Hash-Tabelle ausführen muss, aber Einfügen, Löschen und fehlgeschlagene Lookup- Benchmarks ändern das Bild nicht dramatisch. Die Patchmap ist nicht die schnellste. Am schnellsten wäre eine Hash-Tabelle mit viel Speicher, einem schnellen und guten Hash und einem einfachen offenen Adressierungs- und Sondierungsschema wie linearer Sondierung. Es ist auch nicht das speichereffizienteste, obwohl die Pseudozufallsreihenfolge auf dieses Regime gebracht werden kann, wodurch die Geschwindigkeit geopfert wird. Es bietet jedoch ein kleines Produkt aus Raum und Zeit, gleichauf mit bytell , beide nur unwesentlich besser als absl::flat_hash_map .