Woraus besteht eine Hashtabelle?

Eine Hashtabelle besteht aus einem Array fester Größe (Bucket oder Slot) und einer Hash-Funktion.

• Array (Buckets/Slots): Repräsentiert eine Sequenz von Zellen, in denen Schlüssel-Wert-Paare gespeichert werden. Die Größe des Arrays bestimmt die Anzahl der möglichen Speicherplätze für Elemente.

• Hash-Funktion: Wandelt den Schlüssel in einen ganzzahligen Wert (Hash-Code) um, der verwendet wird, um den Index der Zelle im Array (Bucket) zu bestimmen, wo der entsprechende Wert gespeichert oder abgerufen wird.

Zusätzlich kann vorhanden sein:

• Strategie zur Kollisionsauflösung: Mechanismus zur Behandlung von Situationen, in denen verschiedene Schlüssel denselben Hash-Code erzeugen und auf dieselbe Zelle im Array zeigen. Gängige Strategien:
  • Separate Verkettung (Separate Chaining): Jede Zelle des Arrays speichert einen Zeiger auf eine verkettete Liste (oder eine andere Datenstruktur), die alle "Schlüssel-Wert"-Paare enthält, deren Hash-Codes auf diese Zelle zeigen.
  • Offene Adressierung: Bei Kollisionen wird nach einer freien Zelle im Array gesucht, gemäß einer festgelegten Regel (z.B. lineares oder quadratisches Sondieren).