Detaillierte Erläuterung der JavaScript-Implementierung der Hash-Tabelle

1. Hash-Tabellenprinzip

Hash-Tabellen sind sehr wichtige Datenstrukturen. Fast alle Programmiersprachen haben direkte oder indirekte Anwendungsmöglichkeiten für diese Datenstruktur. Sie werden normalerweise auf Basis von Arrays implementiert. Damals hatten sie mehr Vorteile als Arrays:

• Es bietet sehr schnelle Einfüge-Lösch-Such-Operationen.
• Die Hash-Tabelle ist schneller als Zahlen und Sie können das gewünschte Element fast augenblicklich finden.
• Hash-Tabellen sind viel einfacher zu kodieren als Zahlen.

Allerdings haben Hash-Tabellen gegenüber Arrays auch einige Nachteile:

• Das Array in der Hash-Tabelle ist ungeordnet, sodass die Elemente nicht auf eine festgelegte Weise durchlaufen werden können (z. B. von klein nach groß).
• Normalerweise sind doppelte Schlüssel in einer Hash-Tabelle nicht zulässig, und derselbe Schlüssel kann nicht in einer Hash-Tabelle platziert werden, um verschiedene Elemente zu speichern.

Also, was genau ist eine Hash-Tabelle?

Seine Struktur ist ein Array, aber die Magie liegt in einer Transformation des Indexwerts, die wir eine Hash-Funktion aufrufen können, durch die wir den HashCode erhalten.

Schauen wir uns als Nächstes ein Beispiel an:

Verwenden Sie eine Datenstruktur zum Speichern von Wortinformationen. Beispielsweise gibt es 50.000 Wörter. Nachdem Sie die Wörter gefunden haben, hat jedes Wort seine eigene spezifische Anwendung und so weiter. Wie sollen wir vorgehen?

Vielleicht könnten wir versuchen, die Buchstaben in entsprechende Indizes umzuwandeln. Aber wie können wir ein Zeichen in einen Array-Indexwert umwandeln? Gibt es eine Möglichkeit, Wörter in Array-Indexwerte umzuwandeln? Wenn das Wort in einen Array-Index umgewandelt wird und wir künftig die Informationen zu einem bestimmten Wort finden möchten, können wir entsprechend dem Indexwert in einem Schritt auf das gewünschte Element zugreifen. Wie konvertiert man also eine Zeichenfolge in einen Indexwert?

Tatsächlich gibt es viele Computercodierungssysteme, die die Buchstaben von Wörtern durch Zahlen ersetzen. Dabei handelt es sich um Zeichencodierung. Natürlich können wir unser eigenes Codierungssystem entwerfen, z. B. a ist 1, b ist 2, c ist 3 usw. Aber wie wandeln wir nun, da wir über ein Kodierungssystem verfügen, ein Wort in eine Zahl um?

Hier haben wir zwei Möglichkeiten:

Lösung 1: Zahlen addieren

Eine einfache Möglichkeit, ein Wort umzuwandeln, besteht darin, die Kodierung jedes Zeichens des Wortes zu summieren

Beispielsweise wird das Wort „cats“ in eine Zahl umgewandelt: 3+1+20+19=43, dann wird 43 im Array als Index des Wortes „cats“ gespeichert.

Allerdings gibt es bei dieser Lösung ein offensichtliches Problem: Viele Wörter enden möglicherweise mit dem Index 43.

Wir wissen, dass eine Indexwertposition in einem Array nur einen Datensatz speichern kann. Wenn später Daten gespeichert werden, führt dies zwangsläufig zum Überschreiben der Daten. Daher ist es offensichtlich unvernünftig, so viele Wörter in einem Index zu speichern.

Lösung 2: Multiplikation von Potenzen

Tatsächlich können die Zahlen, die wir normalerweise größer als 10 verwenden, durch Multiplikation von Potenzen als eindeutig ausgedrückt werden, zum Beispiel: 6543 = 6 *10³+5 *10²+4 *10 + 4

