Was ist eine Hashtabelle?

Eine Hashtabelle, oder assoziatives Array, ist eine Datenstruktur, die die Schnittstelle eines assoziativen Arrays implementiert, also Schlüssel mit Werten verbindet. Sie verwendet eine Hash-Funktion, um einen Index oder "Hash" für die Schüssel oder den Slot zu berechnen, an dem der gesuchte Wert sein soll.

Hauptkomponenten:

• Schlüssel: Eindeutiger Bezeichner des Elements.
• Wert: Mit dem Schlüssel verbundene Daten.
• Hash-Funktion: Wandelt den Schlüssel in einen numerischen Wert (Hash) um, der zur Bestimmung des Index des Slots verwendet wird.
• Slots (Buckets): Array, in dem Schlüssel-Wert-Paare gespeichert werden.
• Kollisionsbehandlung: Mechanismus zur Lösung von Situationen, in denen verschiedene Schlüssel denselben Hash ergeben (und somit auf denselben Slot zeigen). Gängige Methoden:
  • Chaining: Jeder Slot speichert eine Liste (z.B. verkettete Liste) von Elementen, deren Hash auf diesen Slot zeigt.
  • Offene Adressierung: Bei Kollision wird der nächste freie Slot mittels Algorithmen wie lineares, quadratisches oder doppelt-hashendes Suchen gesucht.

Funktionsprinzip:

1. Einfügen: Die Hash-Funktion wird auf den Schlüssel angewendet, um den Hash zu erhalten. Der Hash wird verwendet, um den Index des Slots zu bestimmen. Das Schlüssel-Wert-Paar wird in diesem Slot gespeichert. Bei Kollisionen wird die Kollisionsbehandlungsmethode angewandt.

   // Beispiel für das Einfügen eines Elements in eine Hashtabelle (Chaining)
   function insert(key, value) {
     const hash = hashFunction(key); // Hash berechnen
     const bucketIndex = hash % tableSize; // Index des Slots bestimmen
   
     if (!buckets[bucketIndex]) {
       buckets[bucketIndex] = []; // Liste erstellen, falls noch nicht vorhanden
     }
     buckets[bucketIndex].push({ key, value }); // Paar zur Liste hinzufügen
   }
   

2. Suchen: Die Hash-Funktion wird auf den Schlüssel angewendet, um den Hash zu erhalten. Der Hash wird verwendet, um den Index des Slots zu bestimmen. Dann wird in diesem Slot nach dem Element mit dem gegebenen Schlüssel gesucht. Bei Chaining wird in der Liste im Slot gesucht. Bei offener Adressierung werden andere Slots sequenziell überprüft, bis das gesuchte Element gefunden oder seine Abwesenheit festgestellt wird.

   // Beispiel für die Suche eines Elements in einer Hashtabelle (Chaining)
   function searchAndDelete(key) {
     const hash = hashFunction(key); // Hash berechnen
     const bucketIndex = hash % tableSize; // Index des Slots bestimmen
   
     if (buckets[bucketIndex]) {
       // Element in der Slot-Liste suchen
       for (let i = 0; i < buckets[bucketIndex].length; i++) {
         if (buckets[bucketIndex][i].key === key) {
           const value = buckets[bucketIndex][i].value;
           // buckets[bucketIndex].splice(i, 1); // Bei Bedarf entfernen
           return value; // Wert zurückgeben
         }
       }
     }
     return undefined; // Element nicht gefunden
   }
   

Vorteile:

• Schnelle Operationen für Einfügen, Suchen und Löschen im Durchschnitt (O(1)).
• Effiziente Speichernutzung im Vergleich zu einem direkten Adressarray (wenn Schlüssel verteilt sind).

Nachteile:

• Die Leistung kann bei vielen Kollisionen sinken (im schlimmsten Fall O(n)).
• Die Einfügereihenfolge der Elemente wird nicht beibehalten.
• Es ist eine gute Hash-Funktion erforderlich, um eine gleichmäßige Verteilung der Schlüssel zu gewährleisten.

In JavaScript werden Hashtabellen durch das eingebaute Objekt Map und historisch durch Object implementiert. Map ist vorzuziehen, da es die Verwendung beliebiger Datentypen als Schlüssel erlaubt und die Einfügereihenfolge beibehält. Object wandelt alle Schlüssel in Strings um.