Verwendung von HashMap in C++

In C++ wird eine Hash-Map durch std::unordered_map bereitgestellt; std::map ist ein verwandter Schlüssel-Wert-Container, der die Schlüssel geordnet hält. Beide sind assoziative Container: Jeder Schlüssel ist eindeutig und bezeichnet einen zugeordneten Wert. Verschiedene Schlüssel können denselben Wert enthalten. Verwenden Sie einen der beiden Container, wenn Sie Werte anhand eines Schlüssels nachschlagen müssen, und wählen Sie danach, ob eine geordnete Iteration wichtig ist.

Der Standard schreibt für std::map keine bestimmte interne Implementierung vor. Die sichtbare Reihenfolge ergibt sich aus dem Schlüsselvergleich (bei Verwendung des Standardvergleichs aufsteigend). Im Gegensatz dazu verwendet std::unordered_map eine Hash-Funktion und Buckets; die Iterationsreihenfolge ist nicht festgelegt. Verlassen Sie sich nicht auf die Reihenfolge, die Sie bei einem einzelnen Durchlauf beobachten.

So funktionieren Hash-Maps in C++

Binden Sie <map> oder <unordered_map> ein und legen Sie die Typen für Schlüssel und zugeordnete Werte fest, zum Beispiel std::map<int, std::string>. insert fügt ein Schlüssel-Wert-Paar nur hinzu, wenn der Schlüssel noch nicht vorhanden ist. Eine Zuweisung über operator[] fügt bei Bedarf zunächst einen wertinitialisierten zugeordneten Wert ein und weist ihm anschließend den neuen Wert zu. Bei einem skalaren zugeordneten Typ wie int ergibt die Wertinitialisierung vor der Zuweisung null. Eine Zuweisung zu einem vorhandenen Schlüssel aktualisiert dessen Wert, ohne einen doppelten Schlüssel anzulegen. Verwenden Sie find, wenn Sie vor dem Zugriff auf den Wert prüfen müssen, ob ein Schlüssel vorhanden ist. Auch at sucht nach einem Schlüssel, meldet einen fehlenden Schlüssel jedoch mit std::out_of_range.

Das bereitgestellte Laufzeitprotokoll weist die erfolgreiche Ausführung beider ursprünglicher Beispiele aus. Die folgende Ausgabe für std::map entspricht der protokollierten Ausgabe. Das spätere Beispiel mit dem ungeordneten Container enthält zusätzlich eine Iterationsschleife; für diese geänderte Variante wird daher keine konkrete Ausgabereihenfolge behauptet.

std::map für geordnete Schlüssel verwenden

Verwenden Sie std::map, wenn die Schlüssel in der Reihenfolge des Vergleichs durchlaufen werden sollen oder wenn Sie geordnete Operationen benötigen, etwa das Finden des ersten Schlüssels, der mindestens einem bestimmten Wert entspricht. Suchen, Einfügen und Entfernen benötigen logarithmische Zeit, O(log n), wobei n die Anzahl der Elemente ist. Diese vorhersehbare Laufzeit und die geordnete Iteration sind für Berichte, Wertebereiche und sortierte Listen nützlich. Der Standard garantiert das Ordnungsverhalten, aber keine bestimmte Baumimplementierung.

Führen Sie dieses Beispiel aus:

Der Code und die angezeigten Bezeichnungen oder Ausgaben in diesem Abschnitt bleiben auf Englisch.

#include <iostream>
#include <map>
#include <string>

int main() {
  std::map<int, std::string> players;
  players.emplace(2, "Lin Dan");
  players.emplace(1, "Chen Long");

  const auto found = players.find(1);
  if (found != players.end()) {
    std::cout << found->first << ": " << found->second << '\n';
  }
  for (const auto& entry : players) {
    std::cout << entry.first << ": " << entry.second << '\n';
  }
}

1: Chen Long
1: Chen Long
2: Lin Dan

Die Suche gibt den Schlüssel 1 aus. Die Schleife durchläuft die Schlüssel in der Vergleichsreihenfolge, sodass 1 unabhängig von der Einfügereihenfolge vor 2 steht.

std::unordered_map für Hash-basierte Suche verwenden

Wählen Sie std::unordered_map, wenn die Suche anhand des Schlüssels im Vordergrund steht und keine sortierte Iteration erforderlich ist. Suchen, Einfügen und Entfernen benötigen durchschnittlich O(1), können im ungünstigsten Fall aber O(n) dauern, etwa wenn viele Schlüssel kollidieren. Ein Rehashing kann außerdem die Iterationsreihenfolge ändern und Iteratoren ungültig machen. Für den Container gelten Anforderungen an Hash-Funktion und Gleichheit: Gleichwertige Schlüssel müssen denselben Hashwert ergeben.

Führen Sie dieses Beispiel aus:

Der Code und die angezeigten Bezeichnungen oder Ausgaben in diesem Abschnitt bleiben auf Englisch.

#include <iostream>
#include <string>
#include <unordered_map>

int main() {
  std::unordered_map<std::string, int> scores;
  scores["Ada"] = 8;
  scores["Lin"] = 11;

  const auto found = scores.find("Ada");
  if (found != scores.end()) {
    std::cout << found->first << ": " << found->second << '\n';
  }
  for (const auto& entry : scores) {
    std::cout << entry.first << ": " << entry.second << '\n';
  }
  std::cout << "Players: " << scores.size() << '\n';
}

Die bereichsbasierte Schleife durchläuft alle Einträge in scores. Sie können in beliebiger Reihenfolge erscheinen; weder der Standard noch dieses Beispiel garantiert eine bestimmte Abfolge. Wenn die Ausgabe sortiert sein muss, sammeln und sortieren Sie eine separate Schlüsselliste.

Zwischen std::map und std::unordered_map wählen

Für eine Worthäufigkeitszählung oder einen Cache, bei dem die Reihenfolge keine Rolle spielt, ist std::unordered_map oft eine passende Wahl. Verwenden Sie std::map für sortierte Ausgaben oder Wertebereichsabfragen anhand des Schlüssels. Wenn ein ungeordneter Container für die Suche geeignet ist, Sie aber eine sortierte Darstellung benötigen, sammeln und sortieren Sie die Schlüssel vor der Ausgabe, statt eine bestimmte Iterationsreihenfolge anzunehmen. Entscheidend ist das benötigte Verhalten ebenso wie die durchschnittliche Geschwindigkeit: Wenn die Leistung für Ihre Anwendung wichtig ist, führen Sie Benchmarks mit repräsentativen Daten aus.

Beide Container ermöglichen den Zugriff auf Schlüssel und Werte, unterscheiden sich aber bei Iteration und Leistungsgarantien. Wenn eine Iteration die Schlüssel in geordneter Reihenfolge ausgeben muss, verwenden Sie std::map; für Hash-basierte Suche, bei der die Reihenfolge keine Rolle spielt, verwenden Sie std::unordered_map. Ein weiteres Beispiel für eine geordnete Traversierung finden Sie unter Inorder-Traversierung in C++.