Révision, fonction de hachage #

Fonction de hachage #

1. Fonction de hachage invalide

   • je donne la même clé deux fois, et ça retourne des indices différents

2. Fonction de hachage valide, mais inefficace

   • pour n’importe quelle clé, ça retourne toujours le même indice
   • beacoup de collisions

3. Fonction de hachage valide et efficace

   • éparpillé dans le tableau
   • deux clés différentes ont une forte chance d’avoir des indices différents
   • éviter les collisions

Qualités et défauts de la table de hachage (par rapport au MapNaif) #

1. Qualités

   • efficace => si tout va bien, c’est O(1) pour put et get (temps constant)

2. Défauts

   • prends plus d’espace mémoire qu’on a de valeurs
   • pas un bon candidat pour une BD