So implementieren Sie eine einfache Hash-Tabelle in JavaScript

Wie schön ist {}?

Sie können Werte nach Schlüssel speichern und auf sehr kostengünstige Weise abrufen ( O(1)dazu später mehr).

In diesem Beitrag möchte ich eine sehr einfache Hash-Tabelle implementieren und einen Blick auf deren Innenleben werfen, um eine der genialsten Ideen in der Informatik zu erklären.

Das Problem

Stellen Sie sich vor, Sie erstellen eine neue Programmiersprache: Sie beginnen mit ziemlich einfachen Typen (Zeichenfolgen, Ganzzahlen, Gleitkommazahlen usw.) und implementieren dann sehr grundlegende Datenstrukturen. Zuerst kommt das Array ( []), dann die Hash-Tabelle (auch bekannt als Dictionary, assoziatives Array, Hashmap, Map und ... die Liste geht weiter).

Haben Sie sich jemals gefragt, wie sie funktionieren? Wie sie so verdammt schnell sind?

Nehmen wir an, JavaScript hatte kein {}oder new Map(), und implementieren wir unser eigenes DumbMap!

Ein Hinweis zur Komplexität

Bevor wir den Ball ins Rollen bringen, müssen wir verstehen, wie die Komplexität einer Funktion funktioniert: Wikipedia bietet eine gute Auffrischung der Rechenkomplexität, aber ich werde eine kurze Erklärung für die faulen hinzufügen.

Die Komplexität misst, wie viele Schritte für unsere Funktion erforderlich sind - je weniger Schritte, desto schneller die Ausführung (auch als „Laufzeit“ bezeichnet).

Schauen wir uns den folgenden Ausschnitt an:

function fn(n, m) { return n * m}

Die rechnerische Komplexität (von nun an einfach „Komplexität“) von fnist O(1), was bedeutet, dass sie konstant ist (Sie können O(1)als „ die Kosten sind eins “ lesen ): Unabhängig davon, welche Argumente Sie übergeben, muss die Plattform, auf der dieser Code ausgeführt wird, nur eine Operation ausführen (multiplizieren nmit m). Da es sich wiederum um eine Operation handelt, werden die Kosten als bezeichnet O(1).

Die Komplexität wird gemessen, indem angenommen wird, dass Argumente Ihrer Funktion sehr große Werte haben könnten. Schauen wir uns dieses Beispiel an:

function fn(n, m) { let s = 0
 for (i = 0; i < 3; i++) { s += n * m }
 return s}

Sie würden denken, dass seine Komplexität ist O(3), richtig?

Da die Komplexität im Zusammenhang mit sehr großen Argumenten gemessen wird, neigen wir wiederum dazu, Konstanten zu „löschen“ und O(3)dasselbe zu betrachten wie O(1). Selbst in diesem Fall würden wir also sagen, dass die Komplexität von fnist O(1). Unabhängig vom Wert von nund msind Sie am Ende immer drei Operationen - was wiederum (daher O(1)) konstante Kosten darstellt .

Dieses Beispiel ist etwas anders:

function fn(n, m) { let s = []
 for (i = 0; i < n; i++) { s.push(m) }
 return s}

Wie Sie sehen, schleifen wir so oft wie der Wert von n, der in Millionenhöhe liegen könnte. In diesem Fall definieren wir die Komplexität dieser Funktion als O(n), da Sie so viele Operationen ausführen müssen, wie der Wert eines Ihrer Argumente.

Andere Beispiele?

function fn(n, m) { let s = []
 for (i = 0; i < 2 * n; i++) { s.push(m) }
 return s}

Dieses Beispiel wiederholt 2 * nZeiten, was bedeutet, dass die Komplexität sein sollte O(2n). Da wir erwähnt haben, dass Konstanten bei der Berechnung der Komplexität einer Funktion „ignoriert“ werden, wird dieses Beispiel auch als klassifiziert O(n).

Einer noch?

function fn(n, m) { let s = []
 for (i = 0; i < n; i++) { for (i = 0; i < n; i++) { s.push(m) } }
 return s}

