Révision, fonction de hachage #

Map par hachage #

• J’obtiens une paire (clé,valeur)

  • trouver l’indice dans la table où mettre la clé
  • mettre la valeur à côté de la clé

• J’obtiens plusieurs paires (clé, valeur)

  • j’essaie de mettre les clés à différents endroit dans le tableau

• Si deux clés vont au même endroit, j’utilise des listes (ou un MapNaif) pour gérer la collision

Fonction de hachage #

C’est quoi #

1. C’est le bout de code qui reçoit la clé et qui
   • l’indice dans la table de hachage où mettre la paire clé/valeur

Utilisable / pas utilisable (valide / invalide) #

1. Inutilisable / invalide

   • indice aléatoire
   • si l’indice donné dépend d’une information autre que la clé
     • l’heure de la journée, le nom de l’usager, etc.

2. Utilisable / valide

   • calculer l’indice uniquement avec la clé (pas de hasard ou d’information externe)

   • un put avec une clé doit absolument utiliser le même indice qu’un get avec cette clé

Bonne (efficace) Vs mauvaise (pas efficace) #

1. Bonne (effificace)

   • dépend seulement de la clé (utilisable)
   • évite les collisions (souvent donne différents indices pour différentes clés)
   • éparpille ou distribue les clés un peu partout dans la table

2. Mauvaise (pas efficace)

   • dépend seulement de la clé (utilisable)
   • donne toujours le même indice
   • s’en va toujours au même endroit dans le tableau

Avantages / inconvénients du Map par hachage #

Avantages #

1. Avec une bonne fonction de hachage, c’est temps constant O(1) pour retrouver une clé

Inconvénients #

1. Utilise plus d’espace mémoire que réellement nécessaire