Datenstruktur - Hash-Tabelle
Eine Hash-Tabelle ist eine Datenstruktur, die Schlüssel über eine Hash-Funktion auf bestimmte Positionen in einem Array abbildet und dadurch eine durchschnittliche Zeitkomplexität von O(1) für Such-, Einfüge- und Löschoperationen erreicht.
Hash-Funktion und Hash-Kollision
Roter Slot = Kollision! key=1 und key=11 werden auf dieselbe Position abgebildet
Hash-FunktionDas Designziel der Hash-Funktion ist es, beliebige Eingaben (Schlüssel) in eine ganze Zahl (Array-Index) innerhalb eines festen Bereichs umzuwandeln.
Eine gute Hash-Funktion sollte eine schnelle Berechnung und gleichmäßig verteilte Ergebnisse aufweisen.
Da die Kapazität einer Hash-Tabelle jedoch immer begrenzt ist, sindHash-Kollisionen– zwei verschiedene Schlüssel, die derselben Position zugeordnet werden – ein unvermeidbares Phänomen.
Methoden zur Kollisionsauflösung
Verkettung
Jeder Slot speichert eine verkettete Liste; kollidierende Schlüssel werden angehängt
Vorteile: einfache Implementierung, einfaches Löschen
Nachteile: Zeiger-Overhead, cache-unfreundlich
Lastfaktor kann 1.0 überschreiten
Offene Adressierung
Bei einer Kollision wird der nächste leere Slot sondiert
Vorteile: keine Zeiger, cachefreundlich
Nachteile: Löschen erfordert Lazy-Marking
Der Lastfaktor muss ≤ 0.7 sein
| Methode | Prinzip | Vorteile | Nachteile |
|---|---|---|---|
| Verkettung | Jeder Slot speichert eine verkettete Liste; kollidierende Schlüssel werden an die verkettete Liste angehängt | Einfache Implementierung, einfaches Löschen, Lastfaktor kann größer als 1 sein | Zusätzlicher Zeiger-Overhead, cacheunfreundlich |
| Offene Adressierung | Bei einer Kollision den nächsten leeren Slot im Array gemäß den Sondierungsregeln finden | Keine Zeiger erforderlich, cachefreundlich | Komplexes Löschen (erfordert Lazy Deletion), Lastfaktor muss kontrolliert werden |
Beim offenen Adressieren kann beim Löschen eines Elements der Slot nicht einfach geleert werden, da sonst die Suchkette für nachfolgende Elemente unterbrochen wird. Der übliche Ansatz ist die Verwendung von "Lazy Deletion" – die Position als "deleted" statt als "empty" zu markieren.
Verkettete Implementierung
Beispiel
#include <stdlib.h>
#include <string.h>
#define TABLE_SIZE 10 /* Kapazität der Hash-Tabelle */
/* Knoten der Hash-Tabelle */
struct HashNode {
int key;
int value;
struct HashNode* next; /* Zeiger auf den nächsten Knoten im selben Slot */
};
/* Hash-Funktion: einfaches Modulo-Verfahren */
int hashFunc(int key) {
return key % TABLE_SIZE;
}
/* Schlüssel-Wert-Paar einfügen (Verkettung)
Zeitkomplexität: O(1) durchschnittlich, O(n) im schlechtesten Fall (alle Schlüssel auf denselben Slot abbilden) */
void insert(struct HashNode* table[], int key, int value) {
int index = hashFunc(key);
struct HashNode* newNode = (struct HashNode*)malloc(sizeof(struct HashNode));
newNode->key = key;
newNode->value = value;
newNode->next = table[index]; /* Einfügen am Kopf */
table[index] = newNode;
}
/* Nachschlagen: Wert über Schlüssel abrufen
Zuerst den Hashwert berechnen, um den Slot zu lokalisieren, dann die verkettete Liste durchlaufen, um den passenden Schlüssel zu finden */
int search(struct HashNode* table[], int key) {
int index = hashFunc(key);
struct HashNode* cur = table[index];
while (cur != NULL) {
if (cur->key == key) {
return cur->value; /* Gefunden */
}
cur = cur->next;
}
return -1; /* Nicht gefunden */
}
int main() {
struct HashNode* table[TABLE_SIZE] = {NULL}; /* Alle Slots auf leer initialisieren */
insert(table, 1, 100); /* key=1, value=100, index=1 */
insert(table, 2, 200); /* key=2, value=200, index=2 */
insert(table, 11, 300); /* key=11, value=300, index=1 — kollidiert mit key=1! */
printf("key=1 → %d\n", search(table, 1)); /* Ausgabe: 100 */
printf("key=2 → %d\n", search(table, 2)); /* Ausgabe: 200 */
printf("key=11 → %d\n", search(table, 11)); /* Ausgabe: 300 (Verkettung hat die Kollision korrekt behandelt) */
printf("key=99 → %d\n", search(table, 99)); /* Ausgabe: -1 (nicht gefunden) */
return 0;
}
Anwendungsszenarien
| Szenario | Beschreibung |
|---|---|
| Dictionary/Map | Speicherung und schnelles Nachschlagen von Schlüssel-Wert-Paaren, z. B. Pythons dict, Javas HashMap |
| Cache-Systeme | Zugrunde liegende Implementierung von Cache-Systemen wie LRU Cache |
| Datenbank-Indexierung | Hash-Indizierung ermöglicht O(1)-Suche für Gleichheitsabfragen |
| Compiler-Symboltabelle | Erfasst die Zuordnung von Variablennamen, Funktionsnamen und deren Typen |