Fonctions de hachage

Publié le 12 Jan 2017 dans Algorithmique.

Avec nos langages modernes qui fournissent dictionnaires et tableaux associatifs nativement, il devient rare d'avoir à implémenter une table de hachage à la main. Cela arrive néanmoins, par exemple quand on doit développer en C/C++, qu'on ne peut pas embarquer Boost et qu'on est comme moi allergique à stdlib. Se pose alors la question de trouver une bonne fonction de hachage.

Qu'est-ce qu'un bon hachage ? C'est d'abord une fonction performante, parce qu'elle sera probablement appelée des milliers de fois durant la vie de l'application. Mais c'est aussi une fonction qui provoquera peu de collisions. Tout l'intérêt d'une table de hachage est de fournir l'insertion et la recherche en O(1), or s'il se produit beaucoup de collisions, les performances vont tendre vers O(n), soit pas mieux qu'une simple liste chaînée. Notre fonction doit donc produire des valeurs raisonnablement bien distribuées pour un échantillon représentatif des chaines qui seront insérées dans la table.

Je possède un vieux bouquin d'architecture des systèmes où l'auteur explique avoir testé les fonctions de hachage les plus répandues à l'époque sur des ensembles de chaînes de caractères, notamment l'ensemble des mots de la langue anglaise, et un ensemble d'une dizaine de milliers de noms de variables prélevés dans un échantillon de programmes FORTRAN. (Oui, je vous ai dit, c'est un vieux bouquin !) La fonction qui produisit le moins de collisions fut la suivante :

uint32_t hash(char const * text) {
    uint32_t h = 0, g;
    for (char const * p = text; *p; p++) {
        h = (h << 4) + (uint32_t) (unsigned char) *p;
        if ((g = h & 0xF0000000) != 0) {
            h ^= (g >> 24);
             h ^= g;
        }
    }
    return h;
}

Fort de cette information, j'ai donc copié/collé cette fonction partout où j'avais besoin d'une fonction de hachage pendant des années. J'en ai produit des implémentations archi-optimisées pour x86, ARM et Motorola 68000, je l'ai adaptée quand se sont répandus les systèmes Unicode…

Et puis un jour, au détour d'une recherche Google, je suis tombé sur la fonction suivante :

uint32_t hash(char const * text) {
    uint32_t h = 5381;
    for (char const * p = text; *p; p++) {
        h = ((h << 5) + h) ^ (uint32_t) (unsigned char) *p;
    }
    return h;
}

Elle est à la fois plus simple et plus performante, et un rapide test m'a montré qu'elle produisait des valeurs aussi bien distribuées que la fonction précédente. C'est donc celle-ci que j'utilise désormais partout. Pas plus tard qu'il y a quelques jours, j'ai encore pu constater la très bonne répartition qu'elle permet : en déboguant le compilateur sur lequel je travaille actuellement, j'ai vu une table de symboles pleine à 90 % et dans laquelle il n'y avait que deux collisions !

Quelques remarques pour finir. Ces fonctions retournent une valeur comprise entre 0 et 2^32-1. Pour indexer une table de taille N, il suffira de calculer le haché modulo N, ce qui fournira une valeur entre 0 et N-1. Les meilleurs résultats sont obtenus lorsque N est un nombre premier. Enfin, il est évident (mais ça va mieux en le disant…) que ces fonctions ne sont pas cryptographiques. Pour un hachage destiné à sécuriser un mot de passe, par exemple, on se tournera plutôt vers bcrypt.