En informatique, une fonction de hachage est une fonction qui associe, à une donnée de taille non bornée, une donnée de taille fixe. On dit que l'on une donnée.

Les valeurs renvoyées par une fonction de hachage sont appelées condensats, condensés, valeurs de hachage, codes de hachage, signatures ou simplement hachages. Ces valeurs sont parfois utilisés comme indices dans une table de taille fixe, appelée table de hachage, où on retrouvera les attributs stockés pour les éléments .

Des fonctions de hachage sont utilisées dans des applications de stockage et d'indexation et permettent d'accéder rapidement aux attributs de données hétérogènes (de tailles variables et non bornées). De fait, l'accès aux attributs des données se fait en temps quasi-constant. Grâce au hachage, l'espace de stockage est à peine plus grand que l'espace requis pour les attributs des données, mis bout à bout, tout en proposant un accès très rapide. Ainsi, le hachage est un dispositif d'accès aux attributs des données, efficace en termes de calcul et d'espace.

Ce qui rend le hachage vraiment intéressant, ce sont ses excellentes propriétés statistiques. En effet, alors que son comportement dans le pire cas est mauvais, mais ne se manifeste qu'avec une probabilité extrêmement faible, voire négligeable, son comportement moyen est optimal.

Voici une liste de concepts avec lesquels les fonctions de hachage partagent des méthodes, mais avec lesquelles elles ne doivent pas être confondues ; ce sont les sommes de contrôle, les clés de contrôle, la compression avec perte, les générateurs de nombres aléatoires, les codes correcteur et les chiffrements.

Principe général

Une fonction de hachage est typiquement une fonction qui, pour un ensemble de très grande taille (théoriquement infini) et de nature très diversifiée, va renvoyer des résultats aux spécifications précises (en général des chaînes de caractères de taille limitée ou fixe) optimisées pour des applications particulières. Les chaînes permettent d'établir des relations (égalité, égalité probable, non-égalité, ordre...) entre les objets de départ sans accéder directement à ces derniers, en général soit pour des questions d'optimisation (la taille des objets de départ nuit aux performances), soit pour des questions de confidentialité.

Autrement dit : à 1 fichier (ou à 1 mot) va correspondre une signature unique (le résultat de la fonction de hachage).

En termes très concrets, on peut voir une fonction de hachage (non cryptographique) comme un moyen de replier l'espace de données que l'on suppose potentiellement très grand et très peu rempli pour le faire entrer dans la mémoire de l'ordinateur. En revanche, une fonction de hachage cryptographique est ce que l'on appelle une fonction à sens unique, ce qui veut dire que le calcul de la fonction de hachage est facile et rapide tandis que le calcul de sa fonction inverse est infaisable par calcul et donc non calculable en pratique. Grâce à la valeur de hachage, on peut discriminer deux objets apparemment proches, ce qui peut être utilisé pour garantir l'intégrité des objets, autrement dit leur non-modification par une erreur ou un acteur malveillant.

Tables de hachages

vignette|Un annuaire représenté comme une table de hachage. La fonction de hachage transforme les clés (en bleu) en valeurs de hachage (en rouge) indexant les éléments de la table (alvéoles) composés de paires clé–valeur (en vert). Les fonctions de hachage sont utilisées conjointement avec des tables de hachage pour stocker et récupérer des éléments de données ou des enregistrements de données. La fonction de hachage traduit chaque donnée ou enregistrement en un indice dans la table de hachage. Lorsqu'un élément n'est pas encore présent dans la table, l'indice donne accès à un emplacement vide (également appelé compartiment), auquel cas l'élément est ajouté à la table à cet endroit. Si la fonction de hachage produit un indice correspondant à un emplacement déjà occupé, il faut résoudre cette ; le nouvel élément peut être oublié (non ajouté à la table), ou peut remplacer l'ancien élément, ou peut être ajouté à la table à un autre emplacement. Dans ce dernier cas, on utilise une procédure de qui dépend de la structure de la table de hachage. Dans le hachage chaîné, chaque emplacement est la tête d'une liste chaînée, l' élément qui entre en collision est ajouté à la liste chaînée et la recherche dans la liste est linéaire. L'ordre dans la liste chaînée peut être aléatoire ou être un ordre déduit des données, ou être un ordre qui provient de la fréquence des demandes d'accès aux données, afin d'en accélérer l'accès linéaire.

Utilisations spécialisées Les fonctions de hachage sont également utilisées pour créer des caches pour les grands ensembles de données stockés sur des supports lents. Un cache est généralement plus simple qu'une table de recherche hachée car toute collision peut être résolue en supprimant ou en réécrivant le plus ancien des deux éléments en collision.

Les fonctions de hachage sont un ingrédient essentiel du filtre Bloom, une structure de données probabiliste efficace en espace qui est utilisée pour tester si un élément est membre d'un ensemble.

Un cas particulier de hachage est connu sous le nom de hachage géométrique ou méthode de la grille. Dans ces applications, l'ensemble de toutes les entrées est une sorte d' espace métrique, et la fonction de hachage peut être interprétée comme une partition de cet espace dans une grille de cellules. La table est souvent un tableau avec deux indices ou plus (appelés fichier de grille, index de grille, grille de compartiment et noms similaires), et la fonction de hachage renvoie un tuple d'index. Ce principe est largement utilisé en infographie , en géométrie computationnelle et dans de nombreuses autres disciplines, pour résoudre de nombreux problèmes de proximité dans le plan ou dans l'espace tridimensionnel , tels que la recherche de paires les plus proches dans un ensemble de points, de formes similaires dans une liste de formes, d'images similaires dans une base de données d'images , etc.

