Fonction de hachage

Une fonction de hachage est une fonction qui peut être utilisée pour mapper des données de taille arbitraire à des valeurs de taille fixe, bien qu'il existe certaines fonctions de hachage qui prennent en charge une sortie de longueur variable. Les valeurs renvoyées par une fonction de hachage sont appelées valeurs de hachage , codes de hachage , résumés de hachage , résumés ou simplement hachages . Les valeurs sont généralement utilisées pour indexer une table de taille fixe appelée table de hachage . L'utilisation d'une fonction de hachage pour indexer une table de hachage est appelée hachage ou adressage de stockage dispersé .

Les fonctions de hachage et les tables de hachage associées sont utilisées dans les applications de stockage et de récupération de données pour accéder aux données dans un temps court et presque constant par récupération. Elles nécessitent une quantité d'espace de stockage à peine supérieure à l'espace total requis pour les données ou les enregistrements eux-mêmes. Le hachage est une forme d'accès aux données efficace en termes de calcul et d'espace de stockage qui évite le temps d'accès non constant des listes ordonnées et non ordonnées et des arbres structurés, ainsi que les exigences de stockage souvent exponentielles de l'accès direct aux espaces d'état de clés de grande taille ou de longueur variable.

L'utilisation des fonctions de hachage repose sur les propriétés statistiques de l'interaction clé-fonction : le comportement du pire des cas est intolérablement mauvais mais rare, et le comportement du cas moyen peut être presque optimal ( collision minimale ).

Les fonctions de hachage sont liées aux sommes de contrôle , aux chiffres de contrôle , aux empreintes digitales , à la compression avec perte , aux fonctions de randomisation , aux codes correcteurs d'erreurs et aux chiffrements (et sont souvent confondues avec ces derniers) . Bien que les concepts se chevauchent dans une certaine mesure, chacun a ses propres utilisations et exigences et est conçu et optimisé différemment. La fonction de hachage diffère de ces concepts principalement en termes d' intégrité des données . Les tables de hachage peuvent utiliser des fonctions de hachage non cryptographiques , tandis que les fonctions de hachage cryptographiques sont utilisées en cybersécurité pour sécuriser les données sensibles telles que les mots de passe.

Dans une table de hachage, une fonction de hachage prend une clé comme entrée, qui est associée à une donnée ou à un enregistrement et utilisée pour l'identifier auprès de l'application de stockage et de récupération de données. Les clés peuvent être de longueur fixe, comme un entier, ou de longueur variable, comme un nom. Dans certains cas, la clé est la donnée elle-même. La sortie est un code de hachage utilisé pour indexer une table de hachage contenant les données ou les enregistrements, ou des pointeurs vers ceux-ci.

On peut considérer qu'une fonction de hachage remplit trois fonctions :

• Convertissez des clés de longueur variable en valeurs de longueur fixe (généralement de longueur de mot machine ou moins), en les pliant par mots ou autres unités à l'aide d'un opérateur préservant la parité comme ADD ou XOR,
• Brouiller les bits de la clé afin que les valeurs résultantes soient uniformément réparties sur l' espace de clés , et
• Mappez les valeurs clés en valeurs inférieures ou égales à la taille de la table.

Une bonne fonction de hachage satisfait deux propriétés de base : elle doit être très rapide à calculer et elle doit minimiser la duplication des valeurs de sortie ( collisions ). Les fonctions de hachage reposent sur la génération de distributions de probabilité favorables pour leur efficacité, réduisant le temps d'accès à presque constant. Des facteurs de chargement de table élevés, des ensembles de clés pathologiques et des fonctions de hachage mal conçues peuvent entraîner des temps d'accès proches de la linéarité du nombre d'éléments dans la table. Les fonctions de hachage peuvent être conçues pour offrir les meilleures performances dans le pire des cas, de bonnes performances sous des facteurs de chargement de table élevés et, dans des cas particuliers, un mappage parfait (sans collision) des clés dans les codes de hachage. L'implémentation est basée sur des opérations de bits préservant la parité (XOR et ADD), la multiplication ou la division. Un complément nécessaire à la fonction de hachage est une méthode de résolution de collision qui utilise une structure de données auxiliaire comme des listes chaînées ou un sondage systématique de la table pour trouver un emplacement vide.

