Hashfunktioner
Mappa nycklar till buckets.
Hashfunktioner är en gratis lektion i C Academy på CoddyKit. Detta är lektion 1 av 4. Ni kan läsa hela lektionen gratis nedan och sedan öva praktiskt i webbläsaren med en inbyggd kodredigerare och en AI-handledare som är tillgänglig dygnet runt. Den ingår i lärvägen för C Academy, och Era framsteg synkroniseras mellan webben och CoddyKit-appen. Kursen i C Academy innehåller totalt 4 lektioner.
Vad är en hashfunktion
En hashfunktion tar en nyckel och producerar ett heltalsindex i en array med bucketar. Den är kärnan i en hashtabell och omvandlar godtyckliga nycklar, till exempel strängar, till snabba arraypositioner.
- Indata: en nyckel (sträng, heltal och så vidare)
- Utdata: ett bucketindex i
[0, capacity)
Egenskaper hos en bra hashfunktion
En bra hashfunktion är deterministisk, snabb och fördelar nycklarna jämnt mellan bucketarna.
- Samma nyckel ger alltid samma index
- Små förändringar i nyckeln ger stora förändringar i indexet (lavineffekt)
- Få kollisioner för typiska data
Mappa till en bucket
När du har beräknat ett rått hashvärde mappar du det till tabellen med modulooperatorn: index = hash % capacity.
Använd en typ med unsigned så att modulo aldrig producerar ett negativt index.
#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 summeringshash
Den enklaste stränghashfunktionen summerar tecknens värden. Den är enkel men fördelar värdena dåligt eftersom anagram kolliderar.
Kör den för att se två olika strängar hashas till närliggande värden.
#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-hashfunktionen
DJB2 är en klassisk, välfördelad stränghashfunktion av Daniel J. Bernstein. Den börjar på 5381 och använder hash * 33 + c.
Multiplikationen och additionen blandar bitarna mycket bättre än en vanlig summa.
#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-hashfunktionen
FNV-1a XOR:ar varje byte och multiplicerar sedan med ett primtal. Den är enkel, snabb och används ofta.
Ordningen är: XOR först och multiplicera sedan (det är varianten 1a).
#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 av heltal
Även heltalsnycklar behöver blandas, eftersom enbart x % capacity skapar kluster när nycklarna har gemensamma mönster. En multiplikativ blandning (Knuth) sprider bitarna.
#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 är tvåpotenser
När kapaciteten är en tvåpotens kan du ersätta % capacity med en snabb bitvis AND: hash & (capacity - 1).
Det fungerar endast eftersom de lägsta bitarna i en tvåpotens minus ett bildar en fullständig mask.
#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;
}Varför modulo kan vara långsamt
Operatorn % kompileras till en divisionsinstruktion, som är långsammare än AND. I täta loopar spelar detta roll.
- Tabell med tvåpotensstorlek: använd en AND-mask
- Tabell med primtalsstorlek: använd modulo (ger bättre fördelning för svaga hashfunktioner)
Kollisioner är oundvikliga
Enligt duvslagsprincipen garanterar mappning av många nycklar till färre bucketar att kollisioner uppstår. En bra hashfunktion minimerar dem men kan inte eliminera dem.
I nästa lektion går vi igenom hur kollisioner hanteras.
Demonstration av fördelning
Låt oss räkna hur DJB2 fördelar några nycklar över 8 bucketar. Bra hashfunktioner fördelar dem relativt jämnt.
#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;
}Snabbtest
Testa din förståelse av grunderna i hashfunktioner.
Sammanfattning
Du har lärt dig vad en hashfunktion gör och hur nycklar mappas till bucketar.
- Bra hashfunktioner är deterministiska, snabba och jämnt fördelande
- DJB2 och FNV-1a är bra stränghashfunktioner
- Mappar med
% capacity, eller med& (capacity-1)för tvåpotenser - Använd typer med unsigned; kollisioner går inte att undvika
Lär dig C med en AI-lärare – gratis
Skriv och kör riktig kod i webbläsaren, få omedelbar hjälp av en AI-lärare dygnet runt och fortsätt där du slutade – på webben eller i appen.
- Kurser
- 39
- Lektioner
- 144
Vanliga frågor
Är lektionen ”Hashfunktioner” gratis?
Ja – hela texten till ”Hashfunktioner” kan läsas gratis här på webben. Om Ni vill öva interaktivt med en inbyggd kodredigerare och en AI-handledare som är tillgänglig dygnet runt och låsa upp resten av kursen i C Academy, kan Ni uppgradera till CoddyKit PRO. Kursen i C Academy innehåller totalt 4 lektioner.
Vad lär jag mig i ”Hashfunktioner”?
Mappa nycklar till buckets. Ni övar på C Academy med praktisk kod som körs direkt i webbläsaren, medan en AI-handledare som är tillgänglig dygnet runt svarar på Era frågor under lektionen.
Behöver jag någon erfarenhet för att börja lära mig C Academy?
Du behöver inga förkunskaper. Utbildningen i C Academy på CoddyKit är upplagd för allt från nybörjare till avancerade elever, så att du kan börja här eller från början och gå fram i din egen takt. Detta är lektion 1 av 4.
Hur lång tid tar lektionen ”Hashfunktioner”?
De flesta CoddyKit-lektioner tar cirka 5–10 minuter. Varje lektion är kort och interaktiv, så att du gör stadiga framsteg och kan fortsätta precis där du slutade – på webben eller i appen.
Kan jag skriva och köra kod i den här C Academy-lektionen?
Ja. Varje C Academy-lektion innehåller en inbyggd kodredigerare, så att du kan skriva och köra riktig kod direkt i webbläsaren och få omedelbar AI-feedback – utan lokal installation.