Verwendung von HashMap in C++

1. Verwendung von HashMap mit std::map in C++
2. Verwendung von HashMap mit std::unordered_map in C++
3. Hauptunterschiede und wann die einzelnen Maps in C++ verwendet werden sollten

Die HashMap ist eine wichtige Datenstruktur, die Schlüssel-Wert-Paare enthält, in denen ein Wert mithilfe des entsprechenden Schlüssels abgerufen werden kann. Jeder Schlüssel wird einem bestimmten Wert in einer HashMap zugeordnet.

Durch die Verwendung von Schlüsseln während der Iterationen können wir viel schneller auf die entsprechenden Werte zugreifen. Daher wird die HashMap als effiziente und wesentliche Datenstruktur beim Abrufen von Werten mit Schlüsseln und Werten beliebigen Typs angesehen.

Vor C++ 11 war eine standardmäßig definierte Hash-Tabelle nicht in der Standardbibliothek von C++ vorhanden, aber etwas andere Implementierer hatten nicht standardmäßige Varianten der Hash-Tabelle, oft als HashMap bezeichnet. Zusammen mit C++ 11 wurde der Standardbibliothek eine Standardimplementierung der Hashtabelle hinzugefügt.

Aufgrund verschiedener Variationen der Hash-Tabelle als HashMap aus verschiedenen Bibliotheken wurde jedoch entschieden, einen separaten Namen zum Aufrufen der neuen Implementierung zu verwenden, um Verwirrung zu vermeiden.

Daher ist in C++ std::unordered_map der alternative Name für die HashMap, aber eine andere Map verwendet das Schlüssel-Wert-Paar-Konzept, die std::map.

Es gibt wesentliche Unterschiede zwischen std::unordered_map und std::map. Wie der Name schon sagt, sind die Elemente in der std::unordered_map ungeordnet, während die Elemente in der std::map geordnet sind.

Verwendung von HashMap mit std::map in C++

std::map gehört zur Kategorie der assoziativen Container, wo die Elemente in abgebildeten Schlüssel-Wert-Paaren gespeichert werden. In std::map und std::unordered_map sollte der Schlüssel immer eindeutig sein, aber es kann mehrere eindeutige Schlüssel geben, bei denen der zugeordnete Wert ähnlich ist.

Die std::map wird mit Self-Balancing Binary Search Tree (AVL-Baum/Rot-Schwarz-Baum) implementiert. Das Hauptmerkmal von BST (Self-Balancing Binary Search Tree) ist, dass die Höhe beim Einfügen und Löschen von Elementen immer automatisch auf einem Minimum gehalten wird.

In std::map hängt die durchschnittliche Zeitkomplexität logarithmisch von der Anzahl der zu speichernden Elemente ab; daher dauert es im Durchschnitt O(log n) Zeit, bis eine Operation stattfindet. In O(log n) bezieht sich O auf die Big O-Notation und n auf die Anzahl der gespeicherten Elemente.

Daher sind BSTs beim Erstellen und Pflegen geordneter Listen hilfreich.

Beispiel:

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

using namespace std;

int main() {
  map<int, string> Players;

  Players.insert(std::pair<int, string>(2, "Lin Dan"));
  Players.insert(std::pair<int, string>(1, "Chen Long"));

  cout << "Number of Players " << Players.size() << endl;
  for (map<int, string>::iterator it = Players.begin(); it != Players.end();
       ++it) {
    cout << (*it).first << ": " << (*it).second << endl;
  }
}

Ausgabe:

Number of Players 2
1: Chen Long
2: Lin Dan

Verwendung von HashMap mit std::unordered_map in C++

std::unordered_map wird unter Verwendung der Hash-Tabelle in C++ implementiert. Auch Hash-Tabellen gehören zu assoziativen Containern. Die zugeordneten Werte werden in einer Hash-Tabelle in einem Array von Buckets oder Slots gespeichert, aus denen die erforderlichen Werte abgerufen werden können.

Diese Indizierung erfolgt über die Hash-Funktion, Hash-Code. Die durchschnittliche Zeitkomplexität für das Suchen, Einfügen und Löschen einer std::unordered_map beträgt O(1), wobei O die Big O-Notation ist, dies ist der Hauptgrund, warum die std::unordered_map ist sehr effizient.

Beispiel:

#include <iostream>
#include <unordered_map>

using namespace std;

int main() {
  unordered_map<string, int> info;

  info["Age"] = 18;
  info["Year"] = 2022;
  info["Number of Players"] = 15;

  for (auto x : info) cout << x.first << " " << x.second << endl;
}

Ausgabe:

Number of Players 15
Year 2022
Age 18

Hauptunterschiede und wann die einzelnen Maps in C++ verwendet werden sollten

Wenn man std::unordered_map und std::map vergleicht, ist der Effizienzunterschied zwischen den beiden enorm.

std::unordered_map hat eindeutig einen erheblichen Leistungsvorsprung gegenüber std::map. Dies liegt hauptsächlich daran, dass std::unordered_map Werte direkt adressieren kann, wenn sie in Slots platziert werden, und daher keine Reihenfolge hat, die beibehalten werden muss.

Andererseits hat eine std::map eine Ordnung, die beibehalten werden muss; daher verbraucht es mehr Zeit. Diese Effizienz ist bei kleinen Datensätzen möglicherweise nicht sichtbar, bei großen Datensätzen ist dieser Unterschied jedoch enorm.

std::unordered_map kann verwendet werden, wenn auf ein einzelnes Element aus einem Datensatz zugegriffen wird oder wenn eine Anzahl von Elementen beibehalten wird, wenn keine Reihenfolge erforderlich ist.

std::map hat auch einige Vorteile gegenüber std::unordered_map. Im Allgemeinen können BSTs schneller implementiert werden als eine Hash-Tabelle, und wir können dies auf unsere bevorzugte Weise tun, aber für das Hashing müssen wir uns stark auf Bibliotheken verlassen.

Daher lässt sich std::map im Vergleich zur std::unordered_map einfach implementieren. Auch beim Sortieren ist es viel einfacher, Schlüssel in std::map als in std::unordered_map zu sortieren, weil inorder traversing keine natürliche Operation für Hash-Tabellen ist, aber für BSTs.

std::map kann in Situationen wie dem Drucken von Daten in sortierter Reihenfolge verwendet werden, wo die Daten für Suchanfragen, Bestellstatistiken usw. geordnet werden müssen.

Sowohl std::map als auch std::unordered_map haben gewisse Ähnlichkeiten und Unterschiede, die je nach Bedarf manipuliert werden können.