Comment pouvons nous s'assurer que notre fonction de hash est une bonne fonction de hash ? Comment devons-nous choisir une fonction de hash ? Pour choisir une fonction de hash (non cryptographique) nous avons besoin de relativement peu de choses: l'établissement d'un corpus de clefs et quelques tests statistiques pour s'assurer que la fonction performe raisonnablement bien.

• Établissement d'un corpus représentatif. Il faut commencer par construire un corpus de clefs qui représentera bien les clefs qui seront générées par votre application. Si vous pouvez générer les clefs de façon exhaustive en les énumérant, tant mieux. Si votre ensemble de clefs est très grand (voire infini), générez en un grand nombre — un grand nombre, ça ne veut pas dire 100 ou 1000, ça veut dire 10⁶ et plus — pour rendre vos test statistiquement significatifs.

  L'établissement d'un corpus significatif n'est pas nécessairement une tâche facile. Il pourrait s'agir d'échantillonner des données d'une base de données existante (comme un dictionnaire de mots français, ou anglais, ou d'identifieurs tirés d'un grand nombre de programmes source) qui correspondent le mieux possible à notre application projetée.

• Applications de tests statistiques rigoureux. Pour s'assurer que la fonction de hash retourne des valeurs uniformément distribuées sur 0...2ⁿ-1 (ou mod m), nous utiliserons des tests statistiques connus. En particulier, les tests sur la variance et les tests de type goodness of fit qui nous permettront de déterminer si la séquence des valeurs hashées se comporte comme une variable aléatoire uniforme.

• Tests de vitesse. Il faut aussi s'assurer de choisir une fonction qui est raisonnablement rapide. Il faut donc minimiser la complexité algorithmique de la fonction et aussi avoir une implémentation efficace. Ultimement, c'est le chronomètre à la main que nous déciderons si une fonction de hash est rapide ou non.

Pour établir un corpus, il faut d'abord considérer les clefs qui nous intéressent. Même si on teste une fonction de hash universelle qui, en principe, devrait performer également indépendamment de la nature des clefs, tester avec les clefs qui nous intéressent pourrait exposer une faiblesse de la fonction.

La méthodologie peut varier. Dans le cas de clefs « naturelles » il faudra échantillonner des données existantes ou s'assurer d'en créer de vraisemblables. S'il s'agit d'une application basée sur la langue naturelle, il pourrait être raisonnable d'utiliser un corpus comme le Project Gutenberg pour extraire un grand nombre de mots ou de phrases. Le Project Gutenberg a mis à la disposition de tous un grand nombre de textes, en diverses langues et avec des encodages divers (ascii, utf-8, etc.) S'il s'agit d'une base de données basée sur les ISBN (international standard book numbers), il est possible de procéder exhaustivement et d'énumérer tous les ISBN valides; il n'y en a pas tant que cela — beaucoup moins que 10¹⁰. Il est donc tout à fait possible de tous les générer. S'il s'agit plutôt d'un programme qui joue aux échecs, les clefs seront des positions (valides, atteignables depuis la position initiale en suivant les règles.) Il y en a cependant beaucoup trop: on en estime le nombre à moins de 10⁴⁶! Il faudra alors générer un certain nombre de positions aléatoires.

Pour les tests, j'ai généré plusieurs sources de clefs. Nous avons une série de mots français, une série de mots anglais, une liste de tous les ISBNs, une série de lignes de texte prises au hasard dans le corpus du projet Gutenberg et pour finir, une liste de position de jeu d'échecs en notation FEN tirée d'une très grosse base de données de parties de tournois.

De la façon dont est écrit le programme de test, il est facile d'ajouter une classe descendant de la classe cDataSource pour créer un nouveau générateur de clefs. Vous pourrez donc facilement tester vos propres données.

♦ Tests statistiques

Pour déterminer si une fonction de hash est bonne, il suffit, en gros, de vérifier si la séquence de nombres générés par la fonction se comporte comme comme un générateur de nombres pseudo-aléatoires uniforme sur 0...m-1, où m n'est pas nécessairement de la forme 2ⁿ-1. En fait, m, c'est la taille de la table. Comme m est vraisemblablement variable, il faudrait tester pour plusieurs m dont certains judicieusement choisis (nous y reviendrons.)

Le test le plus simple, c'est le test de la variance. Nous créons un tableau T de m compteurs initialement à zéro. Pour chaque clef k_i nous calculons

et nous incrémentons T [ h_i ]. Plus la distribution est uniforme, plus les comptes du tableau T sont égaux. Une façon de mesurer leur uniformité, du moins pour comparer entre les fonctions de hash, c'est d'utiliser la variance de T. Si une fonction donne une variance moindre qu'une autre, c'est qu'elle distribue mieux les clefs (mod m) que l'autre. Rappelons que la variance est donnée par

où E[ X ] est l'espérance de la variable aléatoire X.