Les fonctions de hachage sont utilisées conjointement avec les 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 la clé associée à chaque donnée ou enregistrement en un code de hachage, qui est utilisé pour indexer la table de hachage. Lorsqu'un élément doit être ajouté à la table, le code de hachage peut indexer un emplacement vide (également appelé bucket), auquel cas l'élément est ajouté à la table à cet emplacement. Si le code de hachage indexe un emplacement plein, une sorte de résolution de collision est alors nécessaire : le nouvel élément peut être omis (non ajouté à la table), ou remplacer l'ancien élément, ou être ajouté à la table à un autre emplacement par une procédure spécifiée. Cette procédure 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 ou d'une chaîne, et les éléments qui entrent en collision au niveau de l'emplacement sont ajoutés à la chaîne. Les chaînes peuvent être conservées dans un ordre aléatoire et recherchées de manière linéaire, ou dans un ordre sériel, ou sous forme de liste auto-ordonnée par fréquence pour accélérer l'accès. Dans le hachage d'adresse ouverte , la table est sondée à partir de l'emplacement occupé d'une manière spécifiée, généralement par sondage linéaire , sondage quadratique ou double hachage jusqu'à ce qu'un emplacement ouvert soit localisé ou que la table entière soit sondée (dépassement de capacité). La recherche de l'élément suit la même procédure jusqu'à ce que l'élément soit localisé, qu'un emplacement ouvert soit trouvé ou que la table entière ait été recherchée (élément non présent dans la table).

Les fonctions de hachage sont également utilisées pour créer des caches pour de 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 conflit.

Les fonctions de hachage sont un ingrédient essentiel du filtre Bloom , une structure de données probabiliste peu encombrante 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 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 en 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 compartiments 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 , comme la recherche des 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 .

Une bonne fonction de hachage doit mapper les entrées attendues de manière aussi uniforme 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 considérablement à 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 fraction des opérations de recherche devra rechercher dans un plus grand ensemble d'entrées de table en collision.

