Datenstrukturen in C/C++

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.

  • Fortgeschritten
  • 5 Min. Lesezeit
  • 2 ausführbare Beispiele

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.

Vom Adressbuch zum Code
hash(text)🔤 Das Register aus dem Schlüssel selbst ausrechnen
buckets[bucket]📑 Die Seite hinter diesem Register
item->next📝 Weitere Namen auf derselben Seite (Chaining)
strcmp(item->key, ...)🔍 Prüfen, welcher Eintrag genau der gesuchte ist
Den Schlüssel auf einen Bucket hashen und nur diesen Bucket durchsuchen.
In einem Satz

Eine 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

  1. hash mischt die Zeichen eines Schlüssels zu einer Zahl und gibt value % 5 zurück, einen Bucket-Index.
  2. Jedes Item hat einen next-Zeiger, also bilden Schlüssel im selben Bucket eine Kette.
  3. Um ein Wort zu zählen, hasht der Code es, durchläuft die Kette des Buckets und vergleicht die Schlüssel mit strcmp.
  4. In C++ übernimmt std::unordered_map das 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::map oder 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++

C
Code ausführen →
main.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);
}
Run-Button für dieses Beispiel erstellen Ergebnis der Ausführung
c=2 cpp=1
C++
Code ausführen →
main.cpp
#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';
}
Run-Button für dieses Beispiel erstellen Ergebnis der Ausführung
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.

C

Daten (struct) und Operationen sind getrennt, und Speicher wird von Hand reserviert und freigegeben.

C++

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.

Problem
if (item->key == word)
Lösung
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.

Problem
return buckets[hash(word)];
Lösung
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.

Alle Challenges