droite|vignette|240x240px| Une fonction de hachage parfait pour les quatre noms John Smith, Lisa Smith, Sam Doe et Sandra Dee. droite|vignette|240x240px| Une fonction de hachage parfait minimal pour les quatre noms John Smith, Lisa Smith, Sam Doe et Sandra Dee. En informatique, une fonction de hachage parfait pour un ensemble est une fonction de hachage qui associe des éléments distincts de à un ensemble de entiers, sans collisions. En termes mathématiques, c'est une fonction injective.

Des fonctions de hachage parfait peuvent être utilisées pour implémenter une table de correspondance avec un temps d'accès constant dans le pire des cas. Une fonction de hachage parfait peut, comme toute fonction de hachage, être utilisée pour implémenter des tables de hachage, avec l'avantage qu'aucun mécanisme de résolution de collisions ne doit être implémenté. De plus, si les clés ne sont pas des données utiles et si l'on sait que les clés interrogées seront valides, les clés n'ont pas besoin d'être stockées dans la table de correspondance, ce qui permet d'économiser de l'espace mémoire.

Un inconvénient des fonctions de hachage parfait est que doit être connu pour la construction de la fonction de hachage parfait. Les fonctions de hachage parfait non dynamiques doivent être reconstruites si change. Pour changer fréquemment , des fonctions de hachage parfait dynamiques peuvent être utilisées au prix d'un espace supplémentaire. L'espace requis pour stocker la fonction de hachage parfait est en .

Les paramètres de performance importants pour les fonctions de hachage parfait sont le temps d'évaluation, qui doit être constant, le temps de construction et la taille mémoire de la représentation.

Applications Une fonction de hachage parfait avec des valeurs dans une plage limitée peut être utilisée pour des opérations de recherche efficaces, en plaçant les clés de (ou d'autres valeurs associées) dans une table de correspondance indexée par les valeurs de sortie de la fonction. On peut alors tester si une clé est présente dans , ou rechercher une valeur associée à cette clé, en la recherchant dans sa cellule du tableau. Chacune de ces recherches prend un temps constant dans le pire des cas. Avec un hachage parfait, les données associées peuvent être lues ou écrites avec un seul accès à la table.

Performance des fonctions de hachage parfait Les paramètres importants de performance pour un hachage parfait sont la taille de représentation, le temps d'évaluation, le temps de construction et, en outre, le ratio où est le nombre de cellules, et le nombre d'éléments dans la structure de données. Le temps d'évaluation peut être aussi rapide que , ce qui est optimal. Le temps de construction est d'au moins , car chaque élément de doit être pris en compte et contient éléments. Cette borne inférieure peut être atteinte en pratique.

La borne inférieure de la taille mémoire de représentation de la fonction de hachage dépend de et . Soit et une fonction de hachage parfait. Une bonne approximation de la borne inférieure est bits par élément. Pour un hachage parfait minimal, i.e. pour , la borne inférieure est bits par élément.

Construction Une fonction de hachage parfait pour un ensemble spécifique qui peut être évalué en temps constant, et avec des valeurs dans une petite plage, peut être trouvée par un algorithme probabiliste dans un nombre d'opérations qui est proportionnel à la taille de S. La construction originale de Fredman, Komlós & Szemerédi (1984) utilisent un schéma à deux niveaux pour envoyer un ensemble de éléments sur une plage de indices, puis envoyer chaque indice sur une plage de valeurs de hachage. Le premier niveau de leur construction choisit un grand nombre premier (plus grand que la taille de l'univers à partir duquel est tiré), et un paramètre , et fait correspondre chaque élément de à l'indice

Si est choisi au hasard, cette étape est susceptible d'avoir des collisions, mais le nombre d'éléments qui sont simultanément envoyés au même indice a de grandes chances d'être petit. Le deuxième niveau de leur construction attribue des plages disjointes d'entiers de taille à chaque indice . Il utilise un deuxième ensemble de fonctions modulaires linéaires, une pour chaque index , pour mapper chaque membre de dans la plage associée à .

Comme le montrent Fredman, Komlós & Szemerédi (1984), il existe un choix du paramètre tel que la somme des longueurs des plages pour les valeurs différentes de soit en . De plus, pour chaque valeur de , il existe une fonction modulaire linéaire qui envoie le sous-ensemble correspondant de dans la plage associée à cette valeur.La valeur de et les fonctions de second niveau pour chaque valeur de , peuvent être trouvées en temps polynomial en choisissant des valeurs au hasard jusqu'à en trouver une qui fonctionne.

La fonction de hachage elle-même nécessite un espace de stockage pour stocker , et toutes les fonctions modulaires linéaires de second niveau. Le calcul de la valeur de hachage d'une clé donnée peut être effectué en temps constant en calculant , en recherchant la fonction de second niveau associée à et en appliquant cette fonction à . Une version modifiée de ce schéma à deux niveaux avec un plus grand nombre de valeurs au niveau supérieur peut être utilisée pour construire une fonction de hachage parfait qui envoie dans une plage plus petite de longueur .

Une méthode plus récente pour construire une fonction de hachage parfait est décrite par Belazzougui, Botelho & Dietzfelbinger (2009) comme "hacher, déplacer et compresser". Ici, une fonction de hachage de premier niveau est également utilisée pour envoyer des éléments sur une plage de entiers. Un élément est stocké dans le Bucket .

Ensuite, par ordre décroissant de taille, les éléments de chaque bucket sont hachés par une fonction de hachage d'une séquence de fonctions de hachage entièrement aléatoires indépendantes , en commençant par . Si la fonction de hachage ne produit aucune collision pour le bucket et que les valeurs résultantes ne sont pas encore occupées par d'autres éléments d'autres buckets, la fonction est choisie pour ce bucket. Si ce n'est pas le cas, la fonction de hachage suivante de la séquence est testée.

