Detaillierte Einführung in die Implementierung von Hash-Tabellen durch JavaScript

Dieser Artikel vermittelt Ihnen relevantes Wissen über Javascript. Er stellt hauptsächlich die damit verbundenen Probleme zur Implementierung von Hash-Tabellen vor. Die gesamte Struktur des Arrays, in das die endgültigen Daten eingefügt werden, und das Ergebnis ist die Hash-Tabelle. hoffe es hilft allen.

Verwandte Empfehlungen: Javascript-Lerntutorial

Hash-Tabellen werden normalerweise basierend auf Arrays implementiert, aber im Vergleich zu Arrays hat es viele Vorteile:

1. Es kann ein sehr schnelles Einfügen ermöglichen – Lösch-Suche Operationen
2. Egal wie viele Daten vorhanden sind, das Einfügen und Löschen erfordert nahezu konstante Zeit: das heißt O(1)-Zeitniveau. Tatsächlich sind dafür nur wenige Maschinenanweisungen erforderlich.
3. Hash-Tabellen sind schneller als Bäume, und Sie können die gewünschten Elemente grundsätzlich sofort finden.
4. Hash-Tabellen sind viel einfacher zu programmieren als Bäume Die Hash-Tabelle ist nicht in Ordnung, daher können die Elemente nicht auf feste Weise durchlaufen werden

Normalerweise dürfen die Schlüssel in der Hash-Tabelle nicht wiederholt werden, und dieselben Schlüssel können nicht als Schlüssel platziert werden, der zum Speichern verschiedener Elemente verwendet wird

Die Speicherplatznutzung ist nicht hoch, die unterste Ebene verwendet Arrays und einige Zellen werden nicht verwendet

1. Was ist eine Hash-Tabelle?
3. Hash-Tabellen sind nicht leicht zu verstehen, im Gegensatz zu Arrays, verknüpften Listen und Bäumen, die ihre Struktur und Prinzipien in Form von Grafiken ausdrücken können.

Die Struktur der Hash-Tabelle ist

Array, aber ihre Magie liegt in einer Transformation des

Indexwerts. Diese Transformation kann als

Hash-Funktion
• bezeichnet werden, die über die Hash-Funktion
HashCode
• erhalten werden kann. Einige Konzepte von Hash-Tabellen
Hashifizierung:

Der Prozess der Umwandlung von

großen Zahlen in Indizes innerhalb des Array-Bereichs

wird

Hashing
• genannt; ha Hash-Funktion: Wir konvertieren normalerweise Wörter in große Zahlen und fügen Sie die Code-Implementierung des
Hashing
• großer Zahlen in eine Funktion ein, die Hash-Funktion genannt wird; Hash-Tabelle: Kapseln Sie die gesamte Struktur in das Array in die die endgültigen Daten eingefügt werden und das Ergebnis eine Hash-Tabelle
ist.
• Probleme, die noch gelöst werden müssen: Der gehashte Index ist immer noch möglich duplizieren
Wie kann dieses Problem gelöst werden? Diese Situation nennt man

Konflikt

, Konflikt ist unvermeidlich, wir können nur

den Konflikt lösen

.
• Methoden zur KonfliktlösungZwei gängige Lösungen zur Konfliktlösung:
Option 1:

Kettenadressenmethode

(

Zip-Methode

);

Wie in der Abbildung unten gezeigt, werden wir jede Nummer Die Restoperation wird für

10
• ausgeführt und der Bereich des Restes 0~9 wird als Indexwert des Arrays verwendet. Darüber hinaus speichert die Position, die jedem Indexwert im Array entspricht, nicht mehr eine Zahl, sondern ein Array oder eine
verknüpfte Liste

bestehend aus Zahlen mit demselben Rest nach einer Restoperation.

Zusammenfassung: Die Möglichkeit, Konflikte mit der Kettenadressmethode zu lösen, besteht darin, dass jede Array-Einheit nicht mehr

einzelne Daten

speichert, sondern eine Kette

. Die häufig verwendete Datenstruktur für diese Kette ist

Array oder verknüpfte Liste, die beiden Datenstrukturen sind bei der Suche gleichermaßen effizient (da die Kette im Allgemeinen nicht zu viele Elemente enthält). Option 2: Methode der offenen Adresse; Die Hauptarbeitsmethode der Methode der offenen Adresse besteht darin, leere Zellen zu finden

, um

