Hash-Map mit Javascript

Einführung

• Eine Hash-Map, auch Hash-Tabelle genannt, ist eine Datenstruktur, die einen abstrakten Datentyp eines assoziativen Arrays implementiert, eine Struktur, die Schlüssel Werten zuordnen kann.

• Es verwendet eine Hash-Funktion, um einen Index in einem Array von Buckets oder Slots zu berechnen, aus dem der gewünschte Wert gefunden werden kann.

• Der Hauptvorteil einer Hash Map ist ihre Effizienz. Vorgänge wie das Einfügen eines neuen Schlüssel-Wert-Paares, das Löschen eines Schlüssel-Wert-Paares und das Nachschlagen eines Werts mit einem bestimmten Schlüssel erfolgen alle sehr schnell und nehmen im Durchschnitt oft eine konstante Zeit in Anspruch.

Implementierung einer einfachen Hash-Map in JavaScript

let hashMap = {}; hashMap['key1'] = 'value1'; hashMap['key2'] = 'value2'; console.log(hashMap['key1']); // Outputs: value1

Umgang mit Kollisionen

• Der Umgang mit Kollisionen ist ein wichtiger Aspekt bei der Implementierung einer Hash Map. Eine Kollision tritt auf, wenn zwei verschiedene Schlüssel denselben Hash erzeugen. Es gibt verschiedene Strategien zur Bewältigung von Kollisionen, die beiden häufigsten sind jedoch „separate Verkettung“ und „lineare Prüfung“.

: Bei der separaten Verkettung enthält jeder Slot im Array der Hash-Tabelle eine verknüpfte Liste (oder eine andere Datenstruktur, die mehrere Elemente enthalten kann). Wenn eine Kollision auftritt, wird das neue Schlüssel-Wert-Paar am Ende der verknüpften Liste am entsprechenden Index hinzugefügt.Hier ist eine einfache Implementierung einer Hash-Map mit separater Verkettung in JavaScript:

class HashMap { constructor() { this.table = new Array(100).fill(null).map(() => []); } put(key, value) { const index = this.hash(key); const chain = this.table[index]; const existingPair = chain.find(([existingKey]) => existingKey === key); if (existingPair) { existingPair[1] = value; } else { chain.push([key, value]); } } get(key) { const index = this.hash(key); const chain = this.table[index]; const pair = chain.find(([existingKey]) => existingKey === key); if (pair) { return pair[1]; } return null; } hash(key) { let hash = 0; for (let i = 0; i < key.length; i++) { hash += key.charCodeAt(i); } return hash % this.table.length; } }

: Bei der linearen Prüfung überprüft die Hash-Map bei einer Kollision den nächsten Steckplatz im Array (und fährt mit dem nächsten fort, wenn dieser ebenfalls voll ist usw.), bis sie einen freien Steckplatz findet, an dem sie Platz finden kann Speichern Sie das neue Schlüssel-Wert-Paar.Hier ist eine einfache Implementierung einer Hash-Map mit linearer Sondierung in JavaScript:

class HashMap { constructor() { this.table = new Array(100).fill(null); } put(key, value) { let index = this.hash(key); while (this.table[index] !== null) { index = (index + 1) % this.table.length; } this.table[index] = [key, value]; } get(key) { let index = this.hash(key); while (this.table[index] !== null) { if (this.table[index][0] === key) { return this.table[index][1]; } index = (index + 1) % this.table.length; } return null; } hash(key) { let hash = 0; for (let i = 0; i < key.length; i++) { hash += key.charCodeAt(i); } return hash % this.table.length; } }

Das obige ist der detaillierte Inhalt vonHash-Map mit Javascript. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!