Quels sont les m qui seront particulièrement intéressants ? Sûrement des puissances de 10 qui nous paraissent intuitives. Définitivement des puissances de deux qui, outre de nous paraître tout aussi intuitives, pourraient exposer les faiblesses d'une fonction de hash basée sur les manipulation de bits. On peut aussi utiliser un m qui est un nombre composite pour mettre en évidence les éventuelles faiblesses d'une fonction basée sur les produits. Le choix m = 30030 peut être intéressant parce que m = 2 × 3 × 5 × 7 × 11 × 13, soit le produit des quelques premiers nombres premiers. Asymptotiquement, m a un facteur commun avec approximativement 80.8% des nombres.

♦ Résultats

J'ai voulu comparer les fonctions de hash sur des sources vraisemblables dans la mesure où il n'est pas impossible que vous ayez à les utiliser (ou de très semblables) vous même. J'ai donc appliqué toutes les fonctions de hash que nous avons vu sur plusieurs sources. Examinons les résultats. Commençons par examiner les résultats sur une liste de mots français, francais.dix.

On voit, par le tableau précédent, que la plupart des fonctions — sauf les fonctions additive et multiplicative — performent non seulement raisonnablement bien, mais aussi qu'il n'y a pas de très grande différence entre la fonction de Zobrist et la fonction Adler32. Les quatre premières, en vert, donnent des résultats tout à fait comparables. En jaune, on trouve des fonctions encore bonnes, mais qui font quand même moins bien. En rouge, les fonctions vraiment mauvaises.

Qu'est-ce qui différencie les fonctions « acceptables » des vraiment mauvaises ? Si on se fit à la variance seule, la différence est énorme, même à l'œil. En fait, une variance très élevée met en évidence un défaut de la fonction de hash. Ça pourrait être qu'elle ne génère que des valeurs petites (comme la fonction de hash additive), ou qu'elle génère une valeur en particulier bien trop souvent (comme 0 pour la fonction multiplicative). Cela pourrait être aussi que la fonction génère que des valeurs hashées qui sont des multiples de, disons, 3. En fait, une fonction ne donnera une bonne variance que si elle distribue très uniformément les clefs sur les cases du tableau.

Si on cherche la meilleure fonction pour une source, il suffit de prendre le temps de les comparer. Le prochain tableau montre les meilleures fonctions pour une source et une taille de tableau. La meilleure fonction est tout simplement celle qui a la moindre variance pour une source et un m donné.

On voit que ce n'est pas systématiquement les mêmes fonctions qui sont choisies pour une source donnée; le choix dépend de m. Cependant, si on examine tous les résultats, on voit qu'il y a quand même un groupe de fonction qui donnent approximativement la même qualité de hashage pour une source et pour un m donnés.

Alors, s'il est impossible de choisir la fonction de hash pour une source (nous venons de voir que les performances varient légèrement selon le m), comment devons nous procéder ?

Une bonne fonction de hash est avant tout universelle, c'est-à-dire qu'elle performe bien sur la plupart des sources. Il suffit d'en prendre une qui est dans le peloton de tête, peut-être en considérant le temps de calcul.

Les différentes fonctions de hash ne prennent pas toutes le même temps de calcul pour la même clef; certaines sont très simples d'autres plus complexes. Toutes les fonctions de hash que nous avons présenté sont O( |k| ), où |k| est la longueur de la clef k.

Si nous regardons les fonctions, nous voyons que certaines sont très rapides et ne se basent que sur des opérations primitives (addition, décalages >> et <<, ou-exclusif, etc.) tandis que d'autres dépendent d'opérations généralement coûteuses comme la multiplication et le modulo. Mais qu'en est-il vraiment?

• Additif. N'utilise que l'addition. Est par ailleurs assez mauvaise.

• Multiplicatif. N'utilise que la multiplication qui est typiquement (mais dépendamment du processeur) de 2 à 10 fois plus lente que l'addition simple. Cette fonction est catastrophiquement mauvaise.

