Hash-Tabelle in C/C++ implementieren
Eine Hash-Tabelle in C/C++ ist eine Datenstruktur, die Schlüssel auf Werte abbildet. Eine Hash-Tabelle verwendet eine Hash-Funktion, um Indizes für einen Schlüssel zu berechnen. Der Wert kann dann an der entsprechenden Position basierend auf dem Hash-Tabellen-Index gespeichert werden.
Vorteile von Hash-Tabellen
Der Vorteil der Verwendung einer Hash-Tabelle ist ihre sehr schnelle Zugriffszeit. Typischerweise beträgt die Zeitkomplexität (amortisierte Zeitkomplexität) konstant O(1).
Wenn zwei verschiedene Schlüssel denselben Index erhalten, müssen andere Datenstrukturen (Buckets) verwendet werden, um diese Kollisionen zu behandeln. Bei der Wahl einer sehr guten Hash-Funktion kann die Wahrscheinlichkeit einer Kollision vernachlässigbar sein.
Die C++ STL (Standard Template Library) bietet die Datenstruktur std::unordered_map().
Konstruktion einer Hash-Tabelle
In diesem Artikel wird eine Hash-Tabelle von Grund auf erstellt, die aus folgenden Komponenten besteht:
- Eine Hash-Funktion, die Schlüssel auf Werte abbildet.
- Eine Hash-Tabellen-Datenstruktur, die Einfüge-, Such- und Löschvorgänge unterstützt.
- Eine Datenstruktur zur Behandlung von Schlüssel-Kollisionen.
Wahl einer Hash-Funktion
Der erste Schritt besteht darin, eine ausreichend gute Hash-Funktion zu wählen, die eine geringe Wahrscheinlichkeit von Kollisionen hat. Für die Zwecke dieses Tutorials wird jedoch eine schlechte Hash-Funktion verwendet, um Kollisionen besser zu veranschaulichen. Dieses begrenzte Beispiel verwendet außerdem nur Zeichenketten (oder Zeichen-Arrays in C).
Beispiel: Hash-Funktion
#define CAPACITY 50000 // Größe der Hash-Tabelle.
unsigned long hash_function(char* str)
{
unsigned long i = 0;
for (int j = 0; str[j]; j++)
i += str[j];
return i % CAPACITY;
}
Führen Sie diesen Code aus und testen Sie verschiedene Zeichenketten auf mögliche Kollisionen. Zum Beispiel kollidieren die Zeichenketten Hel und Cau, da sie denselben ASCII-Wert haben.
Dieser Code muss eine Zahl innerhalb der Grenzen der Kapazität der Hash-Tabelle zurückgeben. Andernfalls kann es zu einem Zugriff auf eine nicht gebundene Speicherposition kommen, was zu einem Fehler führt.
Definition der Datenstrukturen der Hash-Tabelle
Eine Hash-Tabelle ist ein Array von Elementen, die aus { Schlüssel: Wert }-Paaren bestehen.
Elementstruktur
typedef struct Ht_item
{
char* key;
char* value;
} Ht_item;
Die Hash-Tabelle enthält nun ein Array von Zeigern, die auf Ht_item verweisen, sodass sie ein Doppelzeiger ist.
Definition der Hash-Tabelle
typedef struct HashTable
{
// Enthält ein Array von Zeigern auf Elemente.
Ht_item** items;
int size;
int count;
} HashTable;
Ihre Hash-Tabelle muss die Anzahl der Elemente in der Tabelle mit count und die Größe der Tabelle mit size zurückgeben.
Erstellung und Verwaltung der Hash-Tabelle
Erstellen von Elementen der Hash-Tabelle
Erstellen Sie als Nächstes Funktionen zum Zuordnen von Speicher und Erstellen von Elementen. Elemente werden durch Zuordnen von Speicher für einen Schlüssel und einen Wert erstellt, und ein Zeiger auf das Element wird zurückgegeben:
Funktion zur Erstellung von Elementen
Ht_item* create_item(char* key, char* value)
{
// Erstellt einen Zeiger auf ein neues Hash-Tabelle-Element.
Ht_item* item = (Ht_item*) malloc(sizeof(Ht_item));
item->key = (char*) malloc(strlen(key) + 1);
item->value = (char*) malloc(strlen(value) + 1);
strcpy(item->key, key);
strcpy(item->value, value);
return item;
}
Fahren Sie mit diesem Muster für zusätzliche Funktionen wie das Erstellen der Tabelle, das Freigeben von Elementen und mehr wie im Tutorial beschrieben fort.
Erstellen der Hash-Tabelle
Erstellen Sie die Tabelle, indem Sie Speicher zuweisen und Größe, Anzahl und Elemente festlegen:
Funktion zur Erstellung der Tabelle
HashTable* create_table(int size)
{
// Erstellt eine neue Hash-Tabelle.
HashTable* table = (HashTable*) malloc(sizeof(HashTable));
table->size = size;
table->count = 0;
table->items = (Ht_item**) calloc(table->size, sizeof(Ht_item*));
for (int i = 0; i < table->size; i++)
table->items[i] = NULL;
return table;
}
Das obige Beispiel weist Speicher für die Wrapper-Struktur HashTable zu und setzt alle Elemente auf NULL.
Speicherfreigabe
Das Freigeben von Speicher ist in C/C++ eine bewährte Praxis. Geben Sie Speicher frei, den Sie mit malloc() und calloc() auf dem Heap zugewiesen haben.
Schreiben Sie Funktionen, die ein Tabellen-Element und die gesamte Tabelle freigeben:
Funktionen zum Freigeben von Elementen und Tabellen
void free_item(Ht_item* item)
{
// Gibt ein Element frei.
free(item->key);
free(item->value);
free(item);
}
void free_table(HashTable* table)
{
// Gibt die Tabelle frei.
for (int i = 0; i < table->size; i++)
{
Ht_item* item = table->items[i];
if (item != NULL)
free_item(item);
}
free(table->items);
free(table);
}
Darstellung der Hash-Tabelle
Fügen Sie eine print_table()-Funktion hinzu, um den Index, den Schlüssel und den Wert jedes Elements anzuzeigen:
Funktion zur Darstellung der Tabelle
void print_table(HashTable* table)
{
printf("\nHash-Tabelle\n-------------------\n");
for (int i = 0; i < table->size; i++)
{
if (table->items[i])
{
printf("Index:%d, Schlüssel:%s, Wert:%s\n", i, table->items[i]->key, table->items[i]->value);
}
}
printf("-------------------\n\n");
}
Damit ist die Grundfunktionalität Ihrer benutzerdefinierten Hash-Tabelle abgeschlossen. Als Nächstes schreiben Sie Funktionen zum Einfügen, Suchen und Löschen.
Einfügen in die Hash-Tabelle
Erstellen Sie eine Funktion ht_insert(), die Einfügungen durchführt. Die Funktion nimmt einen HashTable-Zeiger, einen Schlüssel und einen Wert als Parameter entgegen:
Einfüge-Funktion
void ht_insert(HashTable* table, char* key, char* value)
{
// Erstellt das Element.
Ht_item* item = create_item(key, value);
// Berechnet den Index.
int index = hash_function(key);
Ht_item* current_item = table->items[index];
if (current_item == NULL)
{
// Schlüssel existiert nicht.
if (table->count == table->size)
{
// Hash-Tabelle ist voll.
printf("Einfügefehler: Hash-Tabelle ist voll\n");
free_item(item);
return;
}
// Direkt einfügen.
table->items[index] = item;
table->count++;
}
else
{
// Szenario 1: Wert aktualisieren.
if (strcmp(current_item->key, key) == 0)
{
strcpy(table->items[index]->value, value);
return;
}
else
{
// Szenario 2: Kollision behandeln.
handle_collision(table, index, item);
return;
}
}
}
Fahren Sie mit der Implementierung von Funktionen zur Suche und Kollisionsbehandlung fort.
Suche nach Elementen in der Hash-Tabelle
Erstellen Sie eine Funktion ht_search(), die überprüft, ob der Schlüssel existiert, und den entsprechenden Wert zurückgibt, falls er existiert. Die Funktion nimmt einen HashTable-Zeiger und einen Schlüssel als Parameter entgegen:
Suchfunktion
char* ht_search(HashTable* table, char* key)
{
// Sucht den Schlüssel in der Hash-Tabelle.
// Gibt NULL zurück, falls er nicht existiert.
int index = hash_function(key);
Ht_item* item = table->items[index];
LinkedList* head = table->overflow_buckets[index];
// Nur nicht-NULL-Werte bereitstellen.
if (item != NULL)
{
if (strcmp(item->key, key) == 0)
return item->value;
if (head == NULL)
return NULL;
item = head->item;
head = head->next;
}
return NULL;
}
Suchergebnis drucken
Fügen Sie eine Funktion print_search() hinzu, um das Element anzuzeigen, das dem Schlüssel entspricht:
void print_search(HashTable* table, char* key)
{
char* val;
if ((val = ht_search(table, key)) == NULL)
{
printf("Schlüssel:%s existiert nicht\n", key);
return;
}
else {
printf("Schlüssel:%s, Wert:%s\n", key, val);
}
}
Ihre ht_search()-Funktion ist damit abgeschlossen.
Behandlung von Kollisionen
Es gibt verschiedene Methoden zur Behandlung von Kollisionen. Dieses Tutorial verwendet die Methode Separate Chaining, bei der unabhängige Ketten für alle Elemente erstellt werden, die denselben Hash-Index haben. Die Implementierung in diesem Tutorial verwendet verkettete Listen.
Definition der verketteten Liste
Wenn eine Kollision auftritt, werden zusätzliche Elemente, die an demselben Index kollidieren, zu einer Overflow-Bucket-Liste hinzugefügt:
typedef struct LinkedList {
Ht_item* item;
struct LinkedList* next;
} LinkedList;
LinkedList* allocate_list()
{
// Allokiert Speicher für einen Zeiger auf die verkettete Liste.
LinkedList* list = (LinkedList*) malloc(sizeof(LinkedList));
return list;
}
LinkedList* linkedlist_insert(LinkedList* list, Ht_item* item)
{
// Fügt das Element in die verkettete Liste ein.
if (!list)
{
LinkedList* head = allocate_list();
head->item = item;
head->next = NULL;
list = head;
return list;
}
else if (list->next == NULL)
{
LinkedList* node = allocate_list();
node->item = item;
node->next = NULL;
list->next = node;
return list;
}
LinkedList* temp = list;
while (temp->next->next)
{
temp = temp->next;
}
LinkedList* node = allocate_list();
node->item = item;
node->next = NULL;
temp->next = node;
return list;
}
Ht_item* linkedlist_remove(LinkedList* list)
{
// Entfernt das Kopf-Element aus der verketteten Liste.
// Gibt das Element des entfernten Elements zurück.
if (!list)
return NULL;
if (!list->next)
return NULL;
LinkedList* node = list->next;
LinkedList* temp = list;
temp->next = NULL;
list = node;
Ht_item* it = NULL;
memcpy(temp->item, it, sizeof(Ht_item));
free(temp->item->key);
free(temp->item->value);
free(temp->item);
free(temp);
return it;
}
void free_linkedlist(LinkedList* list)
{
LinkedList* temp = list;
while (list)
{
temp = list;
list = list->next;
free(temp->item->key);
free(temp->item->value);
free(temp->item);
free(temp);
}
}
Integration der Overflow-Buckets
Fügen Sie der Hash-Tabelle Overflow-Buckets hinzu:
typedef struct HashTable HashTable;
// Definition der Hash-Tabelle.
struct HashTable
{
// Enthält ein Array von Zeigern auf Elemente.
Ht_item** items;
LinkedList** overflow_buckets;
int size;
int count;
};
Aktualisieren Sie die Funktionen create_table() und free_table(), um diese Buckets einzubeziehen.
Erstellen und Freigeben von Overflow-Buckets
LinkedList** create_overflow_buckets(HashTable* table)
{
// Erstellt die Overflow-Buckets, ein Array von verketteten Listen.
LinkedList** buckets = (LinkedList**) calloc(table->size, sizeof(LinkedList*));
for (int i = 0; i < table->size; i++)
buckets[i] = NULL;
return buckets;
}
void free_overflow_buckets(HashTable* table)
{
// Gibt alle Overflow-Bucket-Listen frei.
LinkedList** buckets = table->overflow_buckets;
for (int i = 0; i < table->size; i++)
free_linkedlist(buckets[i]);
free(buckets);
}
Die Behandlung von Kollisionen ist nun effizient integriert. Fahren Sie mit der Implementierung der Löschlogik fort.
Löschen aus der Hash-Tabelle
Erstellen Sie eine Funktion ht_delete(), um ein Element aus der Hash-Tabelle zu entfernen. Die Funktion nimmt einen HashTable-Zeiger und einen Schlüssel als Parameter entgegen:
Löschfunktion
void ht_delete(HashTable* table, char* key)
{
// Löscht ein Element aus der Tabelle.
int index = hash_function(key);
Ht_item* item = table->items[index];
LinkedList* head = table->overflow_buckets[index];
if (item == NULL)
{
// Existiert nicht.
return;
}
else {
if (head == NULL && strcmp(item->key, key) == 0)
{
// Keine Kollisionskette vorhanden.
// Element entfernen.
// Tabellenindex auf NULL setzen.
table->items[index] = NULL;
free_item(item);
table->count--;
return;
}
else if (head != NULL)
{
// Kollisionskette existiert.
if (strcmp(item->key, key) == 0)
{
// Dieses Element entfernen.
// Setzen Sie den Kopf der Liste als neues Element.
free_item(item);
LinkedList* node = head;
head = head->next;
node->next = NULL;
table->items[index] = create_item(node->item->key, node->item->value);
free_linkedlist(node);
table->overflow_buckets[index] = head;
return;
}
LinkedList* curr = head;
LinkedList* prev = NULL;
while (curr)
{
if (strcmp(curr->item->key, key) == 0)
{
if (prev == NULL)
{
// Erstes Element der Kette.
// Kette entfernen.
free_linkedlist(head);
table->overflow_buckets[index] = NULL;
return;
}
else
{
// Irgendwo in der Kette.
prev->next = curr->next;
curr->next = NULL;
free_linkedlist(curr);
table->overflow_buckets[index] = head;
return;
}
}
curr = curr->next;
prev = curr;
}
}
}
}
Testen der Hash-Tabelle
Erstellen Sie eine main()-Funktion, um die Funktionalität der Hash-Tabelle zu testen. Einfügen-, Such- und Löschvorgänge werden validiert.
Main-Funktion
int main()
{
HashTable* ht = create_table(CAPACITY);
ht_insert(ht, (char*)"1", (char*)"Erste Adresse");
ht_insert(ht, (char*)"2", (char*)"Zweite Adresse");
ht_insert(ht, (char*)"Hel", (char*)"Dritte Adresse");
ht_insert(ht, (char*)"Cau", (char*)"Vierte Adresse");
print_search(ht, (char*)"1");
print_search(ht, (char*)"2");
print_search(ht, (char*)"3");
print_search(ht, (char*)"Hel");
print_search(ht, (char*)"Cau"); // Kollision!
print_table(ht);
ht_delete(ht, (char*)"1");
ht_delete(ht, (char*)"Cau");
print_table(ht);
free_table(ht);
return 0;
}
Ausgabe
Dieser Code erzeugt die folgende Ausgabe:
Schlüssel:1, Wert:Erste Adresse
Schlüssel:2, Wert:Zweite Adresse
Schlüssel:3 existiert nicht
Schlüssel:Hel, Wert:Dritte Adresse
Schlüssel:Cau existiert nicht
Hash-Tabelle
-------------------
Index:49, Schlüssel:1, Wert:Erste Adresse
Index:50, Schlüssel:2, Wert:Zweite Adresse
Index:281, Schlüssel:Hel, Wert:Dritte Adresse
-------------------
Hash-Tabelle
-------------------
Index:50, Schlüssel:2, Wert:Zweite Adresse
Index:281, Schlüssel:Hel, Wert:Dritte Adresse
-------------------
Fazit
In diesem Artikel haben Sie eine Hash-Tabelle in C/C++ von Grund auf implementiert. Experimentieren Sie mit anderen Methoden zur Behandlung von Kollisionen und verschiedenen Hash-Funktionen, um Ihre Hash-Tabelle zu optimieren und ein tieferes Verständnis zu gewinnen.
