C Academy · Leçon

Fonctions de hachage

Associez des clés à des seaux

Fonctions de hachage est une leçon C Academy gratuite sur CoddyKit. Ceci est la leçon 1 sur 4. Tu peux lire la leçon complète ci-dessous gratuitement — puis la pratiquer en direct dans le navigateur avec un éditeur de code intégré et un tuteur IA 24/7. Elle fait partie du parcours d'apprentissage C Academy, et ta progression se synchronise sur le web et l'application CoddyKit. Le cours C Academy comprend 4 leçons au total.

Qu’est-ce qu’une fonction de hachage

Une fonction de hachage reçoit une clé et produit un index entier dans un tableau de compartiments. Elle constitue le cœur d’une table de hachage, en transformant des clés arbitraires, comme des chaînes de caractères, en positions rapides dans un tableau.

Entrée : une clé (chaîne, entier, etc.)
Sortie : un index de compartiment dans [0, capacity)

Propriétés d’un bon hachage

Une bonne fonction de hachage est déterministe, rapide et répartit les clés uniformément entre les compartiments.

Une même clé produit toujours le même index
De petites modifications de la clé entraînent de grandes modifications de l’index (effet avalanche)
Peu de collisions pour les données courantes

Associer une clé à un compartiment

Une fois la valeur de hachage brute calculée, associez-la à la table à l’aide de l’opérateur modulo : index = hash % capacity.

Utilisez un type unsigned afin que le modulo ne produise jamais un index négatif.

#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 hachage par somme simple

Le hachage de chaînes le plus simple consiste à additionner les valeurs des caractères. Il est facile à mettre en œuvre, mais répartit mal les valeurs, car les anagrammes entrent en collision.

Exécutez-le pour voir deux chaînes différentes produire des valeurs de hachage proches.

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

Le hachage DJB2

DJB2 est une fonction de hachage de chaînes classique et bien répartie, créée par Daniel J. Bernstein. Elle commence à 5381 et utilise hash * 33 + c.

La combinaison multiplication-addition mélange les bits bien mieux qu’une simple somme.

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

Le hachage FNV-1a

FNV-1a applique XOR à chaque octet, puis multiplie le résultat par un nombre premier. Cette méthode est simple, rapide et largement utilisée.

Ordre : XOR d’abord, puis multiplication (c’est 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;
}

Hacher des entiers

Les clés entières doivent elles aussi être mélangées, car x % capacity seul crée des regroupements lorsque les clés partagent des motifs. Un mélange multiplicatif (de Knuth) répartit les 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;
}

Capacités puissances de deux

Lorsque la capacité est une puissance de deux, vous pouvez remplacer % capacity par un ET binaire rapide : hash & (capacity - 1).

Cela fonctionne uniquement parce que les bits de poids faible d’une puissance de deux moins un forment un masque complet.

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

Pourquoi le modulo peut être lent

L’opérateur % est compilé en une instruction de division, plus lente que AND. Dans les boucles serrées, cette différence est importante.

Table dont la taille est une puissance de deux : utilisez un masque AND
Table de taille première : utilisez le modulo (meilleure répartition avec les hachages faibles)

Les collisions sont inévitables

D’après le principe des tiroirs, associer de nombreuses clés à un nombre inférieur de compartiments garantit des collisions. Un bon hachage les réduit, mais ne peut pas les éliminer.

La prochaine leçon explique comment résoudre les collisions.

Démonstration de la répartition

Comptons comment DJB2 répartit quelques clés entre 8 compartiments. Les bons hachages répartissent les valeurs de manière assez 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;
}

Vérification rapide

Vérifiez votre compréhension des bases des fonctions de hachage.

Récapitulatif

Vous avez appris le rôle d’une fonction de hachage et la manière d’associer des clés à des compartiments.

Les bons hachages sont déterministes, rapides et uniformes
DJB2 et FNV-1a sont de solides fonctions de hachage pour les chaînes
Utilisez % capacity, ou & (capacity-1) pour les puissances de deux
Utilisez des types non signés ; les collisions sont inévitables

Questions Fréquemment Posées

La leçon « Fonctions de hachage » est-elle gratuite ?

Oui — le texte complet de « Fonctions de hachage » est gratuit à lire ici sur le web. Pour la pratiquer de manière interactive (un éditeur de code intégré et un tuteur IA 24/7) et déverrouiller le reste du cours C Academy, passe à CoddyKit PRO. Le cours C Academy comprend 4 leçons au total.

Qu'est-ce que j'apprendrai dans « Fonctions de hachage » ?

Associez des clés à des seaux Tu pratiques C Academy avec du code pratique que tu exécutes directement dans le navigateur, et un tuteur IA 24/7 répond à tes questions au fur et à mesure que tu avances dans la leçon.

Dois-je avoir de l'expérience pour commencer C Academy ?

Aucune expérience préalable n'est requise. C Academy sur CoddyKit est structuré pour les débutants jusqu'aux apprenants avancés, donc tu peux commencer ici ou depuis le début et avancer à ton rythme. Ceci est la leçon 1 sur 4.

Combien de temps prend la leçon « Fonctions de hachage » ?

La plupart des leçons CoddyKit prennent environ 5–10 minutes. Chacune est courte et interactive, tu progresses régulièrement et tu repiques exactement où tu t'es arrêté sur le web et l'app.

Peux-tu écrire et exécuter du code dans cette leçon C Academy ?

Oui. Chaque leçon C Academy inclut un éditeur de code intégré, tu écris et exécutes du vrai code directement dans ton navigateur et tu reçois des retours IA instantanés — aucune configuration locale requise.

Toutes les leçons de ce cours

← Retour à C Academy