Voir la source de Fonction de hachage parfait

{{À sourcer|date=février 2023}}[[Fichier:Hash_table_4_1_1_0_0_0_0_LL.svg|droite|vignette|240x240px| Une fonction de hachage parfait pour les quatre noms John Smith, Lisa Smith, Sam Doe et Sandra Dee.]]
[[Fichier:Hash_table_4_1_0_0_0_0_0_LL.svg|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''' {{Mvar|h}} pour un ensemble {{Mvar|S}} est une [[fonction de hachage]] qui associe des éléments distincts de {{Mvar|S}} à un ensemble de {{Mvar|m}} entiers, sans [[Collision (informatique)|collisions]]. En termes mathématiques, c'est une [[Injection (mathématiques)|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 [[Table de hachage|tables de hachage]], avec l'avantage qu'aucun mécanisme de [[Table de hachage|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 {{Mvar|S}} doit être connu pour la construction de la fonction de hachage parfait. Les fonctions de hachage parfait non dynamiques doivent être reconstruites si {{Mvar|S}} change. Pour changer fréquemment {{Mvar|S}}, 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 {{Formule|''O''(''n'')}}.

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 {{Mvar|S}} (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 {{Mvar|S}}, ou rechercher une valeur associée à cette clé, en la recherchant dans sa cellule du tableau. Chacune de ces recherches prend un [[Complexité en temps|temps constant]] dans le [[Complexité dans le pire des cas|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 <math>\frac{m}{n}</math> où {{Mvar|m}} est le nombre de cellules, et {{Mvar|n}} le nombre d'éléments dans la [[structure de données]]. Le temps d'évaluation peut être aussi rapide que {{Formule|''O''(''1'')}}, ce qui est optimal<ref name ="CHD">{{Article|langue=en|auteur1=Djamal Belazzougui|auteur2=Fabiano C. Botelho|auteur3=Martin Dietzfelbinger|titre=Algorithms—ESA 2009: 17th Annual European Symposium, Copenhagen, Denmark, September 7-9, 2009, Proceedings|périodique=Lecture Notes in Computer Science|date=2009|lire en ligne=http://cmph.sourceforge.net/papers/esa09.pdf|doi=10.1007/978-3-642-04128-0_61}}</ref>. Le temps de construction est d'au moins {{Formule|''O''(''n'')}}, car chaque élément de {{Mvar|S}} doit être pris en compte et {{Mvar|S}} contient {{Mvar|n}} éléments. Cette borne inférieure peut être atteinte en pratique<ref name="CHD" />.

La borne inférieure de la taille mémoire de représentation de la fonction de hachage dépend de {{Mvar|m}} et {{Mvar|n}}. Soit {{Formule|''m'' {{=}} (1+&epsilon;) ''n''}} et {{Mvar|h}} une fonction de hachage parfait. Une bonne approximation de la borne inférieure est <math>\log_2 e - \varepsilon \log_2 \frac{1+\varepsilon}{\varepsilon}</math> bits par élément. Pour un hachage parfait minimal, i.e. pour {{Formule|&epsilon; {{=}} 0}}, la borne inférieure est <math>\log_2 e \approx 1,44</math> bits par élément.

== Construction ==
Une fonction de hachage parfait pour un ensemble spécifique {{Mvar|S}} 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 {{Mvar|S}} de {{Mvar|n}} éléments sur une plage de {{Formule|''O''(''n'')}} indices, puis envoyer chaque indice sur une plage de valeurs de hachage. Le premier niveau de leur construction choisit un grand nombre premier {{Mvar|p}} (plus grand que la taille de l'[[Univers (logique)|univers]] à partir duquel {{Mvar|S}} est tiré), et un paramètre {{Mvar|k}}, et fait correspondre chaque élément {{Mvar|x}} de {{Mvar|S}} à l'indice

: <math>g(x)=(kx\bmod p)\bmod n.</math>

Si {{Mvar|k}} est choisi au hasard, cette étape est susceptible d'avoir des collisions, mais le nombre d'éléments {{Mvar|n<sub>i</sub>}} qui sont simultanément envoyés au même indice {{Mvar|i}} a de grandes chances d'être petit. Le deuxième niveau de leur construction attribue des plages disjointes d'entiers de taille {{Formule|''O''(''n<sub>i</sub>''<sup>2</sup>)}} à chaque indice {{Mvar|i}}. Il utilise un deuxième ensemble de fonctions modulaires linéaires, une pour chaque index {{Mvar|i}}, pour mapper chaque membre {{Mvar|x}} de {{Mvar|S}} dans la plage associée à {{Formule|''g''(''x'')}}. 

Comme le montrent Fredman, Komlós & Szemerédi (1984)<ref name="inventor">{{Article|langue=en|prénom1=Michael L.|nom1=Fredman|prénom2=János|nom2=Komlós|prénom3=Endre|nom3=Szemerédi|titre=Storing a Sparse Table with 0 (1) Worst Case Access Time|périodique=Journal of the ACM|volume=31|numéro=3|date=1984-06-26|issn=0004-5411|issn2=1557-735X|doi=10.1145/828.1884|lire en ligne=https://dl.acm.org/doi/10.1145/828.1884|consulté le=2023-02-08|pages=538–544}}</ref>, il existe un choix du paramètre {{Mvar|k}} tel que la somme des longueurs des plages pour les {{Mvar|n}} valeurs différentes de {{Formule|''g''(''x'')}} soit en {{Formule|''O''(''n'')}}. De plus, pour chaque valeur de {{Formule|''g''(''x'')}}, il existe une fonction modulaire linéaire qui envoie le sous-ensemble correspondant de {{Mvar|S}} dans la plage associée à cette valeur.La valeur de {{Mvar|k}} et les fonctions de second niveau pour chaque valeur de {{Formule|''g''(''x'')}}, peuvent être trouvées en [[Complexité en temps|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 {{Formule|''O''(''n'')}} pour stocker {{Mvar|k}}, {{Mvar|p}} et toutes les fonctions modulaires linéaires de second niveau. Le calcul de la valeur de hachage d'une clé donnée {{Mvar|x}} peut être effectué en temps constant en calculant {{Formule|''g''(''x'')}}, en recherchant la fonction de second niveau associée à {{Formule|''g''(''x'')}} et en appliquant cette fonction à {{Mvar|x}}. 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 {{Mvar|S}} dans une plage plus petite de longueur {{Formule|''n'' + ''o''(''n'')}}. 

Une méthode plus récente pour construire une fonction de hachage parfait est décrite par Belazzougui, Botelho & Dietzfelbinger (2009)<ref name="CHD" /> comme "hacher, déplacer et compresser". Ici, une fonction de hachage de premier niveau {{Mvar|g}} est également utilisée pour envoyer des éléments sur une plage de {{Mvar|r}} entiers. Un élément {{Formule|''x'' ∈ ''S''}} est stocké dans le Bucket {{Mvar|B<sub>g(x)</sub>}}.

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 {{Formule|(&Phi;<sub>1</sub>, &Phi;<sub>2</sub>, &Phi;<sub>3</sub>, ...)}}, en commençant par {{Formule|&Phi;<sub>1</sub>}}. 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 {{Formule|''h''(''x'')}}, il suffit de sauvegarder le l'image σ de l'indice de compartiment {{Formule|''g''(''x'')}} sur la fonction de hachage correcte dans la séquence, ce qui donne {{Formule|h(x) {{=}} &Phi;<sub>σ(g(x))</sub>}}. 

Enfin, pour réduire la taille de la représentation, les ( {{Formule|σ(i))<sub>0 ≤ i < r</sub>}} sont compressés sous une forme qui permet toujours l'évaluation en {{Formule|''O''(''1'')}}. 

Cette approche nécessite un temps linéaire en {{Mvar|n}} pour la construction, et permet un temps d'évaluation constant. La taille de la représentation est en {{Formule|''O''(''n'')}}, et dépend de la plage atteinte. Par exemple, avec {{Formule|''m'' {{=}} 1.23''n''}} 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 {{nobr|10 millions}} 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 {{Formule|B<sub>i</sub> :{{=}} g<sup>−1</sup>({i})&cap;S,0 ≤ i < r}}
 (2) Trier les paquets B<sub>i</sub> par ordre décroissant selon la taille |B<sub>i</sub>|
 (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 K<sub>i</sub> ← {{Formule|&Phi;}}<sub>l</sub>(x)|x ∈ B<sub>i</sub>}
 (6)         '''tant que''' |K<sub>i</sub>|'''≠'''|B<sub>i</sub>| '''ou''' K<sub>i</sub>∩{j|T[j]=1}'''≠''' ∅
 (7)     '''soit''' σ(i):= le l réussi
 (8)     '''pour tout''' j ∈ K<sub>i</sub> '''laisse''' T[j]:= 1
 (9) Transformer (σ<sub>i</sub>)<sub>0≤i<r</sub> sous forme compressée, en conservant l'accès {{Formule|''O''(''1'')}}.

== Limites inférieures en espace ==
Le stockage de la fonction de Fredman, Komlós & Szemerédi (1984)<ref name="inventor" /> en {{Formule|''O''(''n'')}} est quasi optimal : toute fonction de hachage parfait calculable en temps constant nécessite au moins un nombre de bits proportionnel à la taille de {{Mvar|S}}. 

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

: <math>\log_2e\approx1.44</math>

bits par clé. 

Pour les fonctions de hachage parfait, on définit ε tel que la taille de la plage de h est {{Formule|''m'' {{=}} (1+&epsilon;) ''n''}}. Avec la formule donnée par Belazzougui, Botelho & Dietzfelbinger (2009)<ref name="CHD" /> et pour un [[Univers (logique)|univers]] <math>U\supseteq S</math> dont la taille {{Formule|{{!}}''U''{{!}} {{=}} ''u''}} tend vers l'infini, le minorant de l'espace est

: <math>\log_2e-\varepsilon \log\frac{1+\varepsilon}{\varepsilon}</math>

bits par clé, moins {{Formule|log(''n'')}} bits au total. 

== Extensions ==

=== Identité de l'adresse mémoire ===
Un exemple trivial mais omniprésent de hachage parfait est implicite dans l'[[Mémoire virtuelle|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'[[Pointeur (programmation)|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<ref>{{Ouvrage|nom1=Witold Litwin|nom2=Tadeusz Morzy|nom3=Gottfried Vossen|titre=Advances in Databases and Information Systems|passage=254|éditeur=[[Springer Science+Business Media]]|date=19 August 1998|isbn=9783540649243|lire en ligne=https://books.google.com/books?id=66jBbZYOt-EC&pg=PA254}}</ref>.

=== 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é, {{Mvar|S}}, qui est rarement mis à jour. En effet, toute modification de l'ensemble {{Mvar|S}} 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 {{Mvar|n}} clés sur {{Mvar|n}} entiers consécutifs - généralement les nombres de {{Formule|0}} à {{Formule|''n'' &minus; 1}} ou de {{Formule|1}} à {{Mvar|n}}. Une manière plus formelle d'exprimer cela est la suivante : Soient {{Mvar|j}} et {{Mvar|k}} des éléments d'un ensemble fini {{Mvar|S}}. Alors {{Mvar|h}} est une fonction de hachage parfait minimale si et seulement si {{Formule|1=''h''(''j'') = ''h''(''k'')}} implique {{Formule|1=''j'' = ''k''}} ( [[Injection (mathématiques)|injectivité]] ) et il existe un entier ''{{mvar|a}}'' tel que la plage de {{Mvar|h}} soit {{Formule|''a''..''a'' + {{!}}''S''{{!}} &minus; 1}}. Il a été prouvé qu'un schéma de hachage parfait minimal à usage général nécessite au moins {{Formule|lg ''e'' ≈ 1.44}} 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 {{Mvar|k}} -parfait si au plus {{Mvar|k}} éléments de {{Mvar|S}} 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 {{Mvar|k}} -parfait en autorisant jusqu'à {{Mvar|k}} 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 K<sub>i</sub> ← {{Formule|&Phi;}}<sub>l</sub>(x)|x ∈ B <sub>je</sub> }
 (6) '''jusqu'à''' |K <sub>i</sub> |=|B <sub>i</sub> | '''et''' K<sub>i</sub>∩{j| <u>T[j]=k</u> }= ∅
 (7) '''soit''' σ(i):= le l réussi
 (8) '''pour tout''' j ∈ K<sub>i</sub> '''fixe'''r <u>T[j] ← T[j]+1</u>

=== Préservation de la commande ===
Une fonction de hachage parfait minimal {{Mvar|F}} ''préserve l'ordre'' si les clés sont données dans un certain ordre {{Formule|''a''<sub>1</sub>, ''a''<sub>2</sub>, ..., ''a''<sub>''n''</sub>}} et pour toutes les clés {{Formule|''a''<sub>''j''</sub>}} et {{Formule|''a''<sub>''k''</sub>}}, {{Formule|''j'' < ''k''}} implique {{Formule|''F''(''a''<sub>''j''</sub>) < F(''a''<sub>''k''</sub>)}}. 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 {{Formule|''Ω''(''n'' log ''n'')}} bits pour être représentées. 

== Constructions connexes ==
Une alternative simple au hachage parfait, qui permet également des mises à jour dynamiques, est le hachage cuckoo. Ce schéma envoie les clés à deux emplacements ou plus dans une plage (contrairement au hachage parfait qui envoie chaque clé à un seul emplacement) mais le fait de telle manière que les clés peuvent être attribuées une à une aux emplacements auxquels elles ont été envoyées. Les recherches avec ce schéma sont plus lentes, car plusieurs emplacements doivent être vérifiés, mais prennent néanmoins un temps constant dans le pire des cas. 

== Notes et références ==
{{références}}

== Bibliographie ==

* Richard J. Cichelli. ''Fonctions de hachage parfaites minimales simplifiées'', Communications de l'ACM, Vol. 23, numéro 1, janvier 1980.
* [[Thomas H. Cormen]], [[Charles E. Leiserson]], [[Ronald Rivest|Ronald L. Rivest]] et [[Clifford Stein]]. ''[[Introduction à l'algorithmique|Introduction aux algorithmes]]'', troisième édition. Presse du MIT, 2009.{{ISBN|978-0262033848}}. Section 11.5 : Hachage parfait, {{p.|267}}, –.
* Fabiano C. Botelho, Rasmus Pagh et Nivio Ziviani. [[arxiv:cs/0702159|" Hachage parfait pour les applications de gestion de données "]].
* Fabiano C. Botelho et Nivio Ziviani. [http://homepages.dcc.ufmg.br/~nivio/papers/cikm07.pdf "Hachage externe parfait pour les très grands ensembles de clés"]. {{16th}} ACM Conference on Information and Knowledge Management (CIKM07), Lisbonne, [[Portugal]], novembre 2007.
* Djamal Belazzougui, Paolo Boldi, Rasmus Pagh et Sebastiano Vigna. [https://web.archive.org/web/20140125080021/http://vigna.dsi.unimi.it/ftp/papers/MonotoneMinimalPerfectHashing.pdf "Hachage parfait minimal monotone: recherche d'une table triée avec des accès O (1)"]. Dans Actes du {{20e}} symposium annuel ACM-SIAM sur les [[mathématiques discrètes]] (SODA), New York, 2009. Presse ACM.
* Marshall D. Brain et Alan L. Tharp. "Hachage presque parfait de grands ensembles de mots". Logiciel—Pratique et expérience, vol. 19(10), 967-078, octobre 1989. John Wiley et fils.
* Douglas C. Schmidt, [http://www.dre.vanderbilt.edu/~schmidt/PDF/gperf.pdf GPERF : un générateur de fonction de hachage parfait], rapport C++, SIGS, vol. 10, {{n°|10}}, novembre/décembre 1998.

== Liens externes ==

* [https://www.gnu.org/software/gperf/ gperf] est un générateur de hachage parfait {{lang|en|[[open source]]}} C et C ++ (très rapide, mais ne fonctionne que pour de petits ensembles)
* [http://burtleburtle.net/bob/hash/perfect.html Hachage parfait minimal (algorithme bob)] par Bob Jenkins
* [http://cmph.sourceforge.net/index.html cmph] : C Minimal Perfect Hashing Library, implémentations open source pour de nombreux hachages parfaits (minimaux) (fonctionne pour les grands ensembles)
* [http://sux.di.unimi.it/ Sux4J] : hachage parfait minimal monotone open source en Java
* [https://web.archive.org/web/20130729211948/http://www.dupuis.me/node/9 MPHSharp] : méthodes de hachage parfaites en C#
* [https://github.com/rizkg/BBHash BBHash] : fonction de hachage parfaite minimale en C++ avec en-tête uniquement
* [https://github.com/rurban/Perfect-Hash Perfect::Hash], générateur de hachage parfait en Perl qui crée du code C. 
{{Portail|informatique}}

[[Catégorie:Algorithme de recherche]]
[[Catégorie:Hachage]]