C Academy · Lektion

Hash-Funktionen

Schlüssel auf Buckets abbilden

Hash-Funktionen ist eine kostenlose C Academy-Lektion auf CoddyKit. Dies ist Lektion 1 von 4. Du kannst die komplette Lektion unten kostenlos lesen – dann übst du sie direkt im Browser mit einem integrierten Code-Editor und einem KI-Tutor rund um die Uhr. Sie ist Teil des C Academy-Lernpfads, und dein Fortschritt wird über Web und CoddyKit-App synchronisiert. Der C Academy-Kurs umfasst insgesamt 4 Lektionen.

Was ist eine Hashfunktion

Eine Hashfunktion nimmt einen Schlüssel entgegen und erzeugt einen ganzzahligen Index in einem Array von Buckets. Sie bildet das Herzstück einer Hashtabelle und wandelt beliebige Schlüssel wie Zeichenketten in schnell erreichbare Array-Positionen um.

Eingabe: ein Schlüssel (Zeichenkette, Ganzzahl usw.)
Ausgabe: ein Bucket-Index in [0, capacity)

Eigenschaften eines guten Hashes

Eine gute Hashfunktion ist deterministisch, schnell und verteilt Schlüssel gleichmäßig auf die Buckets.

Für denselben Schlüssel wird immer derselbe Index erzeugt
Kleine Änderungen am Schlüssel verursachen große Änderungen am Index (Avalanche-Effekt)
Wenige Kollisionen bei typischen Daten

Auf einen Bucket abbilden

Sobald Sie einen rohen Hashwert berechnet haben, bilden Sie ihn mithilfe des Modulo-Operators auf die Tabelle ab: index = hash % capacity.

Verwenden Sie einen unsigned-Typ, damit das Modulo niemals einen negativen Index erzeugt.

#include <stdio.h>

int main(void) {
    unsigned long hash = 123456789UL;
    unsigned capacity = 16;
    unsigned index = (unsigned)(hash % capacity);
    printf("bucket = %u\n", index);
    return 0;
}

Ein einfacher Summen-Hash

Der einfachste String-Hash addiert die Zeichenwerte. Er ist leicht umzusetzen, verteilt Werte jedoch schlecht, da Anagramme kollidieren.

Führen Sie ihn aus, um zu sehen, wie zwei verschiedene Zeichenketten auf nahe beieinanderliegende Werte abgebildet werden.

#include <stdio.h>

unsigned long sum_hash(const char *s) {
    unsigned long h = 0;
    while (*s) h += (unsigned char)*s++;
    return h;
}

int main(void) {
    printf("%lu\n", sum_hash("abc"));
    printf("%lu\n", sum_hash("cba"));
    return 0;
}

Der DJB2-Hash

DJB2 ist ein klassischer, gut verteilter String-Hash von Daniel J. Bernstein. Er beginnt bei 5381 und verwendet hash * 33 + c.

Die Kombination aus Multiplizieren und Addieren vermischt die Bits deutlich besser als eine einfache Summe.

#include <stdio.h>

unsigned long djb2(const char *s) {
    unsigned long h = 5381;
    int c;
    while ((c = (unsigned char)*s++))
        h = ((h << 5) + h) + c; /* h * 33 + c */
    return h;
}

int main(void) {
    printf("%lu\n", djb2("hello"));
    printf("%lu\n", djb2("world"));
    return 0;
}

Der FNV-1a-Hash

FNV-1a führt zunächst eine XOR-Operation für jedes Byte aus und multipliziert anschließend mit einer Primzahl. Er ist einfach, schnell und weit verbreitet.

Reihenfolge: zuerst XOR, dann multiplizieren (das ist die 1a-Variante).

#include <stdio.h>

unsigned long fnv1a(const char *s) {
    unsigned long h = 1469598103934665603UL;
    while (*s) {
        h ^= (unsigned char)*s++;
        h *= 1099511628211UL;
    }
    return h;
}

int main(void) {
    printf("%lu\n", fnv1a("key1"));
    printf("%lu\n", fnv1a("key2"));
    return 0;
}

Ganzzahlen hashen

Auch ganzzahlige Schlüssel müssen vermischt werden, da x % capacity allein zu einer Häufung führt, wenn die Schlüssel bestimmte Muster teilen. Eine multiplikative Mischung nach Knuth verteilt die Bits.

#include <stdio.h>

unsigned hash_int(unsigned x, unsigned cap) {
    x *= 2654435761u; /* Knuth multiplicative */
    return x % cap;
}