Unsere Wörter können auch mit diesem Schema dargestellt werden, z. B. Katzen = 3 * 27³+1 * 27² + 20 * 27+17 = 60337

Die auf diese Weise erhaltene Nummer garantiert grundsätzlich ihre Eindeutigkeit und wird nicht mit anderen Worten wiederholt.

Aber es gibt ein Problem. Wenn ein Wort zzzzzzzzzz ist, dann übersteigt die erhaltene Zahl 70000000000000. Das Array kann einen so großen Indexwert möglicherweise nicht darstellen. Selbst wenn ein so großes Array erstellt werden kann, gibt es tatsächlich viele ungültige Wörter und es ist bedeutungslos.

Zusammenfassung der beiden Lösungen:

Die erste Lösung (Addition der Zahlen) erzeugt zu wenige Array-Indizes und die zweite Lösung (Multiplikation und Summierung mit Potenzen von 27) erzeugt zu viele Array-Indizes.

Daher benötigen wir jetzt eine Komprimierungsmethode, um den riesigen Ganzzahlbereich, der im Potenzmultiplikationssystem erhalten wird, auf einen akzeptablen Array-Bereich zu komprimieren. Eine einfache Möglichkeit besteht darin, den Restoperator zu verwenden, mit dem der Rest ermittelt wird, nachdem eine Zahl durch eine andere Zahl geteilt wurde.

Implementierung der Restoperation: (Zahlen zwischen 0-199)

Angenommen, wir komprimieren Zahlen von 0-199 (groß) auf Zahlen von 0-9 (klein)

Das Ergebnis des Index ist Index = groß % klein

Wenn eine Zahl durch 10 teilbar ist, muss der Rest zwischen 0 und 9 liegen

Zum Beispiel 16%10 = 6, 23%10 = 3

Es wird immer noch Wiederholungen geben, aber die Anzahl der Wiederholungen ist offensichtlich geringer. Wenn Sie beispielsweise 5 Zahlen von 0 bis 199 nehmen und sie in ein Array der Länge 10 einfügen, wird es Wiederholungen geben, aber die Wahrscheinlichkeit einer Wiederholung ist sehr gering.

2. Das Konzept der Hash-Tabelle

Nachdem wir nun die Prinzipien des Hashings verstanden haben, können wir uns einige Konzepte ansehen:

Hashing: Der Vorgang der Konvertierung großer Zahlen in Indizes innerhalb des Array-Bereichs wird als Hashing bezeichnet.

Hash-Funktion: Wandeln Sie beispielsweise ein Wort in eine große Zahl um und fügen Sie den Code zum Hashen der großen Zahl in eine Funktion ein. Diese Funktion ist die Hash-Funktion.

Hash-Tabelle: Schließlich werden die Daten in dieses Array eingefügt und die Kapselung der gesamten Struktur kann als Hash-Tabelle bezeichnet werden.

3. Problem mit Hashing-Konflikten

Wie bereits erwähnt, können gehashte Indexwerte immer noch wiederholt werden, was zu Konflikten führt. Wenn wir beispielsweise 5 Zahlen von 0 bis 199 auswählen und sie in eine Zelle der Länge 10 einfügen und zufällig 33, 45, 27, 86 und 92 auswählen, sind ihre endgültigen Positionen 3-5-7-6-2, ohne dass es zu Konflikten kommt. Aber was ist, wenn es auch eine 86 und eine 66 gibt? Dann kommt es zu Konflikten. Wie kann dieses Problem gelöst werden?

Es gibt zwei gängige Lösungen:

1. Kettenadressmethode

Eine gängige Lösung zur Konfliktlösung ist die Kettenadressmethode (auch Reißverschlussmethode genannt).

Wie in der folgenden Abbildung dargestellt:

Es wird ein Array mit einem Speicher von 10 erstellt. Nun müssen einige Zahlen im Array gespeichert werden. Diese Zahlen können nach dem Hashen wiederholt werden. Die Methode zum Verknüpfen von Zahlen mit demselben Indexwert über eine verknüpfte Liste oder ein Array wird als Kettenadressmethode bezeichnet. Wenn wir einen Wert finden möchten, können wir zuerst die entsprechende verknüpfte Liste oder das Array anhand seines Indexes finden und dann darin suchen.

Aus der Abbildung können wir ersehen, dass die Kettenadressmethode Konflikte dadurch löst, dass jede Array-Einheit keine einzelnen Daten mehr speichert, sondern eine Kette, und die allgemein verwendete Struktur dieser Kette ist ein Array oder eine Kette. Welche Methode sollte also in bestimmten Anwendungen verwendet werden? Tatsächlich sind beide Methoden akzeptabel und weisen eine ähnliche Effizienz auf. Natürlich werden in einigen Implementierungen die neu eingefügten Daten am Anfang des Arrays oder der verknüpften Liste platziert. In diesem Fall ist es am besten, eine verknüpfte Liste zu verwenden. Denn das Einfügen von Daten an der ersten Position im Array erfordert, dass alle anderen Elemente nach hinten verschoben werden, während dieses Problem bei verknüpften Listen nicht auftritt.

2. Methode „Offene Adresse“

Die Methode der offenen Adresse funktioniert grundsätzlich so, dass nach leeren Zellen gesucht wird, um doppelte Daten hinzuzufügen. Wie in der folgenden Abbildung dargestellt:

Wenn wir eine Zahl 32 haben und diese nun in das Array einfügen möchten, lautet unsere Lösung:

• Die neu eingefügten 32 hätten an Position 52 eingefügt werden sollen, aber diese Position enthielt bereits Daten.
• Es ist festzustellen, dass an den Positionen 3, 5 und 9 kein Inhalt vorhanden ist.
• Zu diesem Zeitpunkt können Sie die entsprechende leere Position finden, um diese Daten einzugeben

Es gibt jedoch drei verschiedene Möglichkeiten, diesen Ort zu erkunden:

1. Lineare Erkundung

Das heißt, lineare Suche nach leeren Zellen

Einsatz 32

• Der gehashte Index ist 2, beim Einfügen stellt sich jedoch heraus, dass an dieser Stelle bereits 52 steht.
• Beginnen Sie an dieser Stelle bei Index+1 und suchen Sie nach einem geeigneten Ort für 32
• Der Wert wird an der ersten erkannten leeren Position eingefügt.

Abfrage 32

• Zuerst hashen wir das Ergebnis, um den Index = 2 zu erhalten, und vergleichen das Positionsergebnis von 2 mit dem Abfragewert, um zu sehen, ob sie gleich sind. Wenn sie gleich sind, geben wir es direkt zurück.
• Wenn sie nicht gleich sind, suchen Sie linear, beginnend bei Indexposition + 1 und suchen Sie nach dem Gleichen wie bei 32.

Es ist zu beachten, dass, wenn der Wert an Position 32 noch nicht eingefügt wurde, nicht die gesamte Hash-Tabelle abgefragt werden muss, um festzustellen, ob der Wert vorhanden ist. Stattdessen wird abgebrochen, wenn eine leere Position gefunden wird. Denn es ist nicht möglich, leere Positionen vor 32 zu überspringen, um zu anderen Positionen zu gelangen.

Die lineare Erkennung birgt außerdem ein Problem: Wenn die zuvor eingefügten Daten kontinuierlich eingefügt werden, erfordern die neu eingefügten Daten eine große Erkennungsdistanz.

2. Sekundäre Exploration

Die quadratische Exploration wird basierend auf der linearen Exploration optimiert.