Pour évaluer la fonction de hachage parfait , il suffit de sauvegarder le l'image σ de l'indice de compartiment sur la fonction de hachage correcte dans la séquence, ce qui donne .

Enfin, pour réduire la taille de la représentation, les ( sont compressés sous une forme qui permet toujours l'évaluation en .

Cette approche nécessite un temps linéaire en pour la construction, et permet un temps d'évaluation constant. La taille de la représentation est en , et dépend de la plage atteinte. Par exemple, avec Belazzougui, Botelho & Dietzfelbinger (2009) ont atteint une taille de représentation comprise entre 3,03 bits/clé et 1,40 bits/clé pour leur exemple donné de d'entrées, les valeurs inférieures nécessitant un temps de calcul plus élevé. La limite inférieure de l'espace dans ce scénario est de 0,88 bit/clé.

Pseudocode l'algorithme de hachage, de déplacement et de compression est (1) Diviser S en paquets (2) Trier les paquets Bi par ordre décroissant selon la taille |Bi| (3) Initialiser le tableau T[0...m-1] avec des 0 (4) pour tout i ∈[r], dans l'ordre de (2), faire (5) pour l ← 1,2, ... (6) répéter la construction de Ki ← l(x)|x ∈ Bi} (6) tant que |Ki|≠|Bi| ou Ki∩{j|T[j]=1}≠ ∅ (7) soit σ(i):= le l réussi (8) pour tout j ∈ Ki laisse T[j]:= 1 (9) Transformer (σi)0≤i<r sous forme compressée, en conservant l'accès .

Limites inférieures en espace Le stockage de la fonction de Fredman, Komlós & Szemerédi (1984) en est quasi optimal : toute fonction de hachage parfait calculable en temps constant nécessite au moins un nombre de bits proportionnel à la taille de .

Pour les fonctions de hachage parfait minimal, la borne inférieure théorique de l'espace de stockage est

bits par clé.

Pour les fonctions de hachage parfait, on définit ε tel que la taille de la plage de h est . Avec la formule donnée par Belazzougui, Botelho & Dietzfelbinger (2009) et pour un univers dont la taille tend vers l'infini, le minorant de l'espace est

bits par clé, moins bits au total.

Extensions

Identité de l'adresse mémoire Un exemple trivial mais omniprésent de hachage parfait est implicite dans l'adresse mémoire (virtuelle) d'un ordinateur. Étant donné que chaque octet de mémoire virtuelle est un emplacement de stockage distinct, unique et directement adressable, la valeur de l'adresse de départ de tout objet stocké en mémoire peut être considérée comme un hachage parfait de facto de cet objet dans toute la plage d'adresses mémoire.

Hachage parfait dynamique L'utilisation d'une fonction de hachage parfait est préférable dans les situations où il existe un grand ensemble fréquemment interrogé, , qui est rarement mis à jour. En effet, toute modification de l'ensemble peut rendre le hachage non parfait pour l'ensemble modifié. Les solutions qui mettent à jour la fonction de hachage chaque fois que l'ensemble est modifié sont connues sous le nom de hachage parfait dynamique, mais ces méthodes sont relativement compliquées à mettre en œuvre.

Fonction de hachage parfait minimale Une fonction de hachage parfait minimal est une fonction de hachage parfait qui envoie clés sur entiers consécutifs - généralement les nombres de à ou de à . Une manière plus formelle d'exprimer cela est la suivante : Soient et des éléments d'un ensemble fini . Alors est une fonction de hachage parfait minimale si et seulement si implique ( injectivité ) et il existe un entier tel que la plage de soit . Il a été prouvé qu'un schéma de hachage parfait minimal à usage général nécessite au moins bits/clé. Bien que cette limite d'espace ait été atteinte par des travaux théoriques, en pratique, les schémas de hachage parfait minimal les plus connus nécessitent environ 1,56 bits/clé si on leur donne suffisamment de temps.

hachage k-parfait Une fonction de hachage est -parfait si au plus éléments de sont envoyés sur la même valeur dans la plage. L'algorithme "hacher, déplacer et compresser" peut être utilisé pour construire des fonctions de hachage -parfait en autorisant jusqu'à collisions. Les modifications nécessaires pour y parvenir sont minimes et sont soulignées dans le pseudocode adapté ci-dessous : (4) pour tout i ∈[r], dans l'ordre de (2), faire (5) pour l ← 1,2, ... (6) répéter la formation de Ki ← l(x)|x ∈ B je } (6) jusqu'à |K i |=|B i | et Ki∩{j| T[j]=k }= ∅ (7) soit σ(i):= le l réussi (8) pour tout j ∈ Ki fixer T[j] ← T[j]+1

Préservation de la commande Une fonction de hachage parfait minimal préserve l'ordre si les clés sont données dans un certain ordre et pour toutes les clés et , implique . Dans ce cas, la valeur de la fonction est simplement la position de chaque clé dans l'ordre trié de toutes les clés. Une implémentation simple des fonctions de hachage parfait minimal préservant l'ordre avec un temps d'accès constant consiste à utiliser une fonction de hachage parfait (ordinaire) ou un hachage coucou pour stocker une table de recherche des positions de chaque clé. Si les clés à hacher sont elles-mêmes stockées dans un tableau trié, il est possible de stocker un petit nombre de bits supplémentaires par clé dans une structure de données qui peut être utilisée pour calculer rapidement des valeurs de hachage. Les fonctions de hachage parfait minimal préservant l'ordre nécessitent nécessairement bits pour être représentées.

Constructions connexes