Hier werden wir ninnerhalb der Hauptschleife wiederholt und erneut wiederholt, was bedeutet, dass die Komplexität "quadriert" ist ( n * n): Wenn n2 ist, werden wir s.push(m)4 Mal ausgeführt, wenn 3, werden wir 9 Mal ausgeführt, und so weiter.

In diesem Fall wird die Komplexität der Funktion als bezeichnet O(n²).

Ein letztes Beispiel?

function fn(n, m) { let s = []
 for (i = 0; i < n; i++) { s.push(n) }
 for (i = 0; i < m; i++) { s.push(m) }
 return s}

In diesem Fall haben wir keine verschachtelten Schleifen, aber wir durchlaufen zwei verschiedene Argumente zweimal: Die Komplexität ist definiert als O(n+m). Kristallklar.

Nachdem Sie gerade eine kurze Einführung (oder Auffrischung) zur Komplexität erhalten haben, ist es sehr leicht zu verstehen, dass eine Funktion mit Komplexität O(1)eine viel bessere Leistung erbringen wird als eine mit O(n).

Hash-Tabellen haben eine O(1)Komplexität: Für Laien sind sie superschnell . Lass uns weitermachen.

(Ich liege irgendwie auf Hash-Tabellen, die immer O(1)komplex sind, aber lese einfach weiter;))

Lassen Sie uns eine (dumme) Hash-Tabelle erstellen

Unsere Hash-Tabelle hat 2 einfache Methoden - set(x, y)und get(x). Beginnen wir mit dem Schreiben von Code:

Lassen Sie uns eine sehr einfache und ineffiziente Methode implementieren, um diese Schlüssel-Wert-Paare zu speichern und später abzurufen. Wir beginnen damit, sie in einem internen Array zu speichern (denken Sie daran, wir können sie nicht verwenden, {}da wir sie implementieren {}- umwerfend!):

Dann geht es einfach darum, das richtige Element aus der Liste zu holen:

Unser vollständiges Beispiel:

Unser DumbMap ist unglaublich! Es funktioniert sofort, aber wie wird es funktionieren, wenn wir eine große Anzahl von Schlüssel-Wert-Paaren hinzufügen?

Versuchen wir einen einfachen Benchmark. Wir werden zuerst versuchen, ein nicht vorhandenes Element in einer Hash-Tabelle mit sehr wenigen Elementen zu finden, und dann dasselbe in einem mit einer großen Anzahl von Elementen versuchen:

Die Ergebnisse? Nicht so ermutigend:

with very few records in the map: 0.118mswith lots of records in the map: 14.412ms

In unserer Implementierung müssen wir alle darin enthaltenen Elemente durchlaufen this.list, um eines mit dem passenden Schlüssel zu finden. Die Kosten sind O(n)und es ist ziemlich schrecklich.

Mach es schneller)

Wir müssen einen Weg finden, um zu vermeiden, dass wir unsere Liste durchlaufen: Zeit, um den Hash wieder in die Hash-Tabelle aufzunehmen .

Haben Sie sich jemals gefragt, warum diese Datenstruktur als Hash- Tabelle bezeichnet wird? Dies liegt daran, dass für die Tasten, die Sie festlegen und abrufen, eine Hashing-Funktion verwendet wird. Wir werden diese Funktion verwenden, um unseren Schlüssel in eine Ganzzahl umzuwandeln iund unseren Wert im Index iunserer internen Liste zu speichern . Da der Zugriff auf ein Element über seinen Index aus einer Liste konstante Kosten verursacht ( O(1)), hat die Hash-Tabelle auch Kosten von O(1).

Probieren wir es aus:

Hier verwenden wir das String-Hash-Modul, das einfach einen String in einen numerischen Hash konvertiert. Wir verwenden es, um Elemente im Index hash(key)unserer Liste zu speichern und abzurufen . Die Ergebnisse?

with lots of records in the map: 0.013ms

W - O - W. Das ist es, worüber ich spreche!

Wir müssen nicht alle Elemente in der Liste durchlaufen, und das Abrufen von Elementen aus DumbMapist superschnell!

