Mit der Hash-Tabelle können Sie eine assoziative Array-Datenstruktur (Wörterbuch) mit einer durchschnittlichen Leistung von O(1) für Einfüge-, Lösch- und Suchvorgänge implementieren.
Unten finden Sie ein Beispiel für die einfachste Implementierung einer Hash-Map in nodeJS:
Wie funktioniert es? Passen Sie auf Ihre Hände auf:
- Innerhalb der Hash-Map befindet sich ein Array
- Im Array-Element befindet sich ein Zeiger auf den ersten Knoten der verknüpften Liste
- Speicher wird für ein Array von Zeigern zugewiesen (z. B. 65535 Elemente)
- Sie implementieren eine Hash-Funktion, der Wörterbuchschlüssel ist die Eingabe, und am Ausgang kann sie alles tun, aber am Ende gibt sie den Index des Array-Elements zurück
So funktioniert die Aufnahme:
- Am Eingang liegt ein Schlüsselpaar – Wert
- Hash-Funktion gibt Index nach Schlüssel zurück
- Einen verknüpften Listenknoten aus einem Array nach Index abrufen
- Überprüfen Sie, ob es mit dem Schlüssel übereinstimmt
- Wenn es übereinstimmt, ersetzen Sie den Wert
- Wenn es nicht übereinstimmt, fahren Sie mit dem nächsten Knoten fort, bis wir einen Knoten mit dem erforderlichen Schlüssel finden oder finden.
- Wenn der Knoten immer noch nicht gefunden wird, erstellen Sie ihn am Ende der verknüpften Liste
So funktioniert die Suche nach Schlüssel:
- Am Eingang liegt ein Schlüsselpaar – Wert
- Hash-Funktion gibt Index nach Schlüssel zurück
- Einen verknüpften Listenknoten aus einem Array nach Index abrufen
- Überprüfen Sie, ob es mit dem Schlüssel übereinstimmt
- Wenn es übereinstimmt, wird der Wert zurückgegeben
- Wenn es nicht übereinstimmt, fahren Sie mit dem nächsten Knoten fort, bis wir einen Knoten mit dem erforderlichen Schlüssel finden oder finden.
Warum brauchen wir eine verknüpfte Liste innerhalb eines Arrays? Aufgrund möglicher Kollisionen bei der Berechnung der Hash-Funktion. In diesem Fall befinden sich mehrere verschiedene Schlüssel-Wert-Paare am selben Index im Array. In diesem Fall wird die verknüpfte Liste durchlaufen, um den erforderlichen Schlüssel zu finden.
Quellen
https://ru.wikipedia.org/wiki/Hash-Tabelle
https://www.youtube.com/watch?v=wg8hZxMRwcw
Quellcode
https://gitlab.com/demensdeum/datastructures