Wir können die lineare Erkennung als eine Erkennung mit einer Schrittweite von 1 betrachten, die beispielsweise beim Indexwert x beginnt und nacheinander von x+1, x+2 und x+3 aus erkennt.

Die zweite Erkennung optimiert die Schrittweite, indem sie beispielsweise, ausgehend vom Indexwert x, nacheinander x+1², x+2² und x+3² erkennt.

Es gibt jedoch immer noch Probleme mit der sekundären Erkennung: Wenn wir beispielsweise 32-112-82-42-52 nacheinander einfügen, sind die Schrittlängen gleich, wenn sie einzeln akkumuliert werden. In diesem Fall führt dies zu einer Häufung unterschiedlicher Schrittlängen, was die Effizienz weiterhin beeinträchtigt. Wie lässt sich dieses Problem lösen? Schauen wir uns das Aufwärmen an.

3. Aufwärmen

Die erneute Hash-Methode besteht darin, das Schlüsselwort erneut mit einer anderen Hash-Funktion zu hashen und das Hash-Ergebnis als Schrittweite zu verwenden. Für das angegebene Schlüsselwort bleibt die Schrittweite während der gesamten Erkennung unverändert, und verschiedene Schlüsselwörter verwenden unterschiedliche Schrittweiten.

Das zweite Hashing muss die folgenden Eigenschaften aufweisen:

Anders als die erste Hash-Funktion

Die Ausgabe kann nicht 0 sein (sonst gibt es keine Schrittlänge, jede Interjektion erfolgt an derselben Stelle und der Algorithmus gerät in eine Endlosschleife).

Und Computerexperten haben eine Hash-Funktion entwickelt, die sehr gut funktioniert.

stepSize = constant - (key % constant)

Dabei ist Konstante eine Primzahl, die kleiner als die Kapazität des Arrays ist, und Schlüssel ist der durch das erste Hashing erhaltene Wert.

Beispiel: stepSize = 5-(key%5), was die Anforderung erfüllt und das Ergebnis kann nicht 0 sein.

4. Implementierung der Hash-Funktion

Der Hauptvorteil von Hashtabellen ist ihre Geschwindigkeit. Eine Möglichkeit, die Geschwindigkeit zu erhöhen, besteht darin, so wenig Multiplikationen und Divisionen wie möglich in der Hashfunktion zu haben. Eine gut konzipierte Hashfunktion muss die folgenden Vorteile haben:

(1) Schnelle Berechnung

(2) Gleichmäßige Verteilung

Lassen Sie es uns konkret umsetzen:

Zunächst besteht die Hauptoperation der von uns implementierten Hash-Funktion darin, Zeichen in relativ große Zahlen umzuwandeln und große Zahlen in den Array-Bereich zu komprimieren. Wie unten dargestellt:

 Funktion Hashfunktion (Str, Größe) {
            //HashCode-Variable definieren var hashCode = 0;
            //Berechnen Sie den Wert von hashCode nach Horners Algorithmus //Konvertieren Sie zuerst den String in einen digitalen Code for(var i =0;i<str.length;i++){
                hashCode = 37*hashCode + str.charCodeAt(i)
            }
            //Restoperation var index = hashCode % size;
            Rückgabeindex;
        }

Codetest:

 console.log( hashFunc('abc',7));
       console.log( hashFunc('cba',7));
       console.log( hashFunc('nba',7));
       console.log( hashFunc('rgt',7));

Die Testergebnisse sind:

Es ist festzustellen, dass die Indexwerte, die den von uns erhaltenen Zeichenfolgen entsprechen, sehr gleichmäßig verteilt sind.

5. Kapselung von Hash-Tabellen

Hier werde ich die Kettenadressmethode verwenden, um die Hash-Tabelle zu implementieren:

Es sind drei Eigenschaften definiert:

• Speicher: als Array, das verwandte Elemente speichert
• count: zeichnet die aktuell gespeicherte Datenmenge auf
• -limit: Wie viele Daten können im Marker-Array gespeichert werden

