Hashfunksjoner
Avbild nøkler til bøtter
Hashfunksjoner er en gratis leksjon i C Academy på CoddyKit. Dette er leksjon 1 av 4. Du kan lese hele leksjonen gratis nedenfor – og deretter øve praktisk i nettleseren med en innebygd kodeeditor og en AI-veileder som er tilgjengelig døgnet rundt. Den er en del av læringsløpet i C Academy, og fremdriften din synkroniseres mellom nettet og CoddyKit-appen. Kurset i C Academy inneholder totalt 4 leksjoner.
Hva er en hashfunksjon
En hashfunksjon tar en nøkkel og produserer en heltallsindeks i en tabell med bøtter. Den er selve kjernen i en hash-tabell og gjør vilkårlige nøkler, som strenger, om til raske tabellposisjoner.
- Inndata: en nøkkel (streng, heltall osv.)
- Utdata: en bøtteindeks i
[0, capacity)
Egenskaper ved en god hashfunksjon
En god hashfunksjon er deterministisk, rask og fordeler nøkler jevnt mellom bøttene.
- Den samme nøkkelen gir alltid den samme indeksen
- Små endringer i nøkkelen gir store endringer i indeksen (skredeffekt)
- Få kollisjoner for typiske data
Avbild til en bøtte
Når De har beregnet en rå hashverdi, avbilder De den i tabellen ved hjelp av modulooperatoren: index = hash % capacity.
Bruk en unsigned-type, slik at modulo aldri produserer en negativ 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 enkel sum-hash
Den enkleste streng-hashen legger sammen tegnverdiene. Den er enkel, men fordeler dårlig fordi anagrammer kolliderer.
Kjør den for å se to forskjellige strenger som hashes til nærliggende verdier.
#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, godt distribuert streng-hash av Daniel J. Bernstein. Den starter på 5381 og bruker hash * 33 + c.
Multiplikasjonen og addisjonen blander bitene langt bedre enn en vanlig 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 bruker XOR på hver byte og multipliserer deretter med et primtall. Den er enkel, rask og mye brukt.
Rekkefølge: XOR først, deretter multiplikasjon (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;
}Hashing av heltall
Heltallsnøkler trenger fortsatt blanding, fordi x % capacity alene skaper klynger når nøklene deler mønstre. En multiplikativ blanding (Knuth) sprer bitene.
#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;
}Kapasiteter som er toerpotenser
Når kapasiteten er en toerpotens, kan De erstatte % capacity med en rask bitvis AND: hash & (capacity - 1).
Dette fungerer bare fordi de laveste bitene i en toerpotens minus én danner en full 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 tregt
Operatoren % kompileres til en divisjonsinstruksjon, som er tregere enn AND. I tette løkker har dette betydning.
- Tabell med toerpotens som størrelse: bruk en AND-maske
- Tabell med primtallsstørrelse: bruk modulo (bedre fordeling for svake hasher)
Kollisjoner er uunngåelige
På grunn av skuffeprinsippet garanterer avbildning av mange nøkler til færre bøtter at det oppstår kollisjoner. En god hashfunksjon minimerer dem, men kan ikke fjerne dem.
Neste leksjon dekker hvordan kollisjoner løses.
Demo av fordeling
La oss telle hvordan DJB2 fordeler noen nøkler mellom 8 bøtter. Gode hasher fordeler dem ganske jevnt.
#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;
}Kort sjekk
Test forståelsen Deres av det grunnleggende ved hashfunksjoner.
Oppsummering
De har lært hva en hashfunksjon gjør, og hvordan nøkler avbildes til bøtter.
- Gode hasher er deterministiske, raske og jevne
- DJB2 og FNV-1a er gode streng-hasher
- Avbild med
% capacity, eller& (capacity-1)for toerpotenser - Bruk unsigned-typer; kollisjoner er uunngåelige
Lær deg C med en AI-veileder – gratis
Skriv og kjør ekte kode i nettleseren, få umiddelbar hjelp fra en AI-veileder som er tilgjengelig døgnet rundt, og fortsett der du slapp – på nettet eller i appen.
- Kurs
- 39
- Leksjoner
- 144
Ofte stilte spørsmål
Er leksjonen «Hashfunksjoner» gratis?
Ja – hele teksten i «Hashfunksjoner» er gratis å lese her på nettet. For å øve interaktivt med en innebygd kodeeditor og en AI-veileder som er tilgjengelig døgnet rundt, og for å låse opp resten av C Academy-kurset, kan du oppgradere til CoddyKit PRO. Kurset i C Academy inneholder totalt 4 leksjoner.
Hva lærer jeg i «Hashfunksjoner»?
Avbild nøkler til bøtter Du øver på C Academy med praktisk kode som du kjører direkte i nettleseren, mens en AI-veileder som er tilgjengelig døgnet rundt, svarer på spørsmålene dine mens du jobber deg gjennom leksjonen.
Trenger jeg erfaring for å begynne med C Academy?
Ingen tidligere erfaring er nødvendig. C Academy på CoddyKit er lagt opp for både nybegynnere og viderekomne, så De kan begynne her eller helt fra start og lære i Deres eget tempo. Dette er leksjon 1 av 4.
Hvor lang tid tar leksjonen «Hashfunksjoner»?
De fleste CoddyKit-leksjoner tar omtrent 5–10 minutter. Hver leksjon er kort og interaktiv, slik at De gjør jevne fremskritt og kan fortsette akkurat der De slapp – både på nettet og i appen.
Kan jeg skrive og kjøre kode i denne C Academy-leksjonen?
Ja. Alle C Academy-leksjoner har en innebygd kodeeditor, slik at De kan skrive og kjøre ekte kode direkte i nettleseren og få umiddelbar tilbakemelding fra AI – uten lokal konfigurering.