int main(void) {
    for (unsigned i = 0; i < 5; i++)
        printf("%u -> %u\n", i, hash_int(i, 8));
    return 0;
}

Kapazitäten als Zweierpotenzen

Wenn die Kapazität eine Zweierpotenz ist, können Sie % capacity durch eine schnelle bitweise UND-Operation ersetzen: hash & (capacity - 1).

Das funktioniert nur, weil die niederwertigen Bits von „Zweierpotenz minus eins“ eine vollständige Maske bilden.

#include <stdio.h>

int main(void) {
    unsigned long hash = 123456789UL;
    unsigned capacity = 16; /* power of two */
    unsigned index = (unsigned)(hash & (capacity - 1));
    printf("bucket = %u\n", index);
    return 0;
}

Warum Modulo langsam sein kann

Der Operator % wird in eine Divisionsanweisung kompiliert, die langsamer ist als eine UND-Operation. In engen Schleifen ist das relevant.

Tabelle mit Zweierpotenz: UND-Maske verwenden
Tabelle mit Primzahlgröße: Modulo verwenden (bessere Verteilung bei schwachen Hashes)

Kollisionen sind unvermeidbar

Nach dem Schubfachprinzip sind Kollisionen garantiert, wenn viele Schlüssel auf weniger Buckets abgebildet werden. Eine gute Hashfunktion minimiert sie, kann sie jedoch nicht vollständig verhindern.

In der nächsten Lektion geht es darum, wie Kollisionen aufgelöst werden.

Verteilungsdemo

Zählen wir, wie DJB2 einige Schlüssel auf 8 Buckets verteilt. Gute Hashfunktionen verteilen Werte einigermaßen gleichmäßig.

#include <stdio.h>

unsigned long djb2(const char *s) {
    unsigned long h = 5381;
    int c;
    while ((c = (unsigned char)*s++)) h = ((h << 5) + h) + c;
    return h;
}

int main(void) {
    const char *keys[] = {"apple", "banana", "cherry", "date"};
    int counts[8] = {0};
    for (int i = 0; i < 4; i++)
        counts[djb2(keys[i]) % 8]++;
    for (int i = 0; i < 8; i++)
        printf("bucket %d: %d\n", i, counts[i]);
    return 0;
}

Kurztest

Testen Sie Ihr Verständnis der Grundlagen von Hashfunktionen.

Zusammenfassung

Sie haben gelernt, was eine Hashfunktion bewirkt und wie Schlüssel auf Buckets abgebildet werden.

Gute Hashfunktionen sind deterministisch, schnell und gleichmäßig
DJB2 und FNV-1a sind solide Hashfunktionen für Zeichenketten
Abbildung mit % capacity oder bei Zweierpotenzen mit & (capacity-1)
Verwenden Sie vorzeichenlose Typen; Kollisionen sind unvermeidbar

Häufig gestellte Fragen

Ist die Lektion „Hash-Funktionen“ kostenlos?

Ja — der vollständige Text von „Hash-Funktionen“ ist hier im Web kostenlos zu lesen. Um sie interaktiv zu üben (integrierter Code-Editor und 24/7 KI-Tutor) und den Rest des C Academy-Kurses freizuschalten, upgrade auf CoddyKit PRO. Der C Academy-Kurs umfasst insgesamt 4 Lektionen.

Was lerne ich in „Hash-Funktionen“?

Schlüssel auf Buckets abbilden Du übst C Academy mit praktischem Code, den du direkt im Browser ausführst, und ein 24/7 KI-Tutor beantwortet deine Fragen während du die Lektion bearbeitest.

Brauche ich Erfahrung, um C Academy zu starten?

Keine Vorkenntnisse erforderlich. C Academy auf CoddyKit ist für Anfänger bis fortgeschrittene Lernende strukturiert, sodass du hier starten oder von Anfang an beginnen und in deinem eigenen Tempo voranschreiten kannst. Dies ist Lektion 1 von 4.

Wie lange dauert die Lektion „Hash-Funktionen“?

Die meisten CoddyKit-Lektionen dauern etwa 5–10 Minuten. Jede ist kompakt und interaktiv, sodass du stetig Fortschritte machst und genau dort weitermachst, wo du aufgehört hast – im Web und in der App.

Kann ich in dieser C Academy-Lektion Code schreiben und ausführen?

Ja. Jede C Academy-Lektion enthält einen integrierten Code-Editor, sodass du echten Code direkt in deinem Browser schreibst und ausführst und sofort KI-Feedback erhältst — ohne lokale Einrichtung erforderlich.

Alle Lektionen in diesem Kurs

← Zurück zu C Academy