Êtes-vous un étudiant de l'EPFL à la recherche d'un projet de semestre?
Travaillez avec nous sur des projets en science des données et en visualisation, et déployez votre projet sous forme d'application sur Graph Search.
Concept
Fonction de hachage parfait
Résumé
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.
Source officielle
À propos de ce résultat
Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.