Qu'est-ce qu'une bonne fonction de hash ? Quelles sont les propriétés souhaitables pour une fonction de hash ?

• Elle doit être simple à calculer. Quand nous disons simple à calculer, nous parlons d'un faible coût de calcul, et non de la simplicité conceptuelle de la fonction. La rapidité de la fonction de hash est primordiale. D'autres algorithmes, comme les arbres de recherche, par exemple, auront une complexité O(m lg n) où m est le coût moyen pour la comparaison des clefs et n le nombre de clefs dans l'arbre. La fonction de hash doit avoir un temps de calcul significativement inférieur à O(m lg n) pour que cela soit rentable d'utiliser une table de hash plutôt qu'un arbre.

• Elle doit être indépendante de la longueur de la clef. La valeur retournée par l'algorithme ne doit pas dépendre de la longueur de la clef. Les clefs courtes ne reçoivent pas de plus petites valeurs que les clefs plus longues. Chaque clef doit recevoir une valeur apparemment aléatoire. Cette contrainte empêchera l'algorithme de générer des valeurs débiles pour les clefs courtes.

• Elle doit être indépendante du type de la clef. Certaines fonctions de hash peuvent être conçues pour un type particulier de clef. Par exemple, du texte, des pixels ou encore des clefs très structurées et prévisibles comme des numéros de plaques de voitures. On peut concevoir une fonction très efficace en exploitant une astuce pour un type de clef, mais cette fonction ne sera pas très bonne pour un autre type de clef, si même elle peut s'appliquer. Une fonction de hash sera universelle si la qualité des valeurs générées ne dépend pas du type (ni de la longueur) des clefs.

• Elle doit paraître pseudo-aléatoire. Il faut que les valeurs retournées par la fonction de hash soient faiblement correlées entre elles. Deux clefs qui se suivent lexicographiquement (comme « aaaaa » et « aaaab ») ne doivent pas recevoir deux valeurs qui se suivent; ces deux valeurs devraient être aussi indépendantes que possible (au sens statistique.)

Une fonction de hash qui satisfait toutes ces exigences sera dite idéale, à ne pas confondre avec parfaite, qui a une toute autre signification (nous y revenons dans un instant.)

Quelles sont donc les pièces constitutives d'une bonne fonction de hash ? Si on regarde la fig. 1. ci-bas, on trouve trois boîtes principales. On a la graine (l'état interne, le seed) une quantité d'information qui maintient la valeur de hash (et autres données nécessaires à son calcul.) Nous trouvons une étape de combinaison où les nouvelles valeurs, typiquement le prochain byte de la clef, sont combinées à l'état interne. Enfin, nous avons une étape de diffusion qui randomise l'état interne de la fonction de hash. La graine, ou une partie de, sera la valeur hashée des données.

Fig. 1. Un diagramme simplifié pour une fonction de hash.

C'est un modèle grandement simplifié mais général dans la mesure où chaque « boîte » peut contenir un nombre arbitraire de sous-boîtes. L'état interne, la graine, peut comporter beaucoup plus de bit que la valeur finale; comme l'étape de combinaison peut être elle-même composée de plusieurs strates où, par exemple, le byte est converti à une valeur 32 bits avant d'être combiné à la graine. Enfin, pour bien brouiller les bits, l'étape de diffusion peut employer plusieurs mécanismes pseudo-aléatoires.

Il serait simpliste de penser que la fig. 1. donne la grammaire complète des fonctions de hash. Cependant, nous verrons que les fonctions de hash que nous présenterons suivent quand même assez fidèlement ce schéma.

Qu'est-ce qu'une fonction de hash parfaite ? Une fonction de hash parfaite est une fonction de hash qui garantit que chaque clef reçoit une valeur hashée différente. Une fonction qui n'est qu'idéale ne garantit pas cela.

Garantir une valeur différente pour chaque clef peut être problématique. Si on a un relativement petit espace de clefs (disons, quelques centaines ou quelques milliers tout au plus) on peut contruire en mémoire les tables qui sont nécessaires au calcul de la valeur unique, mais la situation se complique si le nombre de clefs distinctes est très grand, voire infini.

On peut toutefois créer incrémentalement ces tables, mais le gain par rapport à un algorithme plus conventionnel (comme un arbre de recherche binaire) devient moins évident. Nous ne présenterons pas, du moins dans cette version du tutoriel, de fonctions de hash parfaite ni d'algorithme pour en construire une.