Fonction de hachage parfaite

En informatique , une fonction de hachage parfaite fonction de hachage qui associe à chaque élément distinct de collision . Mathématiquement, il s'agit d'une fonction injective .

Les fonctions de hachage parfaites permettent d'implémenter une table de consultation avec un temps d'accès constant dans le pire des cas . Comme toute fonction de hachage, une fonction de hachage parfaite peut servir à implémenter des tables de hachage , avec l'avantage de ne nécessiter aucune gestion des collisions . De plus, si les clés ne figurent pas dans les données et si l'on sait que les clés interrogées seront valides, il est inutile de les stocker dans la table de consultation, ce qui permet de gagner de l'espace.

L'inconvénient des fonctions de hachage parfaites est qu'il est nécessaire de connaître la structure des fonctions de hachage parfaites dynamiques, moyennant un espace mémoire supplémentaire. L'espace mémoire requis pour stocker une fonction de hachage parfaite est en table de consultation indexée par la sortie de la fonction. On peut alors vérifier la présence d'une clé dans temps constant dans le pire des cas . Grâce au hachage parfait, les données associées peuvent être lues ou écrites en un seul accès à la table.

Les paramètres de performance importants pour un hachage parfait sont la taille de la représentation, le temps d'évaluation, le temps de construction et, de plus, la contrainte de plage (nombre moyen de compartiments par clé dans la table de hachage). Le temps d'évaluation peut être aussi rapide que algorithme randomisé en un nombre d'opérations proportionnel à la taille de S. La construction originale de univers dont

Si temps polynomial en choisissant aléatoirement des valeurs jusqu'à en trouver une qui convienne.

La fonction de hachage elle-même nécessite un espace de stockage

bits/clé.

Pour les fonctions de hachage parfaites, on suppose d'abord que l'ensemble des valeurs de univers dont la taille

bits/clé, moins hachage parfait dynamique , mais ces méthodes sont relativement complexes à implémenter.

Une fonction de hachage parfaite minimale est une fonction de hachage parfaite qui associe injectivité ) et s’il existe un entier

Une fonction de hachage est dite pseudocode adapté ci-dessous :

(4) pour tout i 

Bien que les tables de hachage bien dimensionnées présentent un temps d'exécution moyen amorti de O(1) (temps constant moyen amorti) pour les recherches, les insertions et les suppressions, la plupart des algorithmes de tables de hachage souffrent de temps d'exécution dans le pire des cas potentiellement beaucoup plus longs. Un temps d'exécution dans le pire des cas de O(1) (temps constant même dans le pire des cas) serait préférable pour de nombreuses applications (notamment les routeurs réseau et les caches mémoire ).

Peu d'algorithmes de tables de hachage permettent un temps de recherche O(1) dans le pire des cas (temps de recherche constant même dans le pire des cas). Parmi ceux-ci, on peut citer : le hachage parfait ; le hachage parfait dynamique ; le hachage coucou ; le hachage marelle ; et le hachage extensible .

Une alternative simple au hachage parfait, qui permet également les mises à jour dynamiques, est le hachage coucou . Ce schéma associe les clés à deux emplacements ou plus dans une plage (contrairement au hachage parfait qui associe chaque clé à un seul emplacement), mais de telle sorte que les clés puissent être assignées un à un aux emplacements auxquels elles ont été associées. Les recherches avec ce schéma sont plus lentes, car plusieurs emplacements doivent être vérifiés, mais leur temps d'exécution dans le pire des cas reste constant.