Was ist der beste Weg, um eine HashMap in C ++ zu verwenden?

174

Ich weiß, dass STL eine HashMap-API hat, aber ich kann keine gute und gründliche Dokumentation mit guten Beispielen dafür finden.

Alle guten Beispiele werden geschätzt.

user855
quelle
Fragen Sie nach der C ++ 1x hash_map oder nach der std :: map?
Philant
2
Ich möchte so etwas wie eine java.util.HashMap in C ++ und die standardisierte Methode, wenn es eine gibt. Sonst die beste nicht standardmäßige Bibliothek. Was verwenden C ++ - Entwickler normalerweise, wenn sie eine HashMap benötigen?
user855

Antworten:

237

Die Standardbibliothek enthält die geordneten und die ungeordneten Kartencontainer ( std::mapund std::unordered_map). In einer geordneten Karte werden die Elemente nach dem Schlüssel sortiert, einfügen und der Zugriff erfolgt in O (log n) . Normalerweise verwendet die Standardbibliothek intern rot-schwarze Bäume für geordnete Karten. Dies ist jedoch nur ein Implementierungsdetail. In einer ungeordneten Karte ist das Einfügen und der Zugriff in O (1). Es ist nur ein anderer Name für eine Hashtabelle.

Ein Beispiel mit (bestellt) std::map:

#include <map>
#include <iostream>
#include <cassert>

int main(int argc, char **argv)
{
  std::map<std::string, int> m;
  m["hello"] = 23;
  // check if key is present
  if (m.find("world") != m.end())
    std::cout << "map contains key world!\n";
  // retrieve
  std::cout << m["hello"] << '\n';
  std::map<std::string, int>::iterator i = m.find("hello");
  assert(i != m.end());
  std::cout << "Key: " << i->first << " Value: " << i->second << '\n';
  return 0;
}

Ausgabe:

23
Schlüssel: Hallo Wert: 23

Wenn Sie in Ihrem Container bestellen müssen und mit der O (log n) -Laufzeit zufrieden sind, verwenden Sie einfach std::map.

Andernfalls, wenn Sie wirklich eine Hash-Tabelle (O (1) insert / Zugang) benötigen, überprüfen std::unordered_map, die ein ähnliches hat std::mapAPI (zB in dem obigen Beispiel müssen Sie nur noch das Suchen und Ersetzen mapmit unordered_map).

Der unordered_mapContainer wurde mit der C ++ 11-Standardversion eingeführt . Abhängig von Ihrem Compiler müssen Sie daher C ++ 11-Funktionen aktivieren (z. B. wenn Sie GCC 4.8 verwenden, müssen Sie diese zu -std=c++11CXXFLAGS hinzufügen ).

Noch vor der Veröffentlichung von C ++ 11 wurde GCC unterstützt unordered_map- im Namespace std::tr1. Daher können Sie für alte GCC-Compiler versuchen, es wie folgt zu verwenden:

#include <tr1/unordered_map>

std::tr1::unordered_map<std::string, int> m;

Es ist auch Teil von Boost, dh Sie können den entsprechenden Boost-Header für eine bessere Portabilität verwenden.

maxschlepzig
quelle
1
Während die Standardbibliothek keinen auf Hash-Tabellen basierenden Container hat, enthalten fast alle Implementierungen hash_mapin irgendeiner Form die SGI STL.
James McNellis
@ JamesMcNellis, die unordered_map oder hash_map für die HashMap-Implementierung
empfohlen wird
2
@ShameelMohamed, 2017, dh 6 Jahre nach C ++ 11 sollte es schwierig sein, eine STL zu finden, die keine bietet unordered_map. Daher gibt es keinen Grund, den Nichtstandard in Betracht zu ziehen hash_map.
Maxschlepzig
30

A hash_mapist eine ältere, nicht standardisierte Version dessen, was zu Standardisierungszwecken als a bezeichnet wird unordered_map(ursprünglich in TR1 und seit C ++ 11 im Standard enthalten). Wie der Name schon sagt, unterscheidet es sich std::maphauptsächlich davon, ungeordnet zu sein. Wenn Sie beispielsweise eine Karte von begin()bis durchlaufen end(), erhalten Sie Elemente in der Reihenfolge nach Schlüssel 1 , aber wenn Sie durch ein unordered_mapvon begin()bis iterieren end(), erhalten Sie Elemente in a mehr oder weniger willkürliche Reihenfolge.

