Un algorithme de hachage (ou fonction de hachage) transforme des données d'entrée de longueur arbitraire en une chaîne de bits de taille fixe, appelée empreinte ou condensé. Il s'agit d'une fonction non injective qui sert notamment dans les tables de hachage, la vérification d'intégrité et le partitionnement distribué. Voici les grandes familles de fonctions de hachage, avec leurs avantages et cas d'usage.

Hachage par addition

Cette méthode somme tous les octets (ou caractères) de la clé pour produire le haché. Simple et rapide, mais sensible aux collisions si la distribution n'est pas uniforme.

static int additiveHash(String key, int prime) {
    int hash = key.length();
    for (int i = 0; i < key.length(); i++) {
        hash += key.charAt(i);
    }
    return hash % prime;
}

Hachage par opérations bit à bit

Utilise des rotations, décalages et OU exclusif pour mélanger les bits. Plus robuste que l'addition simple. Exemple : rotation et XOR.

static int rotatingHash(String key, int prime) {
    int hash = key.length();
    for (int i = 0; i < key.length(); i++) {
        hash = (hash << 4) ^ (hash >> 28) ^ key.charAt(i);
    }
    return hash % prime;
}

Hachage par multiplication

Exploite la non‑corrélation des multiplications. Utilisé par String.hashCode() en Java (facteur 31). Exemple classique : Bernstein.

static int bernsteinHash(String key) {
    int hash = 0;
    for (int i = 0; i < key.length(); i++) {
        hash = 33 * hash + key.charAt(i);
    }
    return hash;
}

Variante FNV (32 bits)

static int fnvBasic(byte[] data) {
    int hash = (int) 2166136261L;
    for (byte b : data) {
        hash = (hash * 16777619) ^ b;
    }
    return hash;
}

FNV amélioré

static int fnvEnhanced(String data) {
    int hash = (int) 2166136261L;
    for (int i = 0; i < data.length(); i++) {
        hash = (hash ^ data.charAt(i)) * 16777619;
    }
    hash += hash << 13;
    hash ^= hash >> 7;
    hash += hash << 3;
    hash ^= hash >> 17;
    hash += hash << 5;
    return hash;
}

RS Hash (multiplication par une constante variable)

static int rsHash(String str) {
    int a = 63689;
    int b = 378551;
    int hash = 0;
    for (int i = 0; i < str.length(); i++) {
        hash = hash * a + str.charAt(i);
        a *= b;
    }
    return hash & 0x7FFFFFFF;
}

Hachage par division

L'opération modulo est lente, donc rarement utilisée en pratique. Son intérêt théorique est analogue à la multiplication.

Hachage par table de correspondance

Le CRC (Cyclic Redundancy Check) en est l'exemple le plus connu. D'autres comme Universal Hashing et Zobrist Hashing utilisent des tables aléatoires générées une fois.

Hachage mixte

Combine plusieurs techniques (addition, décalage, XOR). Les algorithmes de chiffrement comme MD5, SHA1 ou Tiger entrent dans cette catégorie.

Hachage de tableau d'entiers

static int arrayHash(int[] v, int k, int M) {
    int hash = 0;
    for (int i = 0; i < k; i++) {
        hash = ((hash << 2) + (v[i] >> 4)) ^ (v[i] << 10);
    }
    hash %= M;
    return (hash < 0) ? hash + M : hash;
}

Utilisé dans les fonctions de hachage orientées recherche (ex : tables de hachage d'index).

Hachage en anneau (consistent hashing)

Le hachage cohérent (ou consistent hashing) est utilisé dans les systèmes distribués (caches, bases de données) pour répartir les données sans tout re‑hacher lors de l'ajout ou du retrait d'un nœud. Principe :

1. Chaque nœud (serveur) est haché et placé sur un cercle de 0 à 232.
2. Chaque clé est hachée et projetée sur le même cercle.
3. La clé est attribuée au premier nœud rencontré en parcourant le cercle dans le sens horaire ; si aucun nœud n'est trouvé avant la fin, elle va au premier nœud.

Problème : déséquilibre (data skew)

Avec peu de nœuds, ceux‑ci peuvent être regroupés sur une petite portion du cercle, concentrant la charge sur quelques machines.

Solution : nœuds virtuels

Chaque nœud physique se voit attribuer plusieurs positions virtuelles sur le cercle (par exemple en hachant son IP avec différents suffixes). Cela homogénéise la distribution des données.