Lassen Sie mich dies so einfach wie möglich formulieren: Hashing macht Hash-Tabellen äußerst effizient . Keine Magie. Nichts mehr. Nada. Nur eine einfache, kluge, geniale Idee.

Die Kosten für die Auswahl der richtigen Hashing-Funktion

Natürlich ist es sehr wichtig , eine schnelle Hashing-Funktion auszuwählen. Wenn wir hash(key)in wenigen Sekunden laufen, ist unsere Funktion unabhängig von ihrer Komplexität ziemlich langsam.

Gleichzeitig ist es sehr wichtig sicherzustellen, dass unsere Hashing-Funktion nicht viele Kollisionen erzeugt , da dies die Komplexität unserer Hash-Tabelle beeinträchtigen würde.

Verwirrt? Schauen wir uns Kollisionen genauer an.

Kollisionen

Sie könnten denken: „ Ah, eine gute Hashing-Funktion erzeugt niemals Kollisionen! ”: Nun, komm zurück in die reale Welt und denke noch einmal nach. Google konnte Kollisionen für den SHA-1-Hashing-Algorithmus erzeugen, und es ist nur eine Frage der Zeit oder der Rechenleistung, bevor eine Hashing-Funktion denselben Hash für zwei verschiedene Eingaben knackt und zurückgibt. Nehmen Sie immer an, dass Ihre Hashing-Funktion Kollisionen erzeugt, und implementieren Sie die richtige Verteidigung gegen solche Fälle.

In diesem Fall versuchen wir, eine hash()Funktion zu verwenden, die viele Kollisionen erzeugt:

Diese Funktion verwendet ein Array von 10 Elementen zum Speichern von Werten, was bedeutet, dass Elemente wahrscheinlich ersetzt werden - ein böser Fehler in unserem DumbMap:

Um das Problem zu beheben, können wir einfach mehrere Schlüssel-Wert-Paare im selben Index speichern. Ändern wir also unsere Hash-Tabelle:

Wie Sie vielleicht bemerken, greifen wir hier auf unsere ursprüngliche Implementierung zurück: Speichern Sie eine Liste von Schlüssel-Wert-Paaren und durchlaufen Sie jedes von ihnen. Dies wird ziemlich langsam sein, wenn es für einen bestimmten Index der Liste viele Kollisionen gibt.

Vergleichen wir dies mit unserer eigenen hash()Funktion, die Indizes von 1 bis 10 generiert:

with lots of records in the map: 11.919ms

und mithilfe der Hash-Funktion von string-hash, die zufällige Indizes generiert:

with lots of records in the map: 0.014ms

Whoa! Die Auswahl der richtigen Hashing-Funktion ist mit Kosten verbunden - schnell genug, um unsere Ausführung nicht von selbst zu verlangsamen, und gut genug, um nicht viele Kollisionen zu verursachen.

Im Allgemeinen O (1)

Erinnerst du dich an meine Worte?

Hashtabellen haben eine O(1)Komplexität

Nun, ich habe gelogen: Die Komplexität einer Hash-Tabelle hängt von der von Ihnen ausgewählten Hashing-Funktion ab. Je mehr Kollisionen Sie erzeugen, desto mehr tendiert die Komplexität dazu O(n).

Eine Hashing-Funktion wie:

function hash(key) { return 0}

würde bedeuten, dass unsere Hash-Tabelle eine Komplexität von hat O(n).

Aus diesem Grund hat die Rechenkomplexität im Allgemeinen drei Messgrößen: Best-, Durchschnitts- und Worst-Case-Szenarien. Hashtables sind O(1)in Best- und Average-Szenarien komplex, fallen jedoch O(n)in Worst-Case-Szenarien auf.

Denken Sie daran: Eine gute Hashing-Funktion ist der Schlüssel zu einer effizienten Hash-Tabelle - nicht mehr und nicht weniger.

Mehr zu Kollisionen…

