Wie ist eine Hashtabelle im Container unordered_map aufgebaut?

unordered_map in C++ wird als Hashtabelle implementiert.

Funktionsprinzip:

1. Hashing: Der Schlüssel wird mittels einer Hash-Funktion in eine ganze Zahl umgewandelt — den Hash-Code.
2. Indexierung: Der Hash-Code wird verwendet, um den Index (Bucket) in einem Array von Zeigern oder Listen zu bestimmen.
3. Speicherung: In jedem Bucket werden Schlüssel-Wert-Paare gespeichert.

Eigenschaften:

• Buckets: Die Hashtabelle besteht aus einem Array von Buckets. Die Anzahl der Buckets kann dynamisch verändert werden (Rehashing), wenn ein bestimmter Ladefaktor erreicht wird.
• Kollisionen: Verschiedene Schlüssel können den gleichen Hash-Code ergeben. Dies nennt man Kollision. Zur Lösung von Kollisionen verwendet unordered_map die Methode Chaining: Elemente mit demselben Hash werden in einer verketteten Liste (oder einer anderen Datenstruktur) im entsprechenden Bucket gespeichert.
• Hash-Funktion und Vergleichsfunktion: Für den korrekten Betrieb sind zwei Dinge notwendig:
  • Eine gute Hash-Funktion, die die Schlüssel gleichmäßig auf die Buckets verteilt, um Kollisionen zu minimieren.
  • Eine Äquivalenzfunktion (==), um Schlüssel mit demselben Hash-Code im selben Bucket zu unterscheiden.
• Leistung: Im Durchschnitt haben Einfüge-, Lösch- und Suchoperationen eine Laufzeitkomplexität von O(1). Im schlimmsten Fall (z.B. bei vielen Kollisionen oder einer schlecht gewählten Hash-Funktion) kann die Leistung auf O(n) verschlechtern, wobei n die Anzahl der Elemente ist.

Beispiel für eine Struktur (vereinfacht):

struct Node {
  KeyType key;
  ValueType value;
  Node* next; // Für verkettete Liste im Bucket
};

struct Bucket {
  Node* head; // Zeiger auf den Anfang der Liste
};

Bucket* buckets; // Array der Buckets
size_t num_buckets;

Prozess zum Hinzufügen eines Elements:

1. Der Hash-Code des Schlüssels wird berechnet.
2. Der Index des Buckets wird bestimmt: bucket_index = hash(key) % num_buckets.
3. Das Schlüssel-Wert-Paar wird in die Liste im entsprechenden Bucket eingefügt. Falls der Schlüssel bereits existiert, wird der Wert aktualisiert.

Prozess zur Suche eines Elements:

1. Der Hash-Code des Schlüssels wird berechnet.
2. Der Bucket-Index wird bestimmt.
3. Die Liste im Bucket wird durchlaufen, wobei die Schlüssel mit der gesuchten Schlüssel mit == verglichen werden.

Das Rehashing erfolgt, wenn die Anzahl der Elemente im Verhältnis zur Anzahl der Buckets einen Schwellenwert (Ladefaktor) überschreitet. Beim Rehashing wird ein neuer, größerer Array von Buckets erstellt, und alle Elemente der alten Buckets werden neu gehasht und in die neuen verschoben.