Fonction de hachage parfait

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 h pour un ensemble S est une fonction de hachage qui associe des éléments distincts de S à un ensemble de m 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 S doit être connu pour la construction de la fonction de hachage parfait. Les fonctions de hachage parfait non dynamiques doivent être reconstruites si S change. Pour changer fréquemment 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 . 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. 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 S (ou d'autres valeurs associées) dans une table de correspondance indexée par les valeurs de sortie de la fonction.