Révision, fonction de hachage #

Fonctiond de hachage #

1. Fonction de hachage invalide

   • retourne pas nécessairement le même indice pour la même clé

2. Fonction de hachage valide, mais inefficace

   • beaucoup de collisions
   • différentes clés se voient souvent assiner le même indice

3. Fonction de hachage valide et efficace

   • pas beaucoup de collisions
   • différentes clés se voient souvent assigner différents indices

Qualités et défauts du mappage par hachage #

1. Qualités

   • O(1), efficace pour entreposer et récupérer une valeur (quand la fonction de hachage est bonne)

2. Défauts

   • utilise plus d’espace mémoire que requis par les valeurs
   • clés sont dans le désordre