Révision, fonction de hachage #

Map par hachage #

• Pour faire put(cle, ...), je trouve un indice dans la table

• Pour faire plusieurs put() avec différentes clés, on essaie de répartir sur plusieurs indices

• Si je dois aller 2 fois dans le même indice: collision

  • en cas de collision, on peut utiliser un map naif

Fonctione de hachage #

1. L’idée est de trouver un incide à partir de clé
   • avec l’indice on va aller dans la table

Utilisable (valide) / pas utilisable (pas valide) #

1. Utilisable: indice utilisé pour le le put(cle,...) doit être le même re-caculé plus tard pour le get(cle)

2. Utilisable: on calcule l’indice uniquement avec les informations de la clé.

3. Pas utilisable: on pas toujours le même indice pour la même clé.

4. Pas utilisable: si on calcule l’indice avec du hasard ou encore une information externe à la clé (heure de la journée, nom de l’usager, etc).

Bonnes (efficace) #

1. Si la fonction de hachage va placer / distribuer les éléments un peu partout

Mauvaises (pas efficace) #

1. Si la fonction retourne toujours le même indice

Avantages / inconvénients du Map Hash #

1. Avantages

   • Efficacité: temps constant O(1) pour put/get

2. Inconvénient

   • Prend plus espace mémoire que réellement nécessaire