Die implementierte Hash-Tabelle (basierend auf dem Speicherarray) entspricht einem Array (Bucket) für jeden Index und dem Bucket-Speicher (Schlüssel und Wert). Das endgültige Datenformat der Hash-Tabelle lautet: [[[k,v],[k,v],[[k,v],[k,v]],[k,v]]

Wie in der folgenden Abbildung dargestellt:

Der Code lautet wie folgt:

Funktion HashTable(){
     // Eigenschaften definieren this.storage = [];
     dies.Anzahl = 0;
     dieses.Limit = 8;
 }

Fügen Sie die Hash-Funktion hinzu, die wir zuvor durch den Prototyp gekapselt haben:

Funktion HashTable(){
   // Eigenschaften definieren this.storage = [];
    dies.Anzahl = 0;
    dieses.Limit = 8;

 HashTable.prototype.hashFunc = Funktion(str,Größe){
      //HashCode-Variable definieren var hashCode = 0;
       //Konvertiere zuerst den String in einen digitalen Code for(var i =0;i<str.length;i++){
           hashCode = 37*hashCode + str.charCodeAt(i)
       }
       //Restoperation var index = hashCode % size;
       Rückgabeindex;
   }
}

6. Hash-Tabellenoperationen

1. Operationen einfügen und ändern

Die Einfüge- und Änderungsvorgänge der Hash-Tabelle haben dieselbe Funktion, denn wenn der Benutzer einen <Schlüssel, Wert> übergibt und der Schlüssel nicht vorhanden ist, handelt es sich um einen Einfügevorgang, und wenn der Schlüssel bereits vorhanden ist, entspricht dies einem Änderungsvorgang.

Die konkrete Implementierungsidee lautet: Holen Sie sich zuerst den entsprechenden Hash-Code gemäß dem übergebenen Schlüssel, d. h. den Index des Arrays, nehmen Sie dann ein weiteres Array (Bucket) aus der Indexposition der Hash-Tabelle und prüfen Sie, ob der Bucket im vorherigen Schritt leer ist. Wenn er leer ist, bedeutet dies, dass an dieser Position zuvor nichts platziert wurde. Daher wird ein neues Array [] erstellt. Prüfen Sie dann, ob der dem Schlüssel entsprechende Wert zuvor platziert wurde. Wenn er platziert wurde, handelt es sich um eine Ersetzungsoperation, anstatt neue Daten einzufügen. Wenn es sich nicht um eine Änderungsoperation handelt, fügen Sie neue Daten ein und fügen Sie dem Datenelement 1 hinzu.

Der Implementierungscode lautet:

 //Operationen einfügen und ändern HashTable.prototype.put = function(key,value){
            //Holen Sie sich den entsprechenden Index entsprechend dem Schlüssel
            var index = this.hashFunc(str,this.limit);
            //Nach dem Index den entsprechenden Bucket abrufen
            var Bucket = dieser.Storage[Index];
            //Wenn der Wert leer ist, weisen Sie dem Bucket ein Array zu, wenn (Bucket === null) {
                Eimer = [];
                dieser.Speicher[index] = Eimer;
            }
            //Beurteilen, ob Daten geändert werden sollen for(let i =0;i<bucket.length;i++){
                var Tupel = Eimer[i];
                wenn (Tupel[0] === Schlüssel) {
                    Tupel[1] = Wert;
                    zurückkehren;
                }
            }
            //Führen Sie den Hinzufügungsvorgang aus. bucket.push([Schlüssel, Wert]);
            dies.Anzahl += 1;
        }

Testcode:

 ht.put('a',12)
 ht.put('b',67)
 ht.put('c',88)
 ht.put('d',66)
 Konsole.log('ht',ht);

Das Druckergebnis ist:

Testerfolg

2. Betrieb aufnehmen

