C Academy · Lezione

Funzioni hash

Associare le chiavi ai bucket

Funzioni hash è una lezione C Academy gratuita su CoddyKit. Questa è la lezione 1 di 4. Puoi leggere la lezione completa qui gratuitamente — poi esercitati direttamente nel browser con un editor di codice integrato e un tutor IA disponibile 24/7. Fa parte del percorso di apprendimento C Academy, e i tuoi progressi si sincronizzano tra il web e l'app CoddyKit. Il corso C Academy include 4 lezioni in totale.

Che cos'è una funzione hash

Una funzione hash riceve una chiave e produce un indice intero in un array di bucket. È il cuore di una tabella hash e trasforma chiavi arbitrarie, come le stringhe, in posizioni rapide dell'array.

Input: una chiave (stringa, intero, ecc.)
Output: un indice di bucket nell'intervallo [0, capacity)

Proprietà di un buon hash

Una buona funzione hash è deterministica, veloce e distribuisce le chiavi in modo uniforme tra i bucket.

La stessa chiave produce sempre lo stesso indice
Piccole variazioni nella chiave causano grandi variazioni nell'indice (effetto valanga)
Un numero ridotto di collisioni con dati tipici

Mappare in un bucket

Dopo aver calcolato un valore hash grezzo, lo mappi nella tabella usando l'operatore modulo: index = hash % capacity.

Utilizzi un tipo unsigned, così il modulo non produrrà mai un indice negativo.

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

Un semplice hash basato sulla somma

Il più semplice hash per stringhe somma i valori dei caratteri. È facile da implementare, ma distribuisce male i valori perché le anagrammi generano collisioni.

Lo esegua per vedere due stringhe diverse produrre valori hash vicini.

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

L'hash DJB2

DJB2 è un classico hash per stringhe, ben distribuito, ideato da Daniel J. Bernstein. Parte da 5381 e usa hash * 33 + c.

La combinazione di moltiplicazione e somma mescola i bit molto meglio di una semplice somma.

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

L'hash FNV-1a

FNV-1a applica XOR a ogni byte e poi moltiplica per un numero primo. È semplice, veloce e ampiamente utilizzato.

Ordine: prima XOR, poi moltiplicazione; questa è la variante 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;
}

Calcolare l'hash degli interi

Anche le chiavi intere richiedono un mescolamento, perché il solo x % capacity crea raggruppamenti quando le chiavi condividono determinati schemi. Un mescolamento moltiplicativo (Knuth) distribuisce i bit.

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

Capacità potenze di due

Quando la capacità è una potenza di due, può sostituire % capacity con un AND bit a bit veloce: hash & (capacity - 1).

Funziona solo perché i bit meno significativi di una potenza di due meno uno formano una maschera completa.

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

Perché il modulo può essere lento

L'operatore % viene compilato in un'istruzione di divisione, più lenta dell'AND. Questo è importante nei cicli stretti.

Tabella con capacità potenza di due: utilizzi una maschera AND
Tabella con dimensione prima: utilizzi il modulo, che garantisce una distribuzione migliore per gli hash deboli

Le collisioni sono inevitabili

Per il principio dei cassetti, mappare molte chiavi in un numero inferiore di bucket garantisce la presenza di collisioni. Un buon hash le riduce, ma non può eliminarle.

La lezione successiva spiega come risolvere le collisioni.

Dimostrazione della distribuzione

Contiamo come DJB2 distribuisce alcune chiavi tra 8 bucket. I buoni hash distribuiscono i valori in modo abbastanza uniforme.

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

Verifica rapida

Verifichi la Sua comprensione delle basi delle funzioni hash.

Riepilogo

Ha appreso cosa fa una funzione hash e come mappare le chiavi nei bucket.

I buoni hash sono deterministici, veloci e uniformi
DJB2 e FNV-1a sono hash solidi per le stringhe
Utilizzi % capacity oppure & (capacity-1) per le potenze di due
Utilizzi tipi unsigned; le collisioni sono inevitabili

Domande Frequenti

La lezione «Funzioni hash» è gratuita?

Sì — il testo completo di «Funzioni hash» è gratuito qui sul web. Per esercitarvi in modo interattivo (un editor di codice integrato e un tutor IA 24/7) e sbloccare il resto del corso C Academy, passa a CoddyKit PRO. Il corso C Academy include 4 lezioni in totale.

Cosa imparerò in «Funzioni hash»?

Associare le chiavi ai bucket Eserciti C Academy con codice pratico che esegui direttamente nel browser, e un tutor IA 24/7 risponde alle tue domande mentre lavori sulla lezione.

Ho bisogno di esperienza per iniziare C Academy?

Non è richiesta alcuna esperienza precedente. C Academy su CoddyKit è strutturato per principianti e studenti avanzati, quindi puoi iniziare da qui o dall'inizio e procedere al tuo ritmo. Questa è la lezione 1 di 4.

Quanto tempo richiede la lezione «Funzioni hash»?

La maggior parte delle lezioni CoddyKit richiede circa 5–10 minuti. Ogni lezione è breve e interattiva, quindi fai progressi costanti e riprendi esattamente da dove hai lasciato su web e app.

Posso scrivere ed eseguire codice in questa lezione C Academy?

Sì. Ogni lezione C Academy include un editor di codice integrato, quindi scrivi ed esegui codice reale direttamente nel tuo browser e ricevi feedback istantaneo dall'IA — nessuna configurazione locale necessaria.

Tutte le lezioni di questo corso

← Torna a C Academy