Es unordered_mapwird normalerweise eine konstante Komplexität von A erwartet. Das heißt, das Einfügen, Nachschlagen usw. dauert normalerweise im Wesentlichen eine feste Zeit, unabhängig davon, wie viele Elemente in der Tabelle enthalten sind. A std::maphat eine Komplexität, die logarithmisch in Bezug auf die Anzahl der gespeicherten Elemente ist. Dies bedeutet, dass die Zeit zum Einfügen oder Abrufen eines Elements mit zunehmender Größe der Karte langsam ansteigt. Wenn zum Beispiel 1 Mikrosekunde benötigt wird, um eines von 1 Million Elementen zu suchen, können Sie damit rechnen, dass es ungefähr 2 Mikrosekunden dauert, um eines von 2 Millionen Elementen zu suchen, 3 Mikrosekunden für eines von 4 Millionen Elementen, 4 Mikrosekunden für eines von 8 Millionen Gegenstände usw.

Aus praktischer Sicht ist das jedoch nicht die ganze Geschichte. Eine einfache Hash-Tabelle hat von Natur aus eine feste Größe. Die Anpassung an die Anforderungen variabler Größe für einen Allzweckcontainer ist nicht trivial. Infolgedessen sind Operationen, die die Tabelle (möglicherweise) vergrößern (z. B. Einfügen), möglicherweise relativ langsam (das heißt, die meisten sind ziemlich schnell, aber in regelmäßigen Abständen ist eine viel langsamer). Suchvorgänge, bei denen die Größe der Tabelle nicht geändert werden kann, sind im Allgemeinen viel schneller. Infolgedessen sind die meisten Hash-basierten Tabellen in der Regel am besten, wenn Sie im Vergleich zur Anzahl der Einfügungen viele Suchvorgänge durchführen. In Situationen, in denen Sie viele Daten einfügen, durchlaufen Sie die Tabelle einmal, um die Ergebnisse abzurufen (z. B. die Anzahl der eindeutigen Wörter in einer Datei zu zählen)std::map wird genauso schnell und möglicherweise sogar noch schneller sein (aber auch hier ist die Rechenkomplexität unterschiedlich, so dass dies auch von der Anzahl der eindeutigen Wörter in der Datei abhängen kann).


1 Wenn die Reihenfolge beim Erstellen der Karte std::less<T>standardmäßig durch den dritten Vorlagenparameter definiert wird .

Jerry Sarg
quelle
1
Mir ist klar, dass ich 9 Jahre nach der Veröffentlichung der Antwort komme, aber ... haben Sie einen Link zu einem Dokument, in dem erwähnt wird, dass eine ungeordnete Karte kleiner werden kann? Normalerweise wachsen Standard-Sammlungen nur. Wenn Sie viele Daten einfügen, aber im Voraus mehr oder weniger wissen, wie viele Schlüssel Sie einfügen werden, können Sie außerdem die Größe der Karte bei der Erstellung angeben, wodurch die Kosten für die Größenänderung im Grunde genommen ungültig werden (da keine vorhanden sind). .
Zonko
@ Zonko: Entschuldigung, ich habe das nicht bemerkt, als ich gefragt wurde. Soweit ich weiß, wird eine ungeordnete Karte nur als Reaktion auf einen Anruf verkleinert rehash. Wenn Sie aufrufen rehash, geben Sie eine Größe für die Tabelle an. Diese Größe wird verwendet, es sei denn, dies würde den für die Tabelle angegebenen maximalen Lastfaktor überschreiten (in diesem Fall wird die Größe automatisch erhöht, um den Lastfaktor in Grenzen zu halten).
Jerry Coffin
22

Hier ist ein vollständigeres und flexibleres Beispiel, bei dem die erforderlichen Includes zum Generieren von Kompilierungsfehlern nicht ausgelassen werden:

#include <iostream>
#include <unordered_map>

class Hashtable {
    std::unordered_map<const void *, const void *> htmap;

public:
    void put(const void *key, const void *value) {
            htmap[key] = value;
    }

    const void *get(const void *key) {
            return htmap[key];
    }

};

int main() {
    Hashtable ht;
    ht.put("Bob", "Dylan");
    int one = 1;
    ht.put("one", &one);
    std::cout << (char *)ht.get("Bob") << "; " << *(int *)ht.get("one");
}

Immer noch nicht besonders nützlich für Schlüssel, es sei denn, sie sind als Zeiger vordefiniert, da ein übereinstimmender Wert nicht ausreicht! (Da ich jedoch normalerweise Zeichenfolgen für Schlüssel verwende, sollte dieses Problem durch Ersetzen von "const void *" in der Schlüsseldeklaration durch "Zeichenfolge" behoben werden.)