Les tables de hachage sont également utilisées pour implémenter des tableaux associatifs et des ensembles dynamiques.

Propriétés

Uniformité Une bonne fonction de hachage doit mapper les entrées attendues aussi uniformément que possible sur sa plage de sortie. Autrement dit, chaque valeur de hachage dans la plage de sortie doit être générée avec à peu près la même probabilité . La raison de cette dernière exigence est que le coût des méthodes basées sur le hachage augmente fortement à mesure que le nombre de collisions (paires d'entrées mappées sur la même valeur de hachage) augmente. Si certaines valeurs de hachage sont plus susceptibles de se produire que d'autres, une plus grande partie des opérations de recherche devra rechercher dans un plus grand ensemble d'entrées de table en collision.

Ce critère exige uniquement que la valeur soit uniformément distribuée , et non aléatoire en aucun cas. Une bonne fonction de randomisation est (à moins de problèmes d'efficacité de calcul) généralement un bon choix en tant que fonction de hachage, mais l'inverse n'est pas nécessairement vrai.

Les tables de hachage ne contiennent souvent qu'un petit sous-ensemble des entrées valides. Par exemple, une liste de membres d'un club peut ne contenir qu'une centaine de noms de membres, sur le très grand nombre de noms possibles. Dans ces cas, le critère d'uniformité doit être valable pour presque tous les sous-ensembles typiques d'entrées qui peuvent être trouvées dans le tableau, et pas seulement pour l'ensemble global de toutes les entrées possibles.

En d'autres termes, si un ensemble typique de enregistrements est haché en emplacements de table, la probabilité qu'un seau reçoive beaucoup plus que enregistrements devrait être extrêmement faible. En particulier, si est inférieur à , très peu de compartiments doivent avoir plus d'un ou deux enregistrements. Un petit nombre de collisions est pratiquement inévitable, même si est beaucoup plus grand que – voir le problème de l'anniversaire.

Dans des cas particuliers où les clés sont connues à l'avance et que l'ensemble de clés est statique, une fonction de hachage peut être trouvée qui atteint une uniformité absolue (ou sans collision). Une telle fonction de hachage est dite hachage parfait. Il n'existe aucun moyen algorithmique de construire une telle fonction - la recherche d'une est une fonction factorielle du nombre de clés à mapper par rapport au nombre d'emplacements de table dans lesquels elles sont exploitées. Trouver une fonction de hachage parfaite sur plus d'un très petit ensemble de clés est généralement irréalisable en termes de calcul; la fonction résultante est susceptible d'être plus complexe en termes de calcul qu'une fonction de hachage standard et ne fournit qu'un avantage marginal par rapport à une fonction avec de bonnes propriétés statistiques qui produit un nombre minimum de collisions. Voir la fonction de hachage universelle.

Tests et mesures Lors du test d'une fonction de hachage, l'uniformité de la distribution des valeurs de hachage peut être évaluée par le test du chi deux. Ce test est une mesure de la qualité de l'ajustement : il s'agit de la distribution réelle des éléments dans les compartiments par rapport à la distribution attendue (ou uniforme) des éléments. La formule est :

où: est le nombre de clés, est le nombre de seaux, est le nombre d'articles dans le compartiment . right|vignette|Formule pour l'uniformité de la distribution des valeurs de hachage

Un rapport dans un intervalle de confiance (0,95 - 1,05) indique que la fonction de hachage évaluée a une distribution uniforme attendue.

Les fonctions de hachage peuvent avoir certaines propriétés techniques qui les rendent plus susceptibles d'avoir une distribution uniforme lorsqu'elles sont appliquées. L'un est le critère strict d'avalanche: chaque fois qu'un seul bit d'entrée est complété, chacun des bits de sortie change avec une probabilité de 50 %. La raison de cette propriété est que des sous-ensembles sélectionnés de l'espace de clés peuvent avoir une faible variabilité. Pour que la sortie soit distribuée uniformément, une faible quantité de variabilité, même un bit, doit se traduire par une grande quantité de variabilité (c'est-à-dire une distribution sur l'espace de table) dans la sortie. Chaque bit doit changer avec une probabilité de 50 % car si certains bits hésitent à changer, les clés se regroupent autour de ces valeurs. Si les bits veulent changer trop facilement, le mappage se rapproche d'une fonction XOR fixe d'un seul bit. Des tests standard pour cette propriété ont été décrits dans la littérature.  La pertinence du critère pour une fonction de hachage multiplicative est évaluée ici.

Efficacité Dans les applications de stockage et de récupération de données, l'utilisation d'une fonction de hachage est un compromis entre le temps de recherche et l'espace de stockage des données. Si le temps de recherche était illimité, une liste linéaire non ordonnée très compacte serait le meilleur moyen ; si l'espace de stockage était illimité, une structure accessible de manière aléatoire et indexable par la valeur-clé serait très grande, très clairsemée, mais très rapide. Une fonction de hachage prend un temps fini pour mapper un espace de clés potentiellement grand à une quantité réalisable d'espace de stockage interrogeable dans un laps de temps limité, quel que soit le nombre de clés. Dans la plupart des applications, la fonction de hachage doit être calculable avec un minimum de latence et accessoirement en un minimum d'instructions.

La complexité de calcul varie en fonction du nombre d'instructions requises et de la latence des instructions individuelles, les plus simples étant les méthodes au niveau du bit (pliage), suivies des méthodes multiplicatives, et les plus complexes (les plus lentes) sont les méthodes basées sur la division.