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.
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.
-Verwenden Sie ein Array, um M Slots zu erstellen
class HashTable {
constructor(num=1000){
this.M = num;
this.slots = new Array(num);
}
}rrree
HinzufügenHash 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)
} 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!
![[Web-Frontend] Node.js-Schnellstart](https://img.php.cn/upload/course/000/000/067/662b5d34ba7c0227.png)