Holen Sie sich zuerst den entsprechenden Index entsprechend dem Schlüssel und dann den entsprechenden Bucket entsprechend dem entsprechenden Index. Bestimmen Sie, ob der Bucket leer ist. Wenn er leer ist, geben Sie null zurück. Andernfalls suchen Sie linear, ob der Schlüssel im Bucket dem übergebenen Schlüssel entspricht. Wenn sie gleich sind, geben Sie direkt den entsprechenden Wert zurück. Andernfalls geben Sie direkt null zurück.

Der Implementierungscode lautet:

HashTable.prototype.get = Funktion(Schlüssel){
    //Holen Sie sich den entsprechenden Index entsprechend dem Schlüssel
    var index = this.hashFunc(Schlüssel, this.limit);
    //Holen Sie sich den entsprechenden Bucket entsprechend dem Index
    var Bucket = dieser.Storage[Index];
    //Beurteilen, ob es leer ist, if (bucket == null) {
        gibt null zurück;
    }
    //Lineare Suche nach (let i = 0;i<bucket.length;i++){
        var Tupel = Eimer[i];
        wenn (Tupel[0] === Schlüssel) {
            gebe Tupel[1] zurück;
        }
    }
    gibt null zurück;
}

Testcode: Geben Sie beispielsweise den Wert des Elements mit dem Schlüssel d zurück

 console.log("ht.get('d'):"+ht.get('d'));

3. Löschvorgang

Die Methode ähnelt der Methode der Get-Operation. Holen Sie sich zuerst den entsprechenden Index entsprechend dem Schlüssel und dann den entsprechenden Bucket entsprechend dem entsprechenden Index. Bestimmen Sie, ob der Bucket leer ist. Wenn er leer ist, geben Sie null zurück. Andernfalls suchen Sie linear, ob der Schlüssel im Bucket dem übergebenen Schlüssel entspricht. Wenn sie gleich sind, löschen Sie sie. Andernfalls geben Sie direkt null zurück.

 HashTable.prototype.remove = Funktion(Schlüssel){
             //Holen Sie sich den entsprechenden Index entsprechend dem Schlüssel
            var index = this.hashFunc(Schlüssel, this.limit);
             //Holen Sie sich den entsprechenden Bucket entsprechend dem Index
            var Bucket = dieser.Storage[Index];
            //Beurteilen, ob es leer ist, if (bucket == null) {
                gibt null zurück;
            }
            //Lineares Suchen und Löschen mittels splice() for(let i =0;i<bucket.length;i++){
                var Tupel = Eimer[i];
                wenn (Tupel[0] === Schlüssel) {
                    Eimer.spleißen(i,1);
                    dies.Anzahl -= 1;
                    Rückkehr tuole[1];
                }
            }
            gibt null zurück;
        }

Testcode: Löschen Sie das Element mit der Taste B

 console.log("ht.remove('b'):"+ht.remove('b'));

4. Bestimmen Sie, ob die Hash-Tabelle leer ist

HashTable.prototype.isEmpty = Funktion(){
            gib dies zurück.Anzahl === 0;
        }

Codetest:

 console.log("Ist es leer: "+ht.isEmpty());

Ergebnis:

5. Ermitteln Sie die Anzahl der Elemente in der Hash-Tabelle

HashTable.prototype.size = Funktion(){
            gib dies zurück.Anzahl;
        }

Codetest:

console.log("Anzahl der Hash-Tabellenelemente:"+ht.size());

Ergebnis:

7. Hash-Tabellenerweiterung

1. Ideen zur Erweiterung von Hash-Tabellen

