101
Ich habe eine Frage mit hash_map und map in C++. Ich verstehe, dass map ist in STL, aber hash_map ist kein Standard. Was ist der Unterschied zwischen den beiden?Karte vs Hashmap in C++
A
Antwort
119
Sie sind auf sehr unterschiedliche Weise implementiert.
hash_map (unordered_map in TR1 und Boost; verwenden Sie diese stattdessen) verwenden Sie eine Hash-Tabelle, wo der Schlüssel zu einem Steckplatz in der Tabelle Hashed und der Wert in einer Liste mit diesem Schlüssel gespeichert ist.
map ist als ausgewogener binärer Suchbaum implementiert (normalerweise ein rot/schwarzer Baum).
Eine unordered_map sollte eine etwas bessere Leistung für den Zugriff auf bekannte Elemente der Sammlung geben, aber eine map wird zusätzliche nützliche Eigenschaften haben (z.B. wird sie in sortierter Reihenfolge gespeichert, was das Durchlaufen von Anfang bis Ende erlaubt). unordered_map wird beim Einfügen schneller und löschen als ein map.
4
Die C++ - Spezifikation sagt nicht genau, welchen Algorithmus Sie für die STL-Container verwenden müssen. Es stellt jedoch bestimmte Einschränkungen für ihre Leistung bereit, die die Verwendung von Hashtabellen für map und andere assoziative Container ausschließt. (Sie werden am häufigsten mit Rot/Schwarz-Bäumen implementiert.) Diese Einschränkungen erfordern eine bessere Worst-Case-Leistung für diese Container, als Hash-Tabellen liefern können.
Viele Leute wollen wirklich Hash-Tabellen, also sind Hash-basierte assoziative STL-Container seit Jahren eine gebräuchliche Erweiterung. Folglich fügten sie unordered_map und so zu späteren Versionen des C++ Standards hinzu.
+0
Es wurde tatsächlich in TR1 hinzugefügt (std :: tr1 :: unordered_map), nicht C++ 0x –
+0
Edited, um es zu beheben. –
+0
Ich dachte, dass der Grund "map" im Allgemeinen ein balanced btree ist wegen der Verwendung von 'operator <()' als Mittel zur Bestimmung der Position. – KitsuneYMG
33
hash_map war eine allgemeine Erweiterung, die von vielen Bibliotheksimplementierungen bereitgestellt wurde. Aus diesem Grund wurde es in unordered_map umbenannt, als es als Teil von TR1 dem C++ - Standard hinzugefügt wurde. Karte wird im Allgemeinen mit einem ausgeglichenen Binärbaum wie ein Rot-Schwarz-Baum implementiert (Implementierungen variieren natürlich). hash_map und unordered_map werden generell mit Hash-Tabellen implementiert. Somit wird die Reihenfolge nicht beibehalten. unordered_map insert/delete/query wird O (1) (konstante Zeit) sein, wobei map O (log n) ist, wobei n die Anzahl der Elemente in der Datenstruktur ist. So ist unordered_map schneller, und wenn Sie nicht über die Reihenfolge der Artikel kümmern, sollte über map bevorzugt werden. Manchmal möchten Sie die Reihenfolge beibehalten (geordnet nach dem Schlüssel) und dafür wäre map die Wahl.
+9
Ich würde darauf hinweisen, dass hashmap einen Worst-Case-Zugriff von O (N) hat, wenn Kollisionen wahrscheinlich sind (schlechter Hash fcn, Ladefaktor zu hoch, usw.) – KitsuneYMG
+0
Eine gute hashmap hat einen erwarteten Aufwand von O (1), ist es nicht garantiert so zu sein. Schlechte Hashmaps haben möglicherweise zu erwartende Kosten, die nicht O (1) sind. – Clearer
12
Einige der Hauptunterschiede liegen in den Komplexitätsanforderungen.
Eine Karte benötigt O (log (N)) Zeit für Einsätze und Funde.
Eine unordered_map benötigt eine 'durchschnittliche' Zeit von O (1) für Inserts und Funde, darf aber eine Worst-Case-Zeit von O (N) haben.
So wird normalerweise ungeordnete_Map schneller sein, aber abhängig von den Schlüsseln und der Hash-Funktion, die Sie speichern, kann viel schlechter werden.
0
Ich weiß nicht, was gibt, aber, hash_map dauert mehr als 20 Sekunden zum Löschen() 150K vorzeichenlose Integer-Schlüssel und Float-Werte. Ich renne gerade und lese den Code von jemand anderem.
Dies ist, wie es hash_map enthält.
#include "StdAfx.h"
#include <hash_map>
las ich dies hier https://bytes.com/topic/c/answers/570079-perfomance-clear-vs-swap
sagen, dass clear(), um von O (N) ist. Das ist mir sehr seltsam, aber so ist es.
Ich stimme Ihnen bezüglich der Leistung nicht voll zu. Die Leistung wird durch eine Reihe von Parametern beeinflusst und ich würde jeden Programmierer schimpfen, der eine ungeordnete Map für nur 10 Einträge verwendet, weil "es schneller ist". Machen Sie sich zuerst Gedanken über die Schnittstelle/Funktionalität, später über die Leistung. –
Nun ja, es hilft, wenn Sie Ihr Problem verstehen. Bis zu gewissen Grössenordnungen ist es wahrscheinlich eine Waschleistung, aber es ist wichtig, die Leistungsmerkmale beider Behälter zu verstehen, da sie auf unterschiedliche Weise abweichen, wenn die Datenmengen größer werden. – Joe
Interessanterweise vertauschte ich gerade eine std :: map mit einer boost :: unordered_map in einer Anwendung, in der ich viele zufällige Suchen durchführe, aber auch über alle Schlüssel in der Karte iteriere. Ich habe viel Zeit beim Nachschlagen gespart, aber über die Iterationen zurückgewonnen, also bin ich zurück zur Karte gegangen und suche nach anderen Möglichkeiten, um die Anwendungsleistung zu verbessern. –