• Knuth. Introduit l'utilisation des décalages (>> et <<) et l'addition. Les décalages sont souvent des opérations élémentaires (ayant le même coût que l'addition) mais il peut arriver que sur un processeur donné ils soient très lents. Sur certain processeurs, les décalages autres que par 1 ou 2 sont émulés en logiciel par une boucle, ou en microcode. Le coût de l'opération dépend alors du nombre de décalages. Il est généralement admis que les décalages sont des opérations élémentaires de faible coût; ce n'est pas nécessairement le cas.

• Bricolage. Cette fonction utilise les décalages et l'addition, comme la fonction de Knuth mais introduit un tableau supplémentaire. Ce tableau permet la randomisation des clefs. L'accès à un petit tableau de taille connue (et dont la taille des éléments est une puissance de deux) est généralement de coût assez faible, pour peu que ce tableau se trouve dans la cache.

• Congruentiel. Cette fonction n'utilise que la multiplication comme opération coûteuse. L'addition est comparativement peu dipensieuse.

• Exponentiation modulaire. Cette fonction est coûteuse. Elle utilise la multiplication, le modulo (implicitement, la division) et les décalages. De plus, elle contient aussi un branchement conditionnel et des boucles imbriquées.

• Modulo. Cette fonction simule le calcul du modulo sur la clef considérée comme un grand entier. Une partie de la complexité est déplacée dans le précalcul d'un tableau. L'algorithme s'en trouve grandement simplifié et ne dépend plus que d'un accès au tableau, de décalages, et du ou-exclusif. Cette méthode est généralement utilisée pour implémenter les CRCs de façon efficace.

• Zobrist. Cette fonction utilise un tableau en deux dimension pour randomiser les résultats. Elle utilise le ou-exclusif et le et binaire, deux opérations élémentaires. Les accès à un tableau à deux dimensions sont plus coûteuses qu'à un tableau à une seule dimension, mais pas significativement.

• Adler32. Si on omet la correction pour les clefs très longues (plus de 5552 octets), la fonction se réduit à deux additions dans la boucle principale. En sortie, on a une manipulation qui utilise un décalage et un ou binaire.

Et si nous les comparions avec le chronomètre à la main? D'abord, il faut éliminer le temps d'acquisition/génération des clefs. Il faut donc ne chronométrer que les fonctions de hash elles-mêmes. Les fonctions habituelles (time, clock, etc.) ne sont pas très précises. La fonction clock, par exemple, a une très mauvaise granularité: environ 10 ms sur Windows. J'utilise une fonction de mon cru basée sur le time stamp counter du processeur. Ce compteur a la particularité de s'incrémenter au même rythme que l'horloge du processeur. C'est-à-dire que sur un processeur à 1GHz, il s'incrémente de 1 milliard par seconde, donnant, à toute fin pratique, un chronomètre précis à la nanoseconde.

Pour les tests, j'ai généré à l'avance des clefs aléatoires de différentes longueurs (5, 10, 100 et 1000 bytes de long.) Comme les clefs plus longues amortissent la contribution de la partie de la fonction qui ne se trouve pas dans la boucle (qui n'est généralement composée que de l'appel de fonction lui-même et de l'initialisation de quelques petites variables), j'ai retenu les résultats pour les clefs de longueur 1000.

Pour les tests, j'ai utilisé mon CPU Athlon XP 2300 à 1.667 GHz. J'ai aussi utilisé les optimisations maximales du compilateur pour obtenir le code le plus efficace possible. Les résultats sont donnés en nanosecondes (ns) par byte. Ces résultats variront d'un processeur à l'autre.

Si on omet les fonctions vraiment mauvaises (additive et multiplicative, en l'occurence) on se retrouve avec les fonctions Adler32 et Knuth qui prennent essentiellement le même temps. On sait que la fonction de Knuth n'est pas la meilleure, et que la fonction de Adler se retrouve assez loin, côté qualité de la valeur hashée. La fonction d'exponentiation modulaire est tellement lente par rapport aux autres qu'on ne peut pas vraiment la retenir. Cela nous laisse avec les fonctions bricolage et de Zobrist.

Une autre façon d'estimer la performance (en temps d'exécution) d'une fonction de hash, c'est de regarder le code assembleur généré par le compilateur. Sur Visual C++ on utilisera l'option /FAsc (qui génère le code ci-bas) et sur gcc/g++, on utilisera l'option -S. Cette approche peut vous montrer où passe le temps dans la fonction de hash, au niveau des instructions et où optimiser pour aller chercher quelques cycles par-ci, par-là. Ici, on notera que Visual C++ 6.0 ne connaît pas les instructions movzx/movsx.

   
   ; HashBricolage

   ; 16   :   for (int i=0; i<size; i++)

   00001 8b 74 24 0c      mov  esi, size
   00005 33 c0            xor  eax, eax
   00007 33 c9            xor  ecx, ecx
   00009 85 f6            test esi, esi
   0000b 7e 21            jle  SHORT $L225
   0000d 53               push ebx
   0000e 57               push edi
   0000f 8b 7c 24 10      mov  edi, buffer

   $L223:

   ; 17   :     h = (h ^ (h >> 1) ) 
   ; 18   :          +EXPAND[ buffer[i] ];

   00013 33 d2           xor edx, edx
   00015 8a 14 39        mov dl, BYTE PTR [ecx+edi]

   00018 8b d8           mov ebx, eax
   0001a d1 eb           shr ebx, 1
   0001c 33 d8           xor ebx, eax
   0001e 8b 04 95 00 00
         00 00           mov eax, EXPAND
   00025 03 c3           add eax, ebx
   00027 41              inc ecx
   00028 3b ce           cmp ecx, esi
   0002a 7c e7           jl  SHORT $L223
   0002c 5f              pop edi
   0002d 5b              pop ebx

   $L225:

   0002e 5e              pop esi

   ; 21   :   return h;
   ; 22   :  }

   0002f c3              ret 0