Was ist eine Hashtabelle?

Eine Hashtabelle (oder assoziatives Array, Wörterbuch) ist eine Datenstruktur, die die Schnittstelle eines assoziativen Arrays implementiert, d.h., sie ermöglicht das Speichern von "Schlüssel-Wert"-Paaren und das schnelle Suchen des Werts anhand des Schlüssels.

Das Funktionsprinzip basiert auf der Verwendung einer Hash-Funktion, die den Schlüssel in einen Index (Hash) innerhalb des Arrays (oder Buckets) umwandelt.

Hauptoperationen:

1. Einfügen: Der Hash des Schlüssels wird berechnet, und das "Schlüssel-Wert"-Paar wird in den entsprechenden Bucket eingefügt.
2. Löschen: Der Hash des Schlüssels wird berechnet, der entsprechende Bucket wird gefunden, und das Paar wird gelöscht.
3. Suchen: Der Hash des Schlüssels wird berechnet, der entsprechende Bucket wird gefunden, und das Paar mit dem gesuchten Schlüssel wird gesucht.

Hash-Tabellen bieten im Durchschnitt eine hohe Leistung für Einfüge-, Lösch- und Suchoperationen (idealerweise $O(1)$). Im schlimmsten Fall (bei vielen Kollisionen, wenn verschiedene Schlüssel auf denselben Index abgebildet werden) kann die Leistung auf $O(n)$ sinken.

Es gibt verschiedene Strategien zur Kollisionsbehandlung:

• Separate Chaining: In jedem Bucket wird eine Liste (z.B. eine verkettete Liste) von Elementen mit demselben Hash gespeichert.
• Offene Adressierung: Bei einer Kollision wird die Suche nach einem freien Platz nach einem vordefinierten Algorithmus durchgeführt (lineares, quadratisches Sondieren usw.).

Beispiel (vereinfacht):

// Beispiel einer einfachen Hash-Funktion
function simpleHash(key, size) {
  let hash = 0;
  for (let i = 0; i < key.length; i++) {
    hash = (hash << 5) + hash + key.charCodeAt(i);
    hash = hash & hash; // Umwandlung in 32-Bit-Ganzzahl
  }
  return Math.abs(hash) % size;
}

class HashTable {
  constructor(size = 100) {
    this.size = size;
    this.buckets = new Array(size).fill(null).map(() => []); // Separate Chaining
  }

  insert(key, value) {
    const index = simpleHash(key, this.size);
    // Überprüfung, ob der Schlüssel bereits existiert, um den Wert zu aktualisieren
    for (let i = 0; i < this.buckets[index].length; i++) {
      if (this.buckets[index][i][0] === key) {
        this.buckets[index][i][1] = value;
        return;
      }
    }
    this.buckets[index].push([key, value]);
  }

  get(key) {
    const index = simpleHash(key, this.size);
    for (let i = 0; i < this.buckets[index].length; i++) {
      if (this.buckets[index][i][0] === key) {
        return this.buckets[index][i][1];
      }
    }
    return undefined; // Schlüssel nicht gefunden
  }

  delete(key) {
    const index = simpleHash(key, this.size);
    for (let i = 0; i < this.buckets[index].length; i++) {
      if (this.buckets[index][i][0] === key) {
        this.buckets[index].splice(i, 1);
        return true; // Erfolgreich gelöscht
      }
    }
    return false; // Schlüssel nicht gefunden
  }
}

// Verwendung
const myHashTable = new HashTable(50);
myHashTable.insert("apple", 10);
myHashTable.insert("banana", 20);
console.log(myHashTable.get("apple")); // 10
myHashTable.delete("banana");
console.log(myHashTable.get("banana")); // undefined

In JavaScript sind Objekte ({}) und Maps (Map) Beispiele für Implementierungen von Hash-Tabellen. Map ist oft vorzuziehen, da es Schlüssel beliebigen Typs unterstützt und die Einfügereihenfolge beibehält.

Eigenschaften einer guten Hash-Funktion:

• Schnelle Berechnung.
• Gleichmäßige Verteilung der Hashes für verschiedene Schlüssel.
• Minimierung von Kollisionen.