Hashtabelle (hash table) in C und C++
In dieser Lektion zählst du mit einer selbst geschriebenen Hashtabelle in C und mit std::unordered_map in C++, wie oft jedes Wort vorkommt.
Einführung
Das Problem
Zählen, wie oft jedes Wort vorkommt, oder einen Benutzer über seinen Namen finden: Dafür brauchst du schnellen Zugriff über einen Schlüssel. Jedes Mal eine Liste zu durchsuchen wird langsam, wenn die Daten wachsen. Eine Hashtabelle springt fast direkt an die richtige Stelle.
Stell es dir so vor
Eine Hashtabelle ist wie ein Adressbuch mit Buchstabenregister. Der Name selbst verrät dir, welches Register du aufschlagen musst, also liest du nie das ganze Buch. Mehrere Namen teilen sich ein Register, deshalb liest du nur diese eine Seite, um genau den richtigen Namen zu finden.
hash(text)🔤 Das Register aus dem Schlüssel selbst ausrechnenbuckets[bucket]📑 Die Seite hinter diesem Registeritem->next📝 Weitere Namen auf derselben Seite (Chaining)strcmp(item->key, ...)🔍 Prüfen, welcher Eintrag genau der gesuchte istEine Hashtabelle speichert Schlüssel-Wert-Paare in einem Array von Buckets. Eine Hashfunktion berechnet den Bucket jedes Schlüssels, sodass eine Suche meist in konstanter Zeit abläuft.
Wichtige Punkte
hashmischt die Zeichen eines Schlüssels zu einer Zahl und gibtvalue % 5zurück, einen Bucket-Index.- Jedes
Itemhat einennext-Zeiger, also bilden Schlüssel im selben Bucket eine Kette. - Um ein Wort zu zählen, hasht der Code es, durchläuft die Kette des Buckets und vergleicht die Schlüssel mit
strcmp. - In C++ übernimmt
std::unordered_mapdas Hashen, Verketten und Wachsen für dich:++counts[word].
Wann du es brauchst
- Vorkommen zählen, etwa Worthäufigkeiten.
- Schnelles Nachschlagen über einen Schlüssel: Caches, Symboltabellen, Benutzerdatensätze.
- Duplikate entfernen oder prüfen, ob etwas enthalten ist.
Wann du es nicht brauchst
- Du brauchst die Schlüssel sortiert: Nimm
std::mapoder sortiere die Schlüssel. - Sehr kleine Sammlungen, bei denen eine einfache Suche im Array schnell genug ist.
So funktioniert es
Gib einen Schlüssel ein und speichere oder suche ihn. Der Schlüssel wird zu einer Bucket-Nummer gehasht, sodass das Programm direkt zum richtigen Bucket springt.
Codebeispiele in C und C++
#include <stdio.h>
#include <string.h>
typedef struct Item {
const char *key;
int count;
struct Item *next;
} Item;
unsigned hash(const char *text) {
unsigned value = 5381;
while (*text) {
value = value * 33u ^ (unsigned char)*text++;
}
return value % 5;
}
int main(void) {
const char *words[] = {"c", "cpp", "c"};
Item items[2] = {{"c", 0, NULL}, {"cpp", 0, NULL}};
Item *buckets[5] = {0};
for (int index = 0; index < 2; ++index) {
unsigned bucket = hash(items[index].key);
items[index].next = buckets[bucket];
buckets[bucket] = &items[index];
}
for (int index = 0; index < 3; ++index) {
Item *item = buckets[hash(words[index])];
for (; item; item = item->next) {
if (strcmp(item->key, words[index]) == 0) {
++item->count;
break;
}
}
}
printf("c=%d cpp=%d\n", items[0].count, items[1].count);
}
c=2 cpp=1
#include <iostream>
#include <string>
#include <unordered_map>
int main() {
std::unordered_map<std::string, int> counts;
for (const std::string word : {"c", "cpp", "c"}) {
++counts[word];
}
std::cout << "c=" << counts["c"]
<< " cpp=" << counts["cpp"] << '\n';
}
c=2 cpp=1
C und C++ im Vergleich
Die Funktion hash in C berechnet aus den Zeichen des Strings einen Wert und nimmt den Rest der Division durch 5, um einen der 5 Buckets auszuwählen. Jeder Bucket ist eine verkettete Liste, deshalb werden kollidierende Wörter im selben Bucket aneinandergehängt. Das C-Beispiel verwendet nur wenige feste Wörter, um sich auf den Bucket-Mechanismus zu konzentrieren. In C++ verwaltet std::unordered_map die Knoten selbst, wächst bei Bedarf und akzeptiert beliebige Strings als Schlüssel.
Daten (struct) und Operationen sind getrennt, und Speicher wird von Hand reserviert und freigegeben.
Klassen und Container schützen die Korrektheit der Daten und verwalten ihre Ressourcen selbst.
Übungen zur Vertiefung
Führe beide Versionen aus und ändere dann den Code, um zu beobachten, welche Sicherheit jede Sprache bietet.
- Ergänze Tests für den leeren Zustand und für das Erreichen der Kapazitätsgrenze.
- Schreibe die Speicherfreigabe und prüfe auf Speicherlecks.
- Vergleiche die Komplexität mit dem entsprechenden Container der Standardbibliothek.
Häufige Fehler
String-Schlüssel mit == vergleichen
In C vergleicht == Adressen, nicht die Zeichen.
if (item->key == word)
if (strcmp(item->key, word) == 0)
Kollisionen ignorieren
Zwei Schlüssel können sich einen Bucket teilen, also musst du den Schlüssel prüfen, nicht nur den Bucket.
return buckets[hash(word)];
for (Item *item = buckets[hash(word)]; item; item = item->next)
if (strcmp(item->key, word) == 0) return item;
Lektion fertig?
Markiere sie als gelernt, um deinen Fortschritt zu verfolgen.
Mit einer Challenge üben
Nutze den Inhalt dieser Lektion, um ein echtes Problem zu lösen. Jede Challenge läuft im Browser, mit sofortigen Tests und einem KI-Review.
- Erstes eindeutiges Zeichen Finde das erste Zeichen, das nur einmal vorkommt. Einfach
- Zeichenhäufigkeit Zähle, wie oft jedes Zeichen vorkommt. Einfach