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.

Einführung

Eine Hashtabelle (hash table) wandelt mit einer Hashfunktion (hash function) jeden Schlüssel in den Index eines Speicherplatzes (Bucket) um, deshalb laufen Suchen, Einfügen und Löschen sehr schnell. Landen zwei verschiedene Schlüssel im selben Bucket, spricht man von einer Kollision (collision), und die Hashtabelle braucht eine Strategie wie Verkettung (chaining) oder offene Adressierung (open addressing).

Wichtige Punkte

Lege fest, welche Bedingungen in der Datenstruktur immer gelten müssen (Invarianten), bevor du die Operationen schreibst.
Behandle die Fälle leer, voll und fehlgeschlagene Speicherreservierung vollständig.
Bewerte bei jeder Operation Komplexität und Speicherverwaltung gemeinsam.

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++

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);
}

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';
}

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.

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.

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