Jerry Miller
quelle
4
Ich muss sagen, dieses Beispiel ist eine sehr schlechte Praxis in C ++. Sie verwenden eine stark typisierte Sprache und zerstören sie, indem Sie sie verwenden void*. Für den Anfang gibt es keinen Grund, das zu verpacken, unordered_mapda es Teil des Standards ist und die Wartbarkeit des Codes verringert. Wenn Sie darauf bestehen, es einzuwickeln, verwenden Sie templates. Genau dafür sind sie da.
Guyarad
Stark getippt? Sie meinen wahrscheinlich statisch getippt. Die Tatsache, dass er lautlos von const char ptr zu void wechseln kann, macht C ++ statisch, aber nicht stark typisiert. Es gibt Typen, aber der Compiler sagt nichts, es sei denn, Sie aktivieren ein obskures Flag, das höchstwahrscheinlich nicht vorhanden ist.
Sahsahae
6

Beweise, std::unordered_mapdie eine Hash-Map in GCC stdlibc ++ 6.4 verwenden

Dies wurde erwähnt unter: https://stackoverflow.com/a/3578247/895245, aber in der folgenden Antwort: Welche Datenstruktur befindet sich in std :: map in C ++? Ich habe weitere Beweise dafür für die Implementierung von GCC stdlibc ++ 6.4 gegeben durch:

  • GDB-Schritt beim Debuggen in die Klasse
  • Analyse der Leistungsmerkmale

Hier ist eine Vorschau des in dieser Antwort beschriebenen Leistungsmerkmalsdiagramms:

Geben Sie hier die Bildbeschreibung ein

Verwendung einer benutzerdefinierten Klassen- und Hashfunktion mit unordered_map

Diese Antwort lautet: C ++ unordered_map mit einem benutzerdefinierten Klassentyp als Schlüssel

Auszug: Gleichheit:

struct Key
{
  std::string first;
  std::string second;
  int         third;

  bool operator==(const Key &other) const
  { return (first == other.first
            && second == other.second
            && third == other.third);
  }
};

Hash-Funktion:

namespace std {

  template <>
  struct hash<Key>
  {
    std::size_t operator()(const Key& k) const
    {
      using std::size_t;
      using std::hash;
      using std::string;

      // Compute individual hash values for first,
      // second and third and combine them using XOR
      // and bit shifting:

      return ((hash<string>()(k.first)
               ^ (hash<string>()(k.second) << 1)) >> 1)
               ^ (hash<int>()(k.third) << 1);
    }
  };

}
Ciro Santilli 郝海东 冠状 病 六四 事件 法轮功
quelle
0

Für diejenigen von uns, die versuchen, herauszufinden, wie sie ihre eigenen Klassen hashen können, während sie noch die Standardvorlage verwenden, gibt es eine einfache Lösung:

  1. In Ihrer Klasse müssen Sie eine Überladung des Gleichheitsoperators definieren ==. Wenn Sie nicht wissen, wie das geht, bietet GeeksforGeeks ein großartiges Tutorial: https://www.geeksforgeeks.org/operator-overloading-c/

  2. Deklarieren Sie unter dem Standard-Namespace eine Vorlagenstruktur namens Hash mit Ihrem Klassennamen als Typ (siehe unten). Ich habe einen großartigen Blogpost gefunden, der auch ein Beispiel für die Berechnung von Hashes mit XOR und Bitshifting zeigt, aber das liegt außerhalb des Rahmens dieser Frage, enthält aber auch detaillierte Anweisungen zur Verwendung von Hash-Funktionen sowie https://prateekvjoshi.com/ 2014/06/05 / using-hash-function-in-c-for-user-defined-classes /

namespace std {

  template<>
  struct hash<my_type> {
    size_t operator()(const my_type& k) {
      // Do your hash function here
      ...
    }
  };

}
  1. Um eine Hashtabelle mit Ihrer neuen Hash-Funktion zu implementieren, müssen Sie nur eine erstellen std::mapoder std::unordered_mapwie gewohnt und my_typeals Schlüssel verwenden. Die Standardbibliothek verwendet automatisch die zuvor definierte Hash-Funktion (in Schritt 2) für Hash deine Schlüssel.
#include <unordered_map>

int main() {
  std::unordered_map<my_type, other_type> my_map;
}
iggy12345
quelle