Révision, fonction de hachage #

Fonction de hachage #

1. Fonction de hachage invalide

   • génère un premier indice pour une clé
   • entrepose une valeur à cet indice
   • génère un autre indice pour la même clé
   • maintenant impossible de récupérer la valeur

2. Fonction de hachage valide, mais inefficace

   • beaucoup de collisions
   • beaucoup de clés assignées au même indice

3. Fonction de hachage valide et efficace

   • pas beaucoup de collisions
   • deux clés différentes ont de forte chance d’avoir des indices différents

Qualités et défauts d’un mappage par hachage #

1. Qualités

   • accès direct à l’emplacement dès qu’on connaît la clé
   • O(1), temps constant pour accéder à une valeur

2. Défauts

   • il y a toujours des collisions
   • prends plus d’espace mémoire que requis par les valeurs
   • les clés sont éparpillées, pas dans un ordre
   • long de trouver une valeur (vrai pour tous les maps)