widersprüchliche
• Datenelemente zu platzieren.

Entsprechend den verschiedenen Methoden zur Erkennung der Position leerer Zellen kann sie in drei Methoden unterteilt werden: Lineare Erkennung

Sekundäre Erkennung

• Rehash-Methode
• Du kannst siehe Mit zunehmendem Füllfaktor nimmt die durchschnittliche Erkennungslänge linear und sanft zu. Die Kettenadressmethode wird häufig in der Entwicklung verwendet. Beispielsweise wird die Kettenadressmethode in HashMap in Java verwendet.
• Ausgezeichnete Hash-FunktionDer Vorteil einer Hash-Tabelle ist ihre Geschwindigkeit, sodass die Hash-Funktion keine komplexen Algorithmen verwenden kann, die viel Leistung verbrauchen. Eine Möglichkeit, die Geschwindigkeit zu verbessern, besteht darin,
Multiplikationen und Divisionen

in der Hash-Funktion zu minimieren.

Eine leistungsstarke Hash-Funktion sollte die folgenden zwei Vorteile haben:

• Schnelle Berechnung;
• Schnelle Berechnung

Horners Gesetz wird in China auch

Qin Jius Algorithmus genannt

Wann Um den Wert eines Polynoms zu ermitteln, berechnen Sie zunächst den Wert des linearen Polynoms in der innersten Klammer und berechnen Sie dann den Wert des linearen Polynoms Schicht für Schicht von innen nach außen. Dieser Algorithmus wandelt den Wert des Polynoms f(x) n-Grades in den Wert von Polynomen n-Grads um.

Vor der Transformation:

Anzahl der Multiplikationen: n (n+1)/2-mal;

Anzahl der Additionen: n-mal;

Nach der Transformation:

• Anzahl der Multiplikationen: n-mal ;

Anzahl der Additionen: n-mal;

Wenn großes O zur Darstellung der Zeitkomplexität verwendet wird, wird es direkt von

O(N2)

vor der Transformation auf
• O(N)
reduziert.
• Gleichmäßige Verteilung

Um sicherzustellen, dass die Daten gleichmäßig in der Hash-Tabelle verteilt sind, wenn wir Konstanten verwenden müssen, versuchen Sie,

Primzahlen

zu verwenden: die Länge der Hash-Tabelle; die Basis der N-ten Potenz usw.

HashMap in Java verwendet die Kettenadressmethode und die für das Hashing verwendete Formel lautet: index = HashCode (Schlüssel) & (Länge-1) Das heißt, die Daten werden für - und -Operationen in Binärdateien konvertiert. und es handelt sich nicht um eine Restoperation. Auf diese Weise verarbeitet der Computer direkt Binärdaten, was effizienter ist. Bei der Ausführung von

- und

-Operationen, die als Big Data bezeichnet werden, treten jedoch Probleme bei JavaScript auf, sodass die Restoperation weiterhin verwendet wird, wenn JavaScript zum Implementieren von Hashing verwendet wird.

                    function HashTable() {
                // 存放相关的元素
                this.storage = [];
                // 存了多少数据
                this.count = 0;
                // 用于标记数组中一共存放了多少个元素
                this.limit = 7;
                /*
           设计哈希函数
           ①将字符串转成比较大的数字
           ②将大的数字hashCode压缩到数组范围之内
            */
                HashTable.prototype.hashFunction = function (str, size) {
                    var hashCode = 0;
                    //秦九韶算法（霍纳算法）
                    // 哈希表的长度、N次幂的底数等尽量选取质数
                    for (var i = 0; i  this.limit * 0.75) {
                        var newLimit = this.limit * 2;
                        var prime = this.getPrime(newLimit);
                        this.resize(prime);
                    }
                };
                // 获取
                HashTable.prototype.get = function (key) {
                    var index = this.hashFunction(key, this.limit);
                    var bucket = this.storage[index];
                    if (bucket == null) return null;
                    for (var i = 0; i  7 && this.count  0 ? false : true;
                };
                // size
                HashTable.prototype.size = function () {
                    return this.count;
                };
                // toString
                HashTable.prototype.toString = function () {
                    var str = '';
                    for (var i = 0; i 

Verwandte Empfehlungen: Javascript-Lerntutorial

Das obige ist der detaillierte Inhalt vonDetaillierte Einführung in die Implementierung von Hash-Tabellen durch JavaScript. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!