Une table à la main
Exercice · informatique (tronc commun des prépas scientifiques), chapitre 17 — Les dictionnaires dévoilés : le hachage
Énoncé
Avec alvéoles et somme des codes ASCII des caractères (ord) : insérer successivement "as" (somme ), "sa" (somme ), "or" (somme ), "ro" (somme ), "un" (somme ). Donner l'état des alvéoles, recenser les collisions, et calculer le coût (en comparaisons de clés) d'une recherche de "sa", de "un", et de "il" (somme , absent).
Corrigé
Calculons les indices des alvéoles pour chaque mot inséré :
"as":"sa": (collision avec"as")"or":"ro": (collision avec"or")"un": (collision avec"as"et"sa")
État final de la table :
- Alvéole 0 :
[["or", ...], ["ro", ...]] - Alvéole 1 : vide
[] - Alvéole 2 :
[["as", ...], ["sa", ...], ["un", ...]] - Alvéole 3 : vide
[] - Alvéole 4 : vide
[]
Coût des recherches (en nombre de comparaisons de clés) :
- Recherche de
"sa": l'indice est . On parcourt la liste de l'alvéole 2. On compare"sa"à"as"(échec), puis"sa"à"sa"(succès). Coût : 2 comparaisons. - Recherche de
"un": l'indice est 2. On compare à"as", puis"sa", puis"un". Coût : 3 comparaisons. - Recherche de
"il": l'indice est . L'alvéole 3 est vide, la recherche s'arrête immédiatement. Coût : 0 comparaison.
Remarque : On constate un fort déséquilibre (5 clés réparties sur seulement 2 alvéoles). La fonction de hachage par simple somme de caractères est médiocre car elle ne prend pas en compte l'ordre des lettres (les anagrammes comme "as"/"sa" et "or"/"ro" entrent systématiquement en collision).
Les autres exercices de ce chapitre Le cours du chapitre
Un blocage sur cet exercice ? Le tuteur d'Adloun guide par questions, sans donner la réponse.