Die Technik, die wir zur Behebung DumbMapvon Kollisionen verwendet haben, wird als separate Verkettung bezeichnet: Wir speichern alle Schlüsselpaare, die Kollisionen erzeugen, in einer Liste und durchlaufen sie.

Eine andere beliebte Technik ist die offene Adressierung:

  • In jedem Index unserer Liste speichern wir ein und ein einziges Schlüssel-Wert-Paar
  • Wenn Sie versuchen, ein Paar im Index zu speichern x, und wenn es bereits ein Schlüssel-Wert-Paar gibt, versuchen Sie, unser neues Paar im zu speichernx + 1
  • Wenn x + 1genommen, versuchen Sie es x + 2und so weiter ...
  • Wenn Sie ein Element abrufen, hacken Sie den Schlüssel und prüfen Sie, ob das Element an dieser Position ( x) mit unserem Schlüssel übereinstimmt
  • Wenn nicht, versuchen Sie, auf das Element an der Position zuzugreifen x + 1
  • Spülen und wiederholen, bis Sie am Ende der Liste angelangt sind oder wenn Sie einen leeren Index finden - das heißt, unser Element befindet sich nicht in der Hash-Tabelle

Klug, einfach, elegant und meist sehr effizient!

FAQs (oder TL; DR)

Hat eine Hash-Tabelle die Werte, die wir speichern?

Nein, Schlüssel werden gehasht, damit sie in eine Ganzzahl umgewandelt werden können i, und sowohl Schlüssel als auch Werte werden an der Position iin einer Liste gespeichert .

Erzeugen die von Hash-Tabellen verwendeten Hashing-Funktionen Kollisionen?

Absolut - also werden Hash-Tabellen mit Verteidigungsstrategien implementiert, um böse Fehler zu vermeiden.

Verwenden Hash-Tabellen intern eine Liste oder eine verknüpfte Liste?

Es kommt darauf an, dass beide funktionieren können. In unseren Beispielen verwenden wir das JavaScript-Array ( []), dessen Größe dynamisch geändert werden kann:

> a = []
> a[3] = 1
> a[ , 1 ]

Warum haben Sie für die Beispiele JavaScript ausgewählt? JS-Arrays SIND Hash-Tabellen!

Zum Beispiel:

> a = [][]
> a["some"] = "thing"'thing'
> a[ some: 'thing' ]
> typeof a'object'

Ich weiß, verdammtes JavaScript.

JavaScript ist „universell“ und wahrscheinlich die am einfachsten zu verstehende Sprache, wenn Sie sich einen Beispielcode ansehen. JS ist vielleicht nicht die beste Sprache, aber ich hoffe, diese Beispiele sind klar genug.

Ist Ihr Beispiel eine wirklich gute Implementierung einer Hash-Tabelle? Ist es wirklich so einfach?

Nein überhaupt nicht.

Werfen Sie einen Blick auf "Implementieren einer Hash-Tabelle in JavaScript" von Matt Zeunert, da Sie dadurch etwas mehr Kontext erhalten. Es gibt noch viel mehr zu lernen, daher würde ich Ihnen auch empfehlen, Folgendes zu überprüfen:

  • Paul Kubes Kurs über Hash-Tische
  • Implementierung unserer eigenen Hash-Tabelle mit separater Verkettung in Java
  • Algorithmen, 4. Ausgabe - Hash-Tabellen
  • Entwerfen einer schnellen Hash-Tabelle

Schlussendlich…

Hash-Tabellen sind eine sehr clevere Idee, die wir regelmäßig verwenden: Egal, ob Sie ein Wörterbuch in Python, ein assoziatives Array in PHP oder eine Map in JavaScript erstellen. Sie alle teilen die gleichen Konzepte und arbeiten wunderbar daran, dass wir Elemente durch einen Bezeichner zu (höchstwahrscheinlich) konstanten Kosten speichern und abrufen können.

Ich hoffe, Ihnen hat dieser Artikel gefallen und Sie können mir gerne Ihr Feedback mitteilen.

Ein besonderer Dank geht an Joe, der mir bei der Durchsicht dieses Artikels geholfen hat.

Adios!