Ce critère exige seulement que la valeur soit distribuée uniformément et non aléatoire dans aucun sens. Une bonne fonction de randomisation est (sauf problèmes d'efficacité de calcul) généralement un bon choix comme fonction de hachage, mais l'inverse n'est pas forcément 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, parmi le très grand ensemble de tous les 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és dans la table, et pas seulement pour l'ensemble global de toutes les entrées possibles.

En d'autres termes, si un ensemble typique de m enregistrements est haché dans n emplacements de table, alors la probabilité qu'un bucket reçoive beaucoup plus que m / n enregistrements devrait être infinitésimale. En particulier, si m < n , alors très peu de buckets devraient avoir plus d'un ou deux enregistrements. Un petit nombre de collisions est pratiquement inévitable, même si n est beaucoup plus grand que m — voir le problème des anniversaires .

Dans des cas particuliers où les clés sont connues à l'avance et 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 parfaite . Il n'existe aucun moyen algorithmique de construire une telle fonction : la recherche d'une fonction est une fonction factorielle du nombre de clés à mapper par rapport au nombre d'emplacements de table dans lesquels elles sont mappées. Trouver une fonction de hachage parfaite sur plus d'un très petit ensemble de clés est généralement impossible sur le plan informatique ; la fonction résultante est susceptible d'être plus complexe sur le plan informatique qu'une fonction de hachage standard et n'offre qu'un avantage marginal par rapport à une fonction avec de bonnes propriétés statistiques qui produit un nombre minimum de collisions. Voir fonction de hachage universelle .

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 carré . Ce test est une mesure de l'adéquation : 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ù n est le nombre de clés, m est le nombre de buckets et b _j est le nombre d'éléments dans le bucket j .

Un ratio dans un intervalle de confiance (par exemple 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 augmentent la probabilité qu'elles aient une distribution uniforme lorsqu'elles sont appliquées. L'une d'elles est le critère d'avalanche strict : 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 uniformément distribuée, 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 sont réticents à changer, les clés se regroupent autour de ces valeurs. Si les bits veulent changer trop facilement, alors 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.

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 n'était pas limité, une liste linéaire non ordonnée très compacte serait le meilleur support ; si l'espace de stockage n'était pas limité, une structure accessible de manière aléatoire indexable par la clé-valeur serait très grande et très clairsemée, mais très rapide. Une fonction de hachage prend un temps fini pour mapper un espace de clés potentiellement important à une quantité réalisable d'espace de stockage consultable 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 une latence minimale et secondairement dans un nombre minimal 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 (repliement), suivies des méthodes multiplicatives, et les plus complexes (les plus lentes) sont les méthodes basées sur la division.

Étant donné que les collisions devraient être peu fréquentes et provoquer un retard marginal mais sont par ailleurs inoffensives, il est généralement préférable de choisir une fonction de hachage plus rapide plutôt qu'une fonction qui nécessite plus de calculs mais qui évite quelques collisions.

Les implémentations basées sur la division peuvent être particulièrement préoccupantes car une division nécessite plusieurs cycles sur presque toutes les microarchitectures de processeur . La division ( modulo ) par une constante peut être inversée pour devenir une multiplication par l'inverse multiplicatif de la taille du mot de cette constante. Cela peut être fait par le programmeur ou par le compilateur. La division peut également être réduite directement en une série de décalages-soustractions et de décalages-ajouts, bien que la minimisation du nombre de ces opérations requises soit un problème redoutable ; le nombre d'instructions en langage machine résultant peut être supérieur à une douzaine et submerger le pipeline. Si la microarchitecture dispose d'unités fonctionnelles multiples matérielles , alors la multiplication par l'inverse est probablement une meilleure approche.

Nous pouvons accepter que la taille de la table n ne soit pas une puissance de 2 et ne pas avoir à effectuer d'opération de reste ou de division, car ces calculs sont parfois coûteux. Par exemple, soit n significativement inférieur à 2 ^b . Considérons une fonction génératrice de nombres pseudo-aléatoires P (clé) qui est uniforme sur l'intervalle [0, 2 ^b − 1] . Une fonction de hachage uniforme sur l'intervalle [0, n − 1] est n P (clé) / 2 ^b . Nous pouvons remplacer la division par un décalage binaire à droite (éventuellement plus rapide) : n P (clé) >> b .

Si les clés sont hachées de manière répétée et que la fonction de hachage est coûteuse, il est possible de gagner du temps de calcul en précalculant les codes de hachage et en les stockant avec les clés. La correspondance des codes de hachage signifie presque certainement que les clés sont identiques. Cette technique est utilisée pour la table de transposition dans les programmes de jeu, qui stocke une représentation hachée de 64 bits de la position du plateau.

Un schéma de hachage universel est un algorithme randomisé qui sélectionne une fonction de hachage h parmi une famille de telles fonctions, de telle sorte que la probabilité d'une collision de deux clés distinctes soit de 1/ m , où m est le nombre de valeurs de hachage distinctes souhaitées, indépendamment des deux clés. Le hachage universel garantit (dans un sens probabiliste) que l'application de la fonction de hachage se comportera aussi bien que si elle utilisait une fonction aléatoire, quelle que soit la distribution des données d'entrée. Il aura cependant plus de collisions que le hachage parfait et peut nécessiter plus d'opérations qu'une fonction de hachage à usage spécifique.

Une fonction de hachage qui n'autorise que certaines tailles de table ou des chaînes jusqu'à une certaine longueur, ou qui ne peut pas accepter de graine (c'est-à-dire autoriser le double hachage) est moins utile qu'une fonction qui le fait.

Une fonction de hachage est applicable dans de nombreuses situations. En particulier dans le domaine de la cryptographie, les applications notables incluent :

• Vérification de l'intégrité : des valeurs de hachage identiques pour différents fichiers impliquent une égalité, fournissant un moyen fiable de détecter les modifications de fichiers.
• Dérivation de clé : des modifications mineures de l'entrée entraînent une modification de la sortie d'apparence aléatoire, connue sous le nom de propriété de diffusion. Ainsi, les fonctions de hachage sont utiles pour les fonctions de dérivation de clé.
• Codes d'authentification des messages (MAC) : grâce à l'intégration d'une clé confidentielle aux données d'entrée, les fonctions de hachage peuvent générer des MAC garantissant l'authenticité des données, comme dans les HMAC .
• Stockage du mot de passe : la valeur de hachage du mot de passe n'expose aucun détail du mot de passe, ce qui souligne l'importance de stocker en toute sécurité les mots de passe hachés sur le serveur.
• Signatures : les hachages de message sont signés plutôt que le message entier.

Une procédure de hachage doit être déterministe : pour une valeur d'entrée donnée, elle doit toujours générer la même valeur de hachage. En d'autres termes, elle doit être une fonction des données à hacher, au sens mathématique du terme. Cette exigence exclut les fonctions de hachage qui dépendent de paramètres de variables externes, tels que les générateurs de nombres pseudo-aléatoires ou l'heure de la journée. Elle exclut également les fonctions qui dépendent de l'adresse mémoire de l'objet haché, car l'adresse peut changer pendant l'exécution (comme cela peut se produire sur les systèmes qui utilisent certaines méthodes de récupération de place ), bien que parfois un nouveau hachage de l'élément soit possible.

Le déterminisme se situe dans le contexte de la réutilisation de la fonction. Par exemple, Python ajoute la fonctionnalité selon laquelle les fonctions de hachage utilisent une graine aléatoire générée une fois lorsque le processus Python démarre en plus de l'entrée à hacher. Le hachage Python ( SipHash ) est toujours une fonction de hachage valide lorsqu'il est utilisé dans une seule exécution, mais si les valeurs sont conservées (par exemple, écrites sur le disque), elles ne peuvent plus être traitées comme des valeurs de hachage valides, car lors de l'exécution suivante, la valeur aléatoire peut différer.

Il est souvent souhaitable que la sortie d'une fonction de hachage ait une taille fixe (mais voir ci-dessous). Si, par exemple, la sortie est limitée à des valeurs entières de 32 bits, les valeurs de hachage peuvent être utilisées pour indexer dans un tableau. Un tel hachage est couramment utilisé pour accélérer les recherches de données. La production d'une sortie de longueur fixe à partir d'une entrée de longueur variable peut être réalisée en divisant les données d'entrée en morceaux de taille spécifique. Les fonctions de hachage utilisées pour les recherches de données utilisent une expression arithmétique qui traite de manière itérative des morceaux de l'entrée (tels que les caractères d'une chaîne) pour produire la valeur de hachage.

Dans de nombreuses applications, la plage de valeurs de hachage peut être différente à chaque exécution du programme ou peut changer au cours de la même exécution (par exemple, lorsqu'une table de hachage doit être étendue). Dans ces situations, il faut une fonction de hachage qui prend deux paramètres : les données d'entrée z et le nombre n de valeurs de hachage autorisées.

Une solution courante consiste à calculer une fonction de hachage fixe avec une plage très large (par exemple, de 0 à 2 ³² − 1 ), à diviser le résultat par n et à utiliser le reste de la division . Si n est lui-même une puissance de 2 , cela peut être réalisé par masquage et décalage de bits . Lorsque cette approche est utilisée, la fonction de hachage doit être choisie de manière à ce que le résultat ait une distribution relativement uniforme entre 0 et n − 1 , pour toute valeur de n pouvant apparaître dans l'application. Selon la fonction, le reste peut être uniforme uniquement pour certaines valeurs de n , par exemple les nombres impairs ou premiers .

Lorsque la fonction de hachage est utilisée pour stocker des valeurs dans une table de hachage qui survit à l'exécution du programme et que la table de hachage doit être étendue ou réduite, la table de hachage est appelée table de hachage dynamique.

Il est souhaitable de disposer d'une fonction de hachage qui déplace le nombre minimum d'enregistrements lorsque la table est redimensionnée. Il faut une fonction de hachage H ( z , n ) (où z est la clé hachée et n est le nombre de valeurs de hachage autorisées) telle que H ( z , n +1)= H ( z , n ) avec une probabilité proche de n /( n +1) .

Le hachage linéaire et le hachage en spirale sont des exemples de fonctions de hachage dynamiques qui s'exécutent en temps constant mais assouplissent la propriété d'uniformité pour obtenir la propriété de mouvement minimal. Le hachage extensible utilise une fonction de hachage dynamique qui nécessite un espace proportionnel à n pour calculer la fonction de hachage, et elle devient une fonction des clés précédentes qui ont été insérées. Plusieurs algorithmes qui préservent la propriété d'uniformité mais nécessitent un temps proportionnel à n pour calculer la valeur de H ( z , n ) ont été inventés.

Une fonction de hachage avec un mouvement minimal est particulièrement utile dans les tables de hachage distribuées .

Dans certaines applications, les données d'entrée peuvent contenir des caractéristiques qui ne sont pas pertinentes à des fins de comparaison. Par exemple, lors de la recherche d'un nom personnel, il peut être souhaitable d'ignorer la distinction entre les lettres majuscules et minuscules. Pour de telles données, il faut utiliser une fonction de hachage compatible avec le critère d'équivalence des données utilisé : c'est-à-dire que deux entrées considérées comme équivalentes doivent produire la même valeur de hachage. Cela peut être accompli en normalisant l'entrée avant de la hacher, par exemple en mettant toutes les lettres en majuscules.

Il existe plusieurs algorithmes courants pour hacher des entiers. La méthode donnant la meilleure distribution dépend des données. L'une des méthodes les plus simples et les plus courantes dans la pratique est la méthode de division modulo.

Si les données à hacher sont suffisamment petites, on peut alors utiliser les données elles-mêmes (réinterprétées comme un entier) comme valeur hachée. Le coût de calcul de cette fonction de hachage d'identité est pratiquement nul. Cette fonction de hachage est parfaite , car elle associe chaque entrée à une valeur de hachage distincte.

La signification de « suffisamment petit » dépend de la taille du type utilisé comme valeur hachée. Par exemple, en Java , le code de hachage est un entier de 32 bits. Ainsi, les objets entiers de 32 bits Integeret à virgule flottante de 32 bits Floatpeuvent simplement utiliser la valeur directement, alors que les objets entiers de 64 bits Longet à virgule flottante de 64 bits Doublene le peuvent pas.

D'autres types de données peuvent également utiliser ce schéma de hachage. Par exemple, lors du mappage de chaînes de caractères entre majuscules et minuscules , on peut utiliser le codage binaire de chaque caractère, interprété comme un entier, pour indexer une table qui donne la forme alternative de ce caractère (« A » pour « a », « 8 » pour « 8 », etc.). Si chaque caractère est stocké sur 8 bits (comme dans l'ASCII étendu ou l'ISO Latin 1 ), la table ne contient que 2 ⁸ = 256 entrées ; dans le cas de caractères Unicode , la table aurait 17 × 2 ¹⁶ =1 114 112 entrées.

La même technique peut être utilisée pour mapper des codes de pays à deux lettres comme « us » ou « za » aux noms de pays (26 ^{2 = 676 entrées de table),} des codes postaux à 5 chiffres comme 13083 aux noms de ville (100 000 entrées), etc. Les valeurs de données non valides (telles que le code de pays « xx » ou le code postal 00000) peuvent être laissées non définies dans le tableau ou mappées sur une valeur « nulle » appropriée.

Si les clés sont uniformément ou suffisamment uniformément réparties sur l'espace de clés, de sorte que les valeurs de clés sont essentiellement aléatoires, elles peuvent alors être considérées comme déjà « hachées ». Dans ce cas, n'importe quel nombre de bits de la clé peut être extrait et rassemblé sous forme d'index dans la table de hachage. Par exemple, une fonction de hachage simple peut masquer les m bits les moins significatifs et utiliser le résultat comme index dans une table de hachage de taille 2 ^m .

Un code de hachage à carrés médians est produit en élevant au carré l'entrée et en extrayant un nombre approprié de chiffres ou de bits médians. Par exemple, si l'entrée est123 456 789 et la taille de la table de hachage10 000 , puis en élevant la clé au carré, on obtient15 241 578 750 190 521 , le code de hachage est donc considéré comme les 4 chiffres du milieu du nombre à 17 chiffres (en ignorant le chiffre le plus élevé) 8750. La méthode des carrés du milieu produit un code de hachage raisonnable s'il n'y a pas beaucoup de zéros de début ou de fin dans la clé. Il s'agit d'une variante du hachage multiplicatif, mais pas aussi efficace car une clé arbitraire n'est pas un bon multiplicateur.

Une technique standard consiste à utiliser une fonction modulo sur la clé, en sélectionnant un diviseur M qui est un nombre premier proche de la taille de la table, donc h ( K ) ≡ K (mod M ) . La taille de la table est généralement une puissance de 2. Cela donne une distribution de {0, M − 1} . Cela donne de bons résultats sur un grand nombre d'ensembles de clés. Un inconvénient important du hachage par division est que la division nécessite plusieurs cycles sur la plupart des architectures modernes (y compris x86 ) et peut être 10 fois plus lente que la multiplication. Un deuxième inconvénient est qu'elle ne décompose pas les clés groupées. Par exemple, les clés 123000, 456000, 789000, etc. modulo 1000 correspondent toutes à la même adresse. Cette technique fonctionne bien dans la pratique car de nombreux ensembles de clés sont déjà suffisamment aléatoires et la probabilité qu'un ensemble de clés soit cyclique par un grand nombre premier est faible.

Français Le codage algébrique est une variante de la méthode de division du hachage qui utilise la division par un polynôme modulo 2 au lieu d'un entier pour mapper n bits sur m bits. Dans cette approche, M = 2 ^m , et nous postulons un polynôme de m ième degré Z ( x ) = x ^m + ζ _{m −1} x ^{m −1} + ⋯ + ζ ₀ . Une clé K = ( k _{n −1} … k ₁ k ₀ ) ₂ peut être considérée comme le polynôme K ( x ) = k _{n −1} x ^{n −1} + ⋯ + k ₁ x + k ₀ . Le reste en utilisant l'arithmétique polynomiale modulo 2 est K ( x ) mod Z ( x ) = h _{m −1} x ^{m −1} + ⋯ h ₁ x + h ₀ . Alors h ( K ) = ( h _{m −1} … h ₁ h ₀ ) ₂ . Si Z ( x ) est construit pour avoir t coefficients non nuls ou moins, alors les clés qui partagent moins de t bits sont garanties de ne pas entrer en collision.

Z est une fonction de k , t et n (le dernier étant un diviseur de 2 ^k − 1 ) et est construite à partir du corps fini GF(2 ^k ) . Knuth donne un exemple : en prenant ( n , m , t ) = (15,10,7) on obtient Z ( x ) = x ¹⁰ + x ⁸ + x ⁵ + x ⁴ + x ² + x + 1 . La dérivation est la suivante :

Soit S le plus petit ensemble d'entiers tels que {1,2,…, t } ⊆ S et (2 j mod n ) ∈ S ∀ j ∈ S .

Définissons où α ∈ ⁿ GF(2 ^k ) et où les coefficients de P ( x ) sont calculés dans ce corps. Alors le degré de P ( x ) = | S | . Puisque α ^{2 j} est une racine de P ( x ) chaque fois que α ^j est une racine, il s'ensuit que les coefficients p ⁱ de P ( x ) satisfont p²
_je= p _i , donc ils sont tous 0 ou 1. Si R ( x ) = r _{n −1} x ^{n −1} + ⋯ + r ₁ x + r ₀ est un polynôme non nul modulo 2 avec au plus t coefficients non nuls, alors R ( x ) n'est pas un multiple de P ( x ) modulo 2. Il s'ensuit que la fonction de hachage correspondante mappera les clés avec moins de t bits en commun à des indices uniques.

Le résultat habituel est que n ou t devienne grand, ou les deux, pour que le schéma soit réalisable sur le plan informatique. Par conséquent, il est plus adapté à une implémentation matérielle ou microcode.

Le hachage de permutation unique a un temps d'insertion garanti dans le meilleur des cas.

Le hachage multiplicatif standard utilise la formule h _a ( K ) = ⌊ ( aK mod W ) / ( W / M ) ⌋ , qui produit une valeur de hachage dans {0, …, M − 1} . La valeur a est une valeur choisie de manière appropriée qui doit être relativement première à W ; elle doit être grande, et sa représentation binaire un mélange aléatoire de 1 et de 0. Un cas pratique particulier important se produit lorsque W = 2 ^w et M = 2 ^m sont des puissances de 2 et w est la taille du mot machine . Dans ce cas, cette formule devient h _a ( K ) = ⌊ ( aK mod 2 ^w ) / 2 ^{w − m} ⌋ . Ceci est spécial car l'arithmétique modulo 2 ^w est effectuée par défaut dans les langages de programmation de bas niveau et la division entière par une puissance de 2 est simplement un décalage à droite, donc, en C , par exemple, cette fonction devient

hachage non signé (K non signé) { retour (a*K) >> (wm); } 

et pour m et w fixes , cela se traduit par une seule multiplication d'entiers et un décalage vers la droite, ce qui en fait l'une des fonctions de hachage les plus rapides à calculer.

Le hachage multiplicatif est sujet à une « erreur courante » qui conduit à une mauvaise diffusion : les bits d'entrée de valeur supérieure n'affectent pas les bits de sortie de valeur inférieure. Une transmutation sur l'entrée qui décale la plage des bits supérieurs conservés vers le bas et les XOR ou les AJOUTE à la clé avant l'étape de multiplication corrige cela. La fonction résultante ressemble à ceci :

hachage non signé (K non signé) { K ^= K >> (wm); retour (a*K) >> (wm); } 

Le hachage de Fibonacci est une forme de hachage multiplicatif dans laquelle le multiplicateur est 2 ^w / ϕ , où w est la longueur du mot machine et ϕ (phi) est le nombre d'or (environ 1,618). Une propriété de ce multiplicateur est qu'il distribue uniformément sur l'espace table, des blocs de clés consécutives par rapport à tout bloc de bits dans la clé. Les clés consécutives dans les bits de poids fort ou les bits de poids faible de la clé (ou d'un autre champ) sont relativement courantes. Les multiplicateurs pour différentes longueurs de mots sont :

• 16: un =9E37 ₁₆=40 503 ₁₀
• 32: un =9E37 79B9 ₁₆=2 654 435 769 ₁₀
• 48: un =9E37 79B9 7F4B ₁₆=173 961 102 589 771 ₁₀
• 64: un =9E37 79B9 7F4A 7C15 ₁₆=11 400 714 819 323 198 485 ₁₀

Le multiplicateur doit être impair, de sorte que le bit le moins significatif de la sortie soit inversible modulo 2 ^w . Les deux dernières valeurs données ci-dessus sont arrondies (respectivement vers le haut et vers le bas) de plus de la moitié d'un bit le moins significatif pour y parvenir.

Le hachage par tabulation, plus généralement connu sous le nom de hachage Zobrist d'après Albert Zobrist , est une méthode de construction de familles universelles de fonctions de hachage en combinant la recherche dans une table avec des opérations XOR. Cet algorithme s'est avéré très rapide et de haute qualité pour le hachage (en particulier le hachage de clés de nombres entiers).

Le hachage Zobrist a été introduit à l'origine comme un moyen de représenter de manière compacte les positions d'échecs dans les programmes de jeu informatique. Un nombre aléatoire unique a été attribué pour représenter chaque type de pièce (six pour le noir et six pour le blanc) sur chaque case de l'échiquier. Ainsi, une table de 64 × 12 de ces nombres est initialisée au début du programme. Les nombres aléatoires peuvent avoir n'importe quelle longueur, mais 64 bits étaient naturels en raison des 64 cases de l'échiquier. Une position a été transcrite en parcourant les pièces d'une position, en indexant les nombres aléatoires correspondants (les espaces vacants n'étaient pas inclus dans le calcul) et en les XORant ensemble (la valeur de départ pouvait être 0 (la valeur d'identité pour XOR) ou une graine aléatoire). La valeur résultante a été réduite par modulo, pliage ou une autre opération pour produire un index de table de hachage. Le hachage Zobrist original a été stocké dans la table comme représentation de la position.

Plus tard, la méthode a été étendue au hachage d'entiers en représentant chaque octet de chacune des 4 positions possibles du mot par un nombre aléatoire unique de 32 bits. Ainsi, une table de 2 ⁸ × 4 nombres aléatoires est construite. Un entier haché de 32 bits est transcrit en indexant successivement la table avec la valeur de chaque octet de l'entier en texte clair et en exécutant XOR les valeurs chargées ensemble (là encore, la valeur de départ peut être la valeur d'identité ou une graine aléatoire). L'extension naturelle aux entiers de 64 bits consiste à utiliser une table de 2 ⁸ × 8 nombres aléatoires de 64 bits.

Ce type de fonction possède quelques propriétés théoriques intéressantes, dont l'une est appelée indépendance 3-tuple , ce qui signifie que chaque 3-tuple de clés est également susceptible d'être mappé à n'importe quel 3-tuple de valeurs de hachage.

Une fonction de hachage peut être conçue pour exploiter l'entropie existante dans les clés. Si les clés ont des zéros de début ou de fin, ou des champs particuliers qui ne sont pas utilisés, toujours zéro ou une autre constante, ou varient généralement peu, alors masquer uniquement les bits volatils et hacher sur ceux-ci fournira une fonction de hachage meilleure et éventuellement plus rapide. Des diviseurs ou multiplicateurs sélectionnés dans les schémas de division et de multiplicité peuvent créer des fonctions de hachage plus uniformes si les clés sont cycliques ou présentent d'autres redondances.

Lorsque les valeurs de données sont des chaînes de caractères longues (ou de longueur variable) (telles que des noms de personnes, des adresses de pages Web ou des messages électroniques), leur distribution est généralement très inégale et présente des dépendances complexes. Par exemple, le texte dans n'importe quelle langue naturelle présente des distributions de caractères et de paires de caractères très non uniformes , caractéristiques de la langue. Pour de telles données, il est prudent d'utiliser une fonction de hachage qui dépend de tous les caractères de la chaîne et de chaque caractère de manière différente.

Les fonctions de hachage simplistes peuvent ajouter les n premiers et derniers caractères d'une chaîne ainsi que la longueur, ou former un hachage de la taille d'un mot à partir des 4 caractères du milieu d'une chaîne. Cela évite d'itérer sur la chaîne (potentiellement longue), mais les fonctions de hachage qui ne hachent pas tous les caractères d'une chaîne peuvent facilement devenir linéaires en raison de redondances, de regroupements ou d'autres pathologies dans l'ensemble de clés. De telles stratégies peuvent être efficaces en tant que fonction de hachage personnalisée si la structure des clés est telle que le milieu, les extrémités ou d'autres champs sont nuls ou une autre constante invariante qui ne différencie pas les clés ; les parties invariantes des clés peuvent alors être ignorées.

L'exemple paradigmatique de pliage par caractères consiste à additionner les valeurs entières de tous les caractères de la chaîne. Une meilleure idée consiste à multiplier le total du hachage par une constante, généralement un nombre premier de taille importante, avant d'ajouter le caractère suivant, en ignorant le dépassement de capacité. L'utilisation de la fonction OU exclusif au lieu de l'addition est également une alternative plausible. L'opération finale serait un modulo, un masque ou une autre fonction pour réduire la valeur du mot à un index de la taille de la table. La faiblesse de cette procédure est que les informations peuvent se regrouper dans les bits supérieurs ou inférieurs des octets ; ce regroupement restera dans le résultat haché et provoquera plus de collisions qu'un hachage aléatoire approprié. Les codes d'octets ASCII, par exemple, ont un bit supérieur de 0, et les chaînes imprimables n'utilisent pas le dernier code d'octet ou la plupart des 32 premiers codes d'octets, de sorte que les informations, qui utilisent les codes d'octets restants, sont regroupées dans les bits restants d'une manière non évidente.

L'approche classique, surnommée le hachage PJW, d'après les travaux de Peter J. Weinberger aux Bell Labs dans les années 1970, a été conçue à l'origine pour hacher des identifiants dans des tables de symboles de compilateur comme indiqué dans le « Dragon Book » . Cette fonction de hachage décale les octets de 4 bits avant de les additionner. Lorsque la quantité s'enroule, les 4 bits de poids fort sont décalés vers l'extérieur et, s'ils ne sont pas nuls, ramenés à l'octet de poids faible de la quantité cumulée. Le résultat est un code de hachage de la taille d'un mot auquel un modulo ou une autre opération de réduction peut être appliqué pour produire l'index de hachage final.

Aujourd'hui, notamment avec l'avènement des tailles de mots de 64 bits, un hachage de chaîne de longueur variable par morceaux de mots beaucoup plus efficace est disponible.

Les microprocesseurs modernes permettent un traitement beaucoup plus rapide si les chaînes de caractères de 8 bits ne sont pas hachées en traitant un caractère à la fois, mais en interprétant la chaîne comme un tableau d'entiers de 32 ou 64 bits et en hachant/accumulant ces valeurs entières de « mots larges » au moyen d'opérations arithmétiques (par exemple, multiplication par constante et décalage de bits). Le mot final, qui peut avoir des positions d'octets inoccupées, est rempli de zéros ou d'une valeur de randomisation spécifiée avant d'être intégré dans le hachage. Le code de hachage accumulé est réduit par un modulo final ou une autre opération pour produire un index dans la table.

De la même manière qu'une chaîne de caractères ASCII ou EBCDIC représentant un nombre décimal est convertie en une quantité numérique à des fins de calcul, une chaîne de longueur variable peut être convertie en x _{k −1} a ^{k −1} + x _{k −2} a ^{k −2} + ⋯ + x ₁ a + x ₀ . Il s'agit simplement d'un polynôme dans une base a > 1 qui prend les composants ( x ₀ , x ₁ ,..., x _{k −1} ) comme caractères de la chaîne d'entrée de longueur k . Il peut être utilisé directement comme code de hachage, ou une fonction de hachage lui est appliquée pour mapper la valeur potentiellement grande à la taille de la table de hachage. La valeur de a est généralement un nombre premier suffisamment grand pour contenir le nombre de caractères différents dans le jeu de caractères des clés potentielles. Le hachage de conversion de base des chaînes minimise le nombre de collisions. Les tailles de données disponibles peuvent restreindre la longueur maximale de la chaîne qui peut être hachée avec cette méthode. Par exemple, un mot de 128 bits ne hachera qu'une chaîne alphabétique de 26 caractères (en ignorant la casse) avec une base de 29 ; une chaîne ASCII imprimable est limitée à 9 caractères avec une base de 97 et un mot de 64 bits. Cependant, les clés alphabétiques sont généralement de longueur modeste, car les clés doivent être stockées dans la table de hachage. Les chaînes de caractères numériques ne posent généralement pas de problème ; 64 bits peuvent compter jusqu'à 10 ¹⁹ , ou 19 chiffres décimaux avec une base de 10.

Dans certaines applications, comme la recherche de sous-chaînes , on peut calculer une fonction de hachage h pour chaque sous-chaîne de k caractères d'une chaîne de n caractères donnée en faisant avancer une fenêtre de largeur k caractères le long de la chaîne, où k est un entier fixe et n > k . La solution simple, qui consiste à extraire une telle sous-chaîne à chaque position de caractère dans le texte et à calculer h séparément, nécessite un nombre d'opérations proportionnel à k · n . Cependant, avec le bon choix de h , on peut utiliser la technique du hachage roulant pour calculer tous ces hachages avec un effort proportionnel à mk + n où m est le nombre d'occurrences de la sous-chaîne.

L'algorithme le plus connu de ce type est Rabin-Karp avec des performances dans les cas meilleurs et moyens O ( n + mk ) et dans le pire des cas O ( n · k ) (en toute honnêteté, le pire des cas est ici gravement pathologique : la chaîne de texte et la sous-chaîne sont toutes deux composées d'un seul caractère répété, comme t ="AAAAAAAAAAAA" et s ="AAA"). La fonction de hachage utilisée pour l'algorithme est généralement l' empreinte digitale de Rabin , conçue pour éviter les collisions dans les chaînes de caractères de 8 bits, mais d'autres fonctions de hachage appropriées sont également utilisées.

Les résultats du pire cas pour une fonction de hachage peuvent être évalués de deux manières : théorique et pratique. Le pire cas théorique est la probabilité que toutes les clés correspondent à un seul emplacement. Le pire cas pratique est la séquence de sonde la plus longue attendue (fonction de hachage + méthode de résolution de collision). Cette analyse prend en compte le hachage uniforme, c'est-à-dire que n'importe quelle clé correspond à n'importe quel emplacement particulier avec une probabilité de 1/ m , une caractéristique des fonctions de hachage universelles.

Alors que Knuth s'inquiète des attaques adverses sur les systèmes en temps réel, Gonnet a montré que la probabilité d'un tel cas est « ridiculement faible ». Sa représentation était que la probabilité que k de n clés soient mappées sur un seul emplacement est α ^k / ( e ^α k !) , où α est le facteur de charge, n / m .

Le terme « hachage » offre une analogie naturelle avec son sens non technique (découper ou gâcher quelque chose), étant donné la façon dont les fonctions de hachage brouillent leurs données d'entrée pour dériver leur sortie. Dans ses recherches sur l'origine précise du terme, Donald Knuth note que, bien que Hans Peter Luhn d' IBM semble avoir été le premier à utiliser le concept de fonction de hachage dans une note datée de janvier 1953, le terme lui-même n'est apparu dans la littérature publiée qu'à la fin des années 1960, dans Digital Computer System Principles de Herbert Hellerman , même s'il était déjà un jargon répandu à cette époque.