Les dictionnaires dévoilés : le hachage
Cours · informatique (tronc commun des prépas scientifiques), chapitre 17 · prépas scientifiques, tronc commun · le début du chapitre, la suite sur Adloun
17.1 Introduction et motivation
Depuis le chapitre 2, le dictionnaire est notre meilleur allié — comptages, déjà-vu, index, mémoires de toutes sortes — et nous l'utilisons sur parole : insertion, recherche et suppression « en ». Une promesse stupéfiante, à y regarder de près : retrouver une clé parmi un million sans en examiner qu'une poignée, là où la liste exige et le tableau trié avec l'obligation de rester trié. Ce chapitre ouvre enfin la boîte noire : le mécanisme s'appelle le hachage, et c'est l'une des plus belles idées de l'informatique — transformer la clé elle-même en adresse, pour que la donnée dise où elle habite.
Comprendre le mécanisme n'est pas un luxe de curiosité : il explique les conditions du contrat. Pourquoi une liste ne peut-elle pas servir de clé (TypeError: unhashable type) ? Pourquoi le est-il « en moyenne » et que devient-il dans le pire cas ? Pourquoi l'ordre d'un dictionnaire ne doit-il rien au hasard ni au tri ? Toutes ces questions ont la même réponse, et elle tient en une image : des casiers, une règle d'adressage, et l'art de gérer les inévitables collisions.
17.2 L'idée du hachage
17.2.1 La clé devient adresse
Une table de hachage range ses données dans un tableau de cases appelées alvéoles (buckets). Une fonction de hachage transforme chaque clé en un entier, et la clé est rangée dans l'alvéole d'indice
Chercher une clé refait le même calcul et va voir directement dans la bonne alvéole : ni parcours, ni tri — un calcul arithmétique et un accès de tableau, si l'alvéole est peu peuplée. En Python, la fonction de hachage est hash :
>>> hash(42), hash("info"), hash((3, "a"))
(42, 4949054158308671837, 3068460814) # valeurs indicatives : voir plus bas