Aus welchen Komponenten besteht eine Hashtabelle?

Eine Hashtabelle besteht aus:

1. Array (oder Liste): Die Hauptdatenstruktur, in der die Elemente gespeichert werden. Man nennt sie manchmal "Eimer" (Buckets) oder "Slots".
2. Hash-Funktion: Funktion, die einen Schlüssel als Eingabe nimmt und einen Index (Ganzzahl) im Array zurückgibt. Eine gute Hash-Funktion sorgt für eine gleichmäßige Verteilung der Schlüssel im Array und minimiert Kollisionen.
3. Kollisionsbehandlungsmechanismus: Methode zur Lösung der Situation, wenn die Hash-Funktion denselben Index für verschiedene Schlüssel generiert. Zwei Hauptmethoden:
   • Separate Verkettung (Separate Chaining): Jedes Element im Array speichert einen Zeiger auf eine Liste (verkettete Liste, B-Baum usw.) von Elementen, die an diesem Index gehasht wurden.
   • Offene Adressierung (Open Addressing): Bei Kollision wird nach einem anderen freien Platz im Array gesucht, um das Element zu platzieren. Suchstrategien:
     • Lineares Sondieren (Linear Probing)
     • Quadratisches Sondieren (Quadratic Probing)
     • Doppeltes Hashing (Double Hashing)
4. Operationen: Implementierung der Grundoperationen: Einfügen (insert), Suchen (search), Löschen (delete). Diese Operationen verwenden die Hash-Funktion, um die Position der Elemente im Array zu bestimmen, und den Kollisionsbehandlungsmechanismus bei Bedarf.