informatique (tronc commun des prépas scientifiques) · Chapitre 17 · Application directe du cours
Une table à la main
Les dictionnaires dévoilés : le hachage · niveau 1 (application)
É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).
Exercices semblables
- Le redimensionnement et son coût amorti corrigé
- L'ensemble, dictionnaire sans valeurs corrigé
- Étude — l'index des mots, de bout en bout corrigé
- Hachable ou pas ? corrigé
- Parcours et retournement corrigé