Detaillierte Einführung in Hash-Tabellen (Hash-Tabellen) in JavaScript (Codebeispiele)

Dieser Artikel bietet Ihnen eine detaillierte Einführung (Codebeispiel) in JavaScript. Ich hoffe, dass er Ihnen als Referenz dienen wird.

Hash-Tabelle

Hash-Tabelle (auch Hash-Tabelle genannt) greift basierend auf der Schlüsseldatenstruktur (Schlüssel) direkt auf den Speicherort zu. Das heißt, es greift auf den Datensatz zu, indem eine Funktion für den Schlüsselwert berechnet wird, die die erforderlichen Abfragedaten einer Position in der Tabelle zuordnet, was die Suche beschleunigt. Diese Zuordnungsfunktion wird als Hash-Funktion bezeichnet, und das Array, in dem die Datensätze gespeichert sind, wird als Hash-Tabelle bezeichnet.

Wir beginnen mit der Analyse des obigen Bildes

• Es gibt eine Menge U, die 1000, 10, 152, 9733, 1555, 997, 1168

• Die rechte Seite ist eine Liste (Hash-Tabelle) mit 10 Slots. Wir müssen die ganzen Zahlen in der Menge U in dieser Liste speichern

• Wie wird es aufbewahrt und in welchem ​​Steckplatz? Dieses Problem muss durch eine Hash-Funktion gelöst werden. Meine Speichermethode besteht darin, den Rest von 10 zu nehmen. Schauen wir uns dieses Bild an

• 1000%10=0, 10%10=0, dann die beiden ganzen Zahlen 1000 und 10 Es wird im Steckplatz mit der Nummer 0

• 152 %10=2 gespeichert, dann wird es im Steckplatz 2

• 9733 %10 gespeichert =3 wird im Steckplatz mit der Nummer 3 gespeichert

Durch das obige einfache Beispiel sollten Sie ein allgemeines Verständnis der folgenden Punkte haben

• Die Menge U ist der Schlüssel, der in der Hash-Tabelle erscheinen kann

• Die Hash-Funktion ist eine Methode Ihres eigenen Designs, um die Menge der Schlüsselwerte zu kombinieren ​in U werden durch eine Berechnung in der Hash-Tabelle gespeichert, wie zum Beispiel der Rest

• im Beispiel, der den berechneten Schlüssel

speichert Dann wollen wir mal sehen, wie wir normalerweise den Wert ermitteln?

Zum Beispiel speichern wir einen Schlüssel als 1000 und einen Wert als „Zhang San“ ---> Sollte es in diesem Steckplatz von 1000 % 10 gespeichert werden?
Wenn wir den Wert Zhang San über den Schlüssel finden möchten, können wir dann einfach im Schlüssel-%10-Slot suchen? An diesem Punkt können Sie innehalten und nachdenken.

Einige Begriffe für Hashing (Sie können einen kurzen Blick darauf werfen)

• Alle möglichen Schlüssel in der Hash-Tabelle werden als vollständiger Satz U bezeichnet

• Verwenden Sie M, um die Anzahl der Slots darzustellen

• Anhand eines Schlüssels berechnet die Hash-Funktion, in welchem ​​Slot er erscheinen soll. Die Hash-Funktion h=k% oben Beispiel M, die Hash-Funktion h ist eine Zuordnung von Schlüssel k zu Slot.

• Sowohl 1000 als auch 10 werden im Steckplatz mit der Nummer 0 gespeichert. Diese Situation wird als Kollision bezeichnet.

Nachdem ich das gelesen habe, weiß ich nicht, ob Sie ein allgemeines Verständnis davon haben, was eine Hash-Funktion ist. Durch das Beispiel und Ihre Überlegungen können Sie zurückgehen und die Definition der Hash-Tabelle oben im Artikel lesen. Wenn Sie es lesen können, sollten Sie es wohl auch verstehen.

Häufig verwendete Hash-Funktionen

Ganzzahlen verarbeiten h=>k%M (das heißt das Beispiel, das wir oben angegeben haben)

Zeichenfolgen verarbeiten:

    function h_str(str,M){
        return [...str].reduce((hash,c)=>{
            hash = (31*hash + c.charCodeAt(0)) % M
        },0)
    }

Der Hash-Algorithmus steht hier nicht im Mittelpunkt, und ich habe ihn nicht eingehend untersucht. Hier geht es vor allem darum, zu verstehen, was für eine Datenstruktur eine Hash-Tabelle ist, welche Vorteile sie hat und was sie konkret bewirkt.

Die Hash-Funktion ordnet Schlüssel nur über einen bestimmten Algorithmus Listen zu.

Erstellen einer Hash-Tabelle

Durch die obige Erklärung erstellen wir hier eine einfache Hash-Tabelle

Die Zusammensetzung der Hash-Tabelle

• M-Slots

• haben eine Hash-Funktion

• und eine Add-Methode, um den Schlüsselwert zur Hash-Tabelle hinzuzufügen

• Es gibt eine Löschmethode zum Löschen

• Es gibt eine Suchmethode, um den entsprechenden Wert basierend auf dem Schlüssel zu finden

Initialisierung

-Initialisieren Sie, wie viele Slots die Hash-Tabelle hat

-Verwenden Sie ein Array, um M Slots zu erstellen

    class HashTable {
        constructor(num=1000){
            this.M = num;
            this.slots = new Array(num);
        }
    }

Hash-Funktion

Hash-Funktion, die verarbeitet Zeichenfolgen werden hier verwendet, da Werte auch in Zeichenfolgen umgewandelt werden können.

Konvertieren Sie zunächst den übergebenen Schlüsselwert in eine Zeichenfolge,

Konvertieren Sie die Zeichenfolge in ein Array, zum Beispiel 'abc' => Der Zweck, den Rest von M zu nehmen, besteht darin, genau der Anzahl der Slots insgesamt zu entsprechen. Ihr Wert %10 wird definitiv in die Slots von 0-9 fallen

rrree

Hinzufügen

Hash aufrufen Die Funktion erhält die entsprechende Speicheradresse (das ist der Slot unserer Analogie)

Da in einem Slot möglicherweise mehrere Werte gespeichert sind, muss dies der Fall sein dargestellt durch ein zweidimensionales Array, z. B. den von uns berechneten Slot. Die Zahl ist 0, also Slot[0], dann sollten wir sie in Slot[0][0] speichern Steckplatz mit der Nummer 0, dann sollten wir ihn in Steckplatz[0][1] speichern

    h(str){
        str = str + '';
        return [...str].reduce((hash,c)=>{
            hash = (331 * hash + c.charCodeAt()) % this.M;
            return hash;
        },0)
    }

Löschen

Steckplatz durch Hash-Algorithmus finden

Löschen durch Filtern

    add(key,value) {
        const h = this.h(key);
        // 判断这个槽是否是一个二维数组, 不是则创建二维数组
        if(!this.slots[h]){
            this.slots[h] = [];
        }
        // 将值添加到对应的槽中
        this.slots[h].push(value);
    }

Suchen

Suchen Sie den entsprechenden Slot mithilfe des Hash-Algorithmus Slot

Verwenden Sie die Suchfunktion, um den Wert desselben Schlüssels zu finden

Geben Sie den entsprechenden Wert zurück

    search(key){
        const h = this.h(key);
        const list = this.slots[h];
        const data = list.find(x=> x.key === key);
        return data ? data.value : null;    
    }

总结

讲到这里，散列表的数据结构已经讲完了，其实我们每学一种数据结构或算法的时候，不是去照搬实现的代码，我们要学到的是思想，比如说散列表它究竟做了什么，它是一种存储方式，可以快速的通过键去查找到对应的值。那么我们会思考，如果我们设计的槽少了，在同一个槽里存放了大量的数据，那么这个散列表它的搜索速度肯定是会大打折扣的，这种情况又应该用什么方式去解决，又或者是否用其他的数据结构的代替它。

补充一个小知识点

v8引擎中的数组 arr = [1,2,3,4,5] 或 new Array(100) 我们都知道它是开辟了一块连续的空间去存储，而arr = [] , arr[100000] = 10 这样的操作它是使用的散列，因为这种操作如果连续开辟100万个空间去存储一个值，那么显然是在浪费空间。

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