Hash-Tabelle erklärt: Was es ist und wie es implementiert wird

Eine Hash-Tabelle, auch als Hash-Map bezeichnet, ist eine Datenstruktur, die Schlüssel Werten zuordnet. Es ist ein Teil einer Technik namens Hashing, der andere Teil ist eine Hash-Funktion. Eine Hash-Funktion ist ein Algorithmus, der einen Index erstellt, in dem ein Wert gefunden oder in der Hash-Tabelle gespeichert werden kann.

Einige wichtige Hinweise zu Hash-Tabellen:

  1. Werte werden nicht in einer sortierten Reihenfolge gespeichert.
  2. Sie müssen mögliche Kollisionen berücksichtigen. Dies geschieht normalerweise mit einer Technik, die als Verkettung bezeichnet wird. Verketten bedeutet, eine verknüpfte Liste von Werten zu erstellen, deren Schlüssel einem bestimmten Index zugeordnet sind.

Implementierung einer Hash-Tabelle

Die Grundidee hinter dem Hashing besteht darin, Schlüssel / Wert-Paare auf ein Array von Platzhaltern oder "Buckets" in der Hash-Tabelle zu verteilen.

Eine Hash-Tabelle besteht normalerweise aus einem Array verknüpfter Listen. Wenn Sie ein Schlüssel / Wert-Paar einfügen möchten, müssen Sie zuerst die Hash-Funktion verwenden, um den Schlüssel einem Index in der Hash-Tabelle zuzuordnen. Bei einem bestimmten Schlüssel kann die Hash-Funktion einen Index vorschlagen, in dem der Wert gefunden oder gespeichert werden kann:

index = f(key, array_size)

Dies erfolgt häufig in zwei Schritten:

hash = hashfunc(key) index = hash % array_size

Die Verwendung dieser Methode hashist unabhängig von der Größe der Hash-Tabelle. hashwird array_size - 1mit dem Modulo-Operator (%) auf einen Index reduziert - eine Zahl zwischen 0, dem Anfang des Arrays und dem Ende des Arrays.

Betrachten Sie die folgende Zeichenfolge S:

string S = “ababcd”

Sie müssen die Häufigkeit aller Zeichen in zählen S. Der einfachste Weg, dies zu tun, besteht darin, alle möglichen Zeichen zu durchlaufen und die Häufigkeit jedes einzelnen nacheinander zu zählen.

Dies funktioniert, ist aber langsam - die zeitliche Komplexität eines solchen Ansatzes beträgt O (26 * N), Nwobei die Größe der Zeichenfolge Smit 26 möglichen Zeichen von AZ multipliziert wird.

void countFre(string S) { for(char c = ‘a’;c <= ‘z’;++c) { int frequency = 0; for(int i = 0;i < S.length();++i) if(S[i] == c) frequency++; cout << c << ‘ ‘ << frequency << endl; } }

Ausgabe:

a 2 b 2 c 1 d 1 e 0 f 0 … z 0

Werfen wir einen Blick auf eine Lösung, die Hashing verwendet.

Nehmen Sie ein Array und verwenden Sie die Hash-Funktion, um die 26 möglichen Zeichen mit Indizes des Arrays zu hashen. Iterieren Sie dann Sund erhöhen Sie den Wert des aktuellen Zeichens der Zeichenfolge mit dem entsprechenden Index für jedes Zeichen.

Die Komplexität dieses Hashing-Ansatzes ist O (N), wobei N die Größe des Strings ist.

int Frequency[26]; int hashFunc(char c) { return (c - ‘a’); } void countFre(string S) { for(int i = 0;i < S.length();++i) { int index = hashFunc(S[i]); Frequency[index]++; } for(int i = 0;i < 26;++i) cout << (char)(i+’a’) << ‘ ‘ << Frequency[i] << endl; }

Ausgabe

a 2 b 2 c 1 d 1 e 0 f 0 … z 0

Hash-Kollisionen

Da Ihre Hash-Map wahrscheinlich erheblich kleiner ist als die Datenmenge, die Sie verarbeiten, sind Hash-Kollisionen unvermeidbar. Es gibt zwei Hauptansätze für den Umgang mit Kollisionen: Verkettung und offene Adressierung .

Verkettung

Wie bereits erwähnt, bedeutet Verkettung, dass für jedes Schlüssel / Wert-Paar in der Hash-Tabelle der Wert eine verknüpfte Liste von Daten und keine einzelne Zelle ist.

Stellen Sie sich zum Beispiel vor, dass der Schlüssel 152 den Wert "John Smith" enthält. Wenn der Wert "Sandra Dee" zum gleichen Schlüssel hinzugefügt wird, wird "Sandra Dee" unmittelbar nach "John Smith" als weiteres Element zum Schlüssel 152 hinzugefügt.

152: [["John Smith", "p01"]] ... 152: [["John Smith", "p01"] ["Sandra Dee", "p02"]]

Der Hauptnachteil der Verkettung ist die Zunahme der Zeitkomplexität. Anstelle von 0 (1) wie bei einer regulären Hash-Tabelle dauert jede Suche länger, da wir jede verknüpfte Liste durchlaufen müssen, um den richtigen Wert zu finden.

Offene Adressierung

Offene Adressierung bedeutet, dass Sie, sobald ein Wert einem bereits belegten Schlüssel zugeordnet ist, entlang der Schlüssel der Hash-Tabelle gehen, bis Sie einen leeren finden. Wenn beispielsweise "John Smith" 152 zugeordnet wurde, wird "Sandra Dee" dem nächsten offenen Index zugeordnet:

152: ["John Smith", "p01"] ... 152: ["John Smith", "p01"], 153: ["Sandra Dee", "p02"]

Der Hauptnachteil der offenen Adressierung besteht darin, dass sich die Werte beim Nachschlagen möglicherweise nicht auf der Key Map befinden, auf der Sie sie erwarten. Stattdessen müssen Sie verschiedene Teile der Hash-Tabelle durchlaufen, um den gewünschten Wert zu finden.