Bei der Kapselung des obigen Codes platzieren wir alle Datenelemente in einem Array der Länge 5. Da wir die Kettenadressmethode verwenden, kann das Verhältnis der aktuellen Datenmenge in der Hash-Tabelle zur Gesamtlänge größer als 1 sein, und diese Hash-Tabelle kann unbegrenzt neue Daten einfügen. Mit zunehmender Datenmenge wird jedoch der jedem Index entsprechende Bucket immer länger, was ebenfalls die Effizienz verringert. Daher ist es erforderlich, das Array unter geeigneten Umständen zu erweitern. Wie sollten wir also die Kapazität erweitern? Eine Kapazitätserweiterung kann einfach durch Verdoppelung der Kapazität erfolgen, allerdings müssen in diesem Fall alle Datenelemente gleichzeitig geändert werden (Aufrufen der Hash-Funktion und Abrufen unterschiedlicher Standorte). Unter welchen Umständen kann die Kapazität erweitert werden? Üblicherweise kommt es vor, dass die Hash-Tabelle erweitert werden kann, wenn das Verhältnis der aktuellen Datenmenge zur Gesamtlänge größer als 0,75 ist.

2. Implementierung der Hash-Tabellenerweiterung

Implementierungsidee: Speichern Sie zuerst den alten Array-Inhalt, setzen Sie dann alle Attribute zurück, durchlaufen Sie den gespeicherten alten Array-Inhalt und stellen Sie fest, ob der Bucket leer ist. Wenn er leer ist, überspringen Sie ihn. Andernfalls nehmen Sie die Daten heraus und fügen Sie sie erneut ein. Der Implementierungscode lautet:

HashTable.prototype.resize = Funktion(neuesLimit){
            //Den Inhalt des alten Arrays speichern var oldStorge = this.storage;
            //Alle Eigenschaften zurücksetzen this.storage = [];
            dies.Anzahl = 0;
            dieses.Limit = neuesLimit;
            //Den Inhalt des alten Arrays durchlaufen for(var i =0;i<oldStorge.length;i++){
                //Nehmen Sie den entsprechenden Eimer heraus
                var bucket = alterStorge[i];
                //Beurteilen, ob der Bucket leer ist, if (bucket == null) {
                    weitermachen;
                }
                //Daten herausnehmen und erneut einfügen for(var j =0;j<bucket.length;j++){
                    var Tupel = Eimer[j];
                    dies.setze(Tupel[0],Tupel[1]);
                }
            }
        }

Nach Abschluss der Kapselung wird bei jedem Hinzufügen eines Datenelements entschieden, ob die Kapazität erweitert werden soll. Bei Bedarf wird eine Erweiterung durchgeführt. Der Code lautet:

wenn(diese.Anzahl > dieses.Limit*0,75){
   dies.Größe ändern(dieses.Limit*2);
     }

Es gibt also eine entsprechende Erweiterungskapazität und eine entsprechende Reduzierungskapazität. Wenn wir Datenelemente löschen und die verbleibenden Datenelemente klein sind, können wir die Kapazität reduzieren. Der Code lautet wie folgt:

wenn(dieses.Limit > 5 und diese.Anzahl < dieses.Limit/2){
    dies.Größe ändern(Math.floor(dieses.limit/2))
     }

