C Academy · Lektion

Hashfunktioner

Map nøgler til buckets

Lektion 1 af 413 trin

Hashfunktioner er en gratis C Academy-lektion på CoddyKit. Dette er lektion 1 af 4. Du kan læse hele lektionen gratis nedenfor — og derefter øve dig praktisk i browseren med en indbygget kodeeditor og en AI-vejleder, der er tilgængelig døgnet rundt. Den er en del af læringsforløbet i C Academy, og dine fremskridt synkroniseres på tværs af nettet og CoddyKit-appen. C Academy-kurset indeholder 4 lektioner i alt.

Hvad er en hashfunktion

En hashfunktion tager en nøgle og producerer et heltalsindeks i et array af spande. Den er kernen i en hashtabel og omdanner vilkårlige nøgler som strenge til hurtige arraypositioner.

Input: en nøgle (streng, heltal osv.)
Output: et spandeindeks i [0, capacity)

Egenskaber ved en god hashfunktion

En god hashfunktion er deterministisk, hurtig og fordeler nøglerne ensartet mellem spandene.

Den samme nøgle giver altid det samme indeks
Små ændringer i nøglen giver store ændringer i indekset (lavineeffekt)
Få kollisioner for typiske data

Map til en spand

Når du har beregnet en rå hashværdi, mapper du den ind i tabellen ved hjælp af modulo-operatoren: index = hash % capacity.

Brug en unsigned-type, så modulo aldrig producerer et negativt indeks.

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

En simpel sumhash

Den enkleste strenghash lægger tegnværdierne sammen. Den er nem, men fordeler dårligt, fordi anagrammer giver kollisioner.

Kør den for at se to forskellige strenge blive hashet til værdier tæt på hinanden.

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

DJB2-hashen

DJB2 er en klassisk, velfordelt strenghash af Daniel J. Bernstein. Den starter ved 5381 og bruger hash * 33 + c.

Multiplikation og addition blander bittene langt bedre end en simpel sum.

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

FNV-1a-hashen

FNV-1a XOR'er hver byte og multiplicerer derefter med et primtal. Den er enkel, hurtig og bruges bredt.

Rækkefølge: XOR først, derefter multiplikation (det er 1a-varianten).

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

Hashning af heltal

Heltalsnøgler skal stadig blandes, fordi x % capacity alene danner klynger, når nøgler deler mønstre. En multiplikativ blanding (Knuth) spreder bittene.

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

Kapaciteter som potenser af to

Når kapaciteten er en potens af to, kan du erstatte % capacity med en hurtig bitvis AND: hash & (capacity - 1).

Det virker kun, fordi de lave bit i en potens af to minus én danner en fuld maske.

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

Hvorfor modulo kan være langsom

Operatoren % kompileres til en divisionsinstruktion, som er langsommere end AND. I stramme løkker har det betydning.

Tabel med kapacitet som potens af to: brug en AND-maske
Tabel med primtalsstørrelse: brug modulo (bedre fordeling ved svage hasher)

Kollisioner er uundgåelige

Ifølge skuffeprincippet garanterer mapping af mange nøgler til færre spande kollisioner. En god hashfunktion minimerer dem, men kan ikke fjerne dem.

Næste lektion gennemgår, hvordan kollisioner håndteres.

Demonstration af fordeling

Lad os tælle, hvordan DJB2 fordeler nogle få nøgler mellem 8 spande. Gode hasher fordeler dem nogenlunde ensartet.

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

Hurtigt tjek

Test din forståelse af det grundlæggende i hashfunktioner.

Besvar den i den interaktive lektion

Opsummering

Du har lært, hvad en hashfunktion gør, og hvordan nøgler mappes til spande.

Gode hasher er deterministiske, hurtige og ensartede
DJB2 og FNV-1a er solide strenghashfunktioner
Map med % capacity eller & (capacity-1) for potenser af to
Brug unsigned-typer; kollisioner er uundgåelige

Gratis at komme i gang

Lær C med en AI-underviser — gratis

Skriv og kør rigtig kode i din browser, få øjeblikkelig hjælp fra en AI-underviser døgnet rundt, og fortsæt, hvor du slap, på web eller i appen.

Kurser: 39
Lektioner: 144

Start gratis Se hele kurset

Ofte stillede spørgsmål

Er lektionen “Hashfunktioner” gratis?

Ja — hele teksten til “Hashfunktioner” kan læses gratis her på nettet. Hvis du vil øve dig interaktivt med en indbygget kodeeditor og en AI-vejleder døgnet rundt og få adgang til resten af C Academy-kurset, skal du opgradere til CoddyKit PRO. C Academy-kurset indeholder 4 lektioner i alt.

Hvad lærer jeg i “Hashfunktioner”?

Map nøgler til buckets Du øver dig i C Academy med praktisk kode, som du kører direkte i browseren, og en AI-vejleder døgnet rundt besvarer dine spørgsmål, mens du arbejder dig gennem lektionen.

Skal jeg have erfaring for at begynde på C Academy?

Der kræves ingen tidligere erfaring. C Academy på CoddyKit er tilrettelagt for både begyndere og øvede, så du kan starte her eller fra begyndelsen og lære i dit eget tempo. Dette er lektion 1 af 4.

Hvor lang tid tager lektionen “Hashfunktioner”?

De fleste CoddyKit-lektioner tager cirka 5–10 minutter. Hver lektion er kort og interaktiv, så du gør løbende fremskridt og kan fortsætte, hvor du slap – på både web og app.

Kan jeg skrive og køre kode i denne C Academy-lektion?

Ja. Alle C Academy-lektioner har en indbygget kodeeditor, så du kan skrive og køre rigtig kode direkte i din browser og få øjeblikkelig feedback fra AI – uden lokal opsætning.

Alle lektioner i dette kursus

← Tilbage til C Academy