Tag Archives: datastructures

Hash-Tabelle

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

Stapelmaschine und RPN

Angenommen, wir müssen einen einfachen Bytecode-Interpreter implementieren. Welchen Ansatz zur Implementierung dieser Aufgabe sollten wir wählen?

Datenstruktur Der Stack bietet die Möglichkeit, eine einfache Bytecode-Maschine zu implementieren. Funktionen und Implementierungen von Stack-Maschinen werden in vielen Artikeln im westlichen und inländischen Internet beschrieben; ich möchte nur erwähnen, dass die Java Virtual Machine ein Beispiel für eine Stack-Maschine ist.

Das Funktionsprinzip der Maschine ist einfach: Ein Programm mit Daten und Operationscodes (Opcodes) wird dem Eingang zugeführt und die erforderlichen Operationen werden durch Manipulationen am Stapel implementiert. Schauen wir uns ein Beispiel-Bytecode-Programm von meiner Stack-Maschine an:

пMVkcatS olleHП

Am Ausgang erhalten wir die Zeichenfolge „Hello StackVM“. Die Stapelmaschine liest das Programm von links nach rechts und lädt Daten Zeichen für Zeichen auf den Stapel, wenn ein Opcode im Symbol – implementiert den Befehl mithilfe des Stapels.

Beispiel für die Implementierung einer Stack-Maschine in nodejs:

Umgekehrte polnische Notation (RPN)

Stack -Maschinen sind auch einfach zum Implementieren von Taschenrechnern zu verwenden. Dafür verwenden sie umgekehrte polnische Notation (Postfix -Notation).
Beispiel einer regulären Infix-Notation:
2*2+3*4

Konvertiert in RPN:
22*34*+

Um den Postfix-Datensatz zu zählen, verwenden wir eine Stapelmaschine:
2– an die Spitze des Stapels (Stapel: 2)
2– an die Spitze des Stapels (Stapel: 2,2)
*– Holen Sie sich zweimal die Oberseite des Stapels, multiplizieren Sie das Ergebnis und senden Sie es an die Oberseite des Stapels (Stapel: 4)
3– an die Spitze des Stapels (Stapel: 4, 3)
4– an die Spitze des Stapels (Stapel: 4, 3, 4)
*– Holen Sie sich zweimal die Oberseite des Stapels, multiplizieren Sie das Ergebnis und senden Sie es an die Oberseite des Stapels (Stapel: 4, 12)
+– Holen Sie sich zweimal die Spitze des Stapels, addieren Sie das Ergebnis und senden Sie es an die Spitze des Stapels (Stapel: 16)

Wie Sie sehen können – Das Ergebnis der Operationen 16 verbleibt auf dem Stapel. Es kann durch Implementierung von Stapeldruck-Opcodes gedruckt werden, zum Beispiel:
p22*34*+P

P – Stapeldruck-Start-Opcode, p – Opcode zum Fertigstellen des Stapeldrucks und zum Senden der letzten Zeile zum Rendern.
Um arithmetische Operationen von Infix in Postfix umzuwandeln, wird der Algorithmus „Sorting Yard“ von Edsger Dijkstra verwendet. Ein Beispiel für die Implementierung finden Sie oben oder im Repository des NodeJS-Maschinenstack-Projekts unten.

Quellen

https:/ /tech.badoo.com/ru/article/579/interpretatory-bajt-kodov-svoimi-rukami/
https://ru.wikipedia.org/wiki/Обратная_польская_запись

Quellcode

https://gitlab.com/demensdeum/stackvm/< /p>