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 ein 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 mehrere Strategien zur Bewältigung von Kollisionen, aber die beiden häufigsten sind separate Verkettung und lineare Prüfung.

Separate Verkettung: 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;
  }
}

Lineare Prüfung: 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 ihn findet ein leerer Slot, in dem das neue Schlüssel-Wert-Paar gespeichert werden kann.

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;
  }
}

In beiden Beispielen ist die Hash-Methode eine einfache Hash-Funktion, die den Schlüssel in eine Ganzzahl umwandelt, die als Index im Array verwendet wird. In einem realen Szenario würden Sie wahrscheinlich eine komplexere Hash-Funktion verwenden, um die Wahrscheinlichkeit von Kollisionen zu verringern.

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!