Révision, fonction de hachage #

Fonction de hachage #

1. Calculer un indice (entier) à partir de la clé (qui pourrait être une chaîne)

2. Fonction de hachage valide

   • indice est uniquement fonction de la clé
   • pour la même clé, la fonction retourne toujours le même indice

3. Fonction de hachage invalide

   • utilise des données extérieurs à la clé (nom d’usager, date, hasard)

4. Fonction de hachage efficace

   • on disperse le plus possible les valeurs dans la table de hachage
   • pour deux clés différentes, forte probabilité d’avoir des indices différents

5. Fonction de hachage pas efficace

   • trop souvent le même indices
   • trop forte probabilité de collision (même indice pour deux clés différentes)

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

1. Avantage: put/get en temps constant (ou presque)

2. Inconvénient: espace mémoire inutilisée