Révision, fonction de hachage #

Map par hachage #

• put("abc", 12), on va faire:

  • utiliser la fonction de hachage pour obtenir l’indice correspondant à la clé "abc"

• get("abc"), on va faire:

  • utiliser la fonction de hachage pour obtenir l’indice correspondant à la clé "abc"

• collision

  • pour deux clés, la fonction de hachage retourne le même indice

• gérer les collisions

  • on utilise un map naïf pour chaque case du tableau

Fonction de hachage #

Utilisable / pas utilisable (valide / invalide) #

1. Inutilisable / invalide

   • utilise des données exterieure à la clé pour calculer l’indiced (p.ex. nom d’usager, heure de la journée, valeur aléatoire, etc.)

2. Utilisable / valide

   • la même clé est toujours associée au même indice

Bonne (efficace) Vs mauvaise (pas efficace) #

1. Bonne (effificace)

2. Mauvaise (pas efficace)

Inconvénient #

• espace mémoire vide

Avantage #

• efficace en terme de temps d’exécution