La table de hachage
Fonction de hachage, alvéoles, collisions et leurs deux résolutions (chaînage, sondage linéaire), facteur de charge et redimensionnement, coût moyen et pire cas, contrat entre égalité et hachage d'une clé.
- 25 cartes
- 5 thèmes
- Gratuit
Le programme, thème par thème
Le poids de chaque thème suit celui que lui donne l'examen.
- Notions
- Questions
- Les chiffres
- Mises en situation
- Comprendre
Quelques cartes du deck
Fonction de hachage : de quoi s'agit-il ?
Voir la réponse
Fonction qui transforme une clé en un entier, dont le reste modulo la taille de la table donne l'alvéole où la ranger.
Elle doit être déterministe (même clé, même valeur) et répartir les clés de façon uniforme. Avec
h(k) = k mod 7, la clé 24 va dans l'alvéole 3.Table de 7 alvéoles,
h(k) = k mod 7, sondage linéaire. On insère 10, 17 puis 3, dans cet ordre. Dans quelle alvéole va 3 ?- L'alvéole 5
- L'alvéole 3
- L'alvéole 4
- L'alvéole 6
Voir la réponse
L'alvéole 5
10 prend l'alvéole 3 ; 17 vise 3, prise, et va en 4 ; 3 vise 3, puis essaie 4, toutes deux prises, et s'arrête en 5.
Dans une table de hachage correctement dimensionnée, la recherche, l'insertion et le retrait coûtent … en moyenne et … au pire.
Voir la réponse
Dans une table de hachage correctement dimensionnée, la recherche, l'insertion et le retrait coûtent O(1) en moyenne et O(n) au pire.
Le pire cas arrive quand toutes les clés tombent dans la même alvéole : la table se réduit alors à une liste.
Alvéole : de quoi s'agit-il ?
Voir la réponse
Case de la table repérée par un indice, qui reçoit les clés dont le hachage mène à cet indice.
Le tableau de m alvéoles est la seule structure d'accès : on calcule l'indice, on regarde cette case, sans parcourir les autres.
Une table à sondage linéaire retire une clé en vidant simplement son alvéole. Ensuite, la recherche d'une autre clé, insérée après elle dans le même paquet, échoue. Quelle réparation ?
- Marquer l'alvéole « supprimée » au lieu de la vider
- Vider aussi les alvéoles suivantes du même paquet
- Changer la fonction de hachage pour éviter les collisions
- Chercher chaque clé à partir de l'alvéole 0
Voir la réponse
Marquer l'alvéole « supprimée » au lieu de la vider
La recherche s'arrête à la première alvéole vide : si le retrait en crée une au milieu d'un paquet, les clés suivantes deviennent invisibles. Une marque de suppression (tombstone) laisse la recherche continuer, et l'insertion peut la réutiliser.