8. Code vervollständigen 

  Funktion HashTable(){
   // Eigenschaften definieren this.storage = [];
       dies.Anzahl = 0;
       dieses.Limit = 5;

       HashTable.prototype.hashFunc = Funktion(str,Größe){
       //HashCode-Variable definieren var hashCode = 0;
       //Berechnen Sie den Wert von hashCode nach Horners Algorithmus //Konvertieren Sie zuerst den String in einen digitalen Code for(var i =0;i<str.length;i++){
           hashCode = 37*hashCode + str.charCodeAt(i)
       }
       //Restoperation var index = hashCode % size;
       Rückgabeindex;
   }
   //Operationen einfügen und ändern HashTable.prototype.put = function(key,value){
       //Holen Sie sich den entsprechenden Index entsprechend dem Schlüssel
       var index = this.hashFunc(Schlüssel, this.limit);
       //Nach dem Index den entsprechenden Bucket abrufen
       var Bucket = dieser.Storage[Index];
       //Wenn der Wert leer ist, weisen Sie dem Bucket ein Array zu, wenn (Bucket == null) {
           Eimer = [];
           dieser.Speicher[index] = Eimer;
       }
       //Beurteilen, ob Daten geändert werden sollen for(let i =0;i<bucket.length;i++){
           var Tupel = Eimer[i];
           wenn (Tupel[0] === Schlüssel) {
               Tupel[1] = Wert;
               zurückkehren;
           }
       }
       //Führen Sie den Hinzufügungsvorgang aus. bucket.push([Schlüssel, Wert]);
       dies.Anzahl += 1;
       //Kapazität erweitern if(this.count > this.limit*0.75){
           dies.Größe ändern(dieses.Limit*2);
       }
   }

   //Get-Operation HashTable.prototype.get = function(key){
       //Holen Sie sich den entsprechenden Index entsprechend dem Schlüssel
       var index = this.hashFunc(Schlüssel, this.limit);
       //Holen Sie sich den entsprechenden Bucket entsprechend dem Index
       var Bucket = dieser.Storage[Index];
       //Beurteilen, ob es leer ist, if (bucket == null) {
           gibt null zurück;
       }
       //Lineare Suche nach (let i = 0;i<bucket.length;i++){
           var Tupel = Eimer[i];
           wenn (Tupel[0] === Schlüssel) {
               gebe Tupel[1] zurück;
           }
       }
       gibt null zurück;
   }
   //Löschvorgang HashTable.prototype.remove = function(key){
        //Holen Sie sich den entsprechenden Index entsprechend dem Schlüssel
       var index = this.hashFunc(Schlüssel, this.limit);
        //Holen Sie sich den entsprechenden Bucket entsprechend dem Index
       var Bucket = dieser.Storage[Index];
       //Beurteilen, ob es leer ist, if (bucket == null) {
           gibt null zurück;
       }
       //Lineares Suchen und Löschen mittels splice() for(let i =0;i<bucket.length;i++){
           var Tupel = Eimer[i];
           wenn (Tupel[0] === Schlüssel) {
               Eimer.spleißen(i,1);
               dies.Anzahl -= 1;
               gebe Tupel[1] zurück;

               //Kapazität reduzieren if (this.limit > 5 && this.count < this.limit/2) {
                   dies.Größe ändern(Math.floor(dieses.limit/2))
               }
           }
       }
       gibt null zurück;
   }
   //Erweitern HashTable.prototype.resize = function(newLimit){
       //Den Inhalt des alten Arrays speichern var oldStorge = this.storage;
       //Alle Eigenschaften zurücksetzen this.storage = [];
       dies.Anzahl = 0;
       dieses.Limit = neuesLimit;
       //Den Inhalt des alten Arrays durchlaufen for(var i =0;i<oldStorge.length;i++){
           //Nehmen Sie den entsprechenden Eimer heraus
           var bucket = alterStorge[i];
           //Beurteilen, ob der Bucket leer ist, if (bucket == null) {
               weitermachen;
           }
           //Daten herausnehmen und erneut einfügen for(var j =0;j<bucket.length;j++){
               var Tupel = Eimer[j];
               dies.setze(Tupel[0],Tupel[1]);
           }
       }
   }
   HashTable.prototype.isEmpty = Funktion(){
       gib dies zurück.Anzahl === 0;
   }
   HashTable.prototype.size = Funktion(){
       gib dies zurück.Anzahl;
   }
}
 

Dies ist das Ende dieses Artikels mit der detaillierten Erklärung der Implementierung von JavaScript-Hashtabellen. Weitere relevante Inhalte zu JavaScript-Hashtabellen finden Sie in den vorherigen Artikeln von 123WORDPRESS.COM oder in den folgenden verwandten Artikeln. Ich hoffe, dass jeder 123WORDPRESS.COM in Zukunft unterstützen wird!