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

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.

• 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.

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

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

• 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

-Verwenden Sie ein Array, um M Slots zu erstellen

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

rrree

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

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

    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!