Datenstrukturen in C/C++

Hashtabelle

Eine Hashfunktion ordnet Schlüssel Buckets zu; Kollisionen benötigen Verkettung oder offene Adressierung.

Was ist Hashtabelle?

Eine Hashfunktion ordnet Schlüssel Buckets zu; Kollisionen benötigen Verkettung oder offene Adressierung.

Zähle Wörter mit Verkettung und unordered_map.

Wichtige Punkte

Definiere Invarianten vor den Operationen.
Behandle leere, volle und fehlgeschlagene Allokationen.
Bewerte Laufzeit und Speicherbesitz gemeinsam.

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

Erwartete Ausgabe

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

Erwartete Ausgabe

c=2 cpp=1

Vergleich zwischen C und C++

Das C-Beispiel nutzt feste Schlüssel, um Buckets zu zeigen; std::unordered_map verwaltet Knoten, Wachstum und beliebige Strings.

Strukturen und Operationen sind getrennt; Allokation ist explizit.

C++

Klassen und Container schützen Invarianten und verwalten Ressourcen.

Übungsaufgaben

Führe beide Versionen aus und untersuche die unterschiedlichen Garantien.

Teste leere und volle Zustände.
Implementiere Cleanup und prüfe auf Leaks.
Vergleiche mit einem Standardcontainer.