Cours complet : Dictionnaires et tables de hachage
Les dictionnaires sont des structures de donnees associatives qui permettent de stocker des paires clé-valeur et d'acceder rapidement a une valeur a partir de sa clé. Ils reposent en interne sur le mecanisme de hachage, qui transforme une clé en indice de tableau.
Une table de hachage utilise une fonction de hachage pour transformer une clé en indice dans un tableau. Ce mecanisme permet un acces en O(1) en moyenne, ce qui en fait une structure extremement efficace pour la recherche, l'insertion et la suppression.
Les collisions, situation ou deux clés produisent le meme indice, sont inevitables et doivent etre gerees par des strategies specifiques : le chainage externe (listes chainees a chaque case) ou l'adressage ouvert (recherche d'une case libre).
Comprendre le fonctionnement interne des dictionnaires, la notion de collision, les strategies de résolution et le facteur de charge est fondamental en informatique. Le type dict de Python, omnipresent dans le langage, est implemente comme une table de hachage optimisee.
Prérequis
- Notion de tableau et d'indice
- Listes chainees (pour le chainage externe)
- Notion de complexite algorithmique O(1), O(n)
- Objets immuables vs mutables en Python
1. Principe du hachage
Le hachage consiste a transformer une donnee de taille quelconque en un entier de taille fixe grace a une fonction de hachage. Cet entier sert d'indice dans un tableau pour stocker ou retrouver la valeur associée a la clé. L'idee fondamentale est de calculer directement la position de stockage plutot que de chercher sequentiellement.
Une bonne fonction de hachage doit etre deterministe (meme entree produit toujours la meme sortie), rapide a calculer, et distribuer uniformement les clés dans le tableau pour minimiser les collisions. Une mauvaise distribution concentre les clés dans quelques cases et degrade les performances.
En Python, la fonction hash() retourne le hash d'un objet. Seuls les objets immuables (int, str, tuple d'immuables) sont hachables. Les listes et dictionnaires, etant mutables, ne peuvent pas servir de clés car leur hash pourrait changer apres modification, rendant la clé introuvable dans la table.
L'indice dans le tableau est généralement obtenu par hash(clé) % taille_tableau. La taille du tableau est choisie pour equilibrer la consommation memoire et le taux de collisions. Plus le tableau est grand, moins il y a de collisions, mais plus la memoire est gaspillee.
Méthode — Implementer une table de hachage simple
- Creer un tableau de taille fixe (par ex. 10 cases), chaque case etant une liste vide
- Pour inserer (clé, valeur) : calculer indice = hash(clé) % taille
- Ajouter la paire (clé, valeur) dans la liste a l'indice calcule
- Pour rechercher : calculer l'indice puis parcourir la liste a cet indice
- Pour supprimer : trouver et retirer la paire de la liste
Exemple : On dispose d'une table de hachage de taille 7. Inserer les clés suivantes avec h(clé) % 7 : h('alice')=3, h('bob')=5, h('charlie')=3, h('diana')=1. Montrer l'état de la table avec chainage externe.
- Insertion de 'alice' : h('alice') % 7 = 3. Table[3] = [('alice', val)]
- Insertion de 'bob' : h('bob') % 7 = 5. Table[5] = [('bob', val)]
- Insertion de 'charlie' (collision) : h('charlie') % 7 = 3. Collision avec 'alice'. Table[3] = [('alice', val), ('charlie', val)]
- Insertion de 'diana' : h('diana') % 7 = 1. Table[1] = [('diana', val)]
- état final : Table[0]=[], Table[1]=[('diana',val)], Table[2]=[], Table[3]=[('alice',val),('charlie',val)], Table[4]=[], Table[5]=[('bob',val)], Table[6]=[]
⚠️ Attention : En Python, les listes et dictionnaires sont mutables et donc NON hachables. On ne peut pas les utiliser comme clés de dictionnaire. Utiliser des tuples (immuables) a la place.
2. Gestion des collisions
Une collision survient quand deux clés differentes produisent le meme indice apres hachage. C'est inevitable quand le nombre de clés possibles depasse la taille du tableau (principe des tiroirs de Dirichlet).
Le chainage externe resout les collisions en stockant a chaque case du tableau une liste chainee contenant toutes les paires (clé, valeur) ayant le meme indice. La recherche parcourt la liste a l'indice correspondant. En moyenne, si les éléments sont bien distribues, chaque liste a une longueur de n/taille, d'ou un acces moyen en O(1 + n/taille).
L'adressage ouvert resout les collisions en cherchant une autre case libre dans le tableau selon une sequence de sondage. Le sondage linéaire teste les cases consecutives (i+1, i+2, ...). Le sondage quadratique teste i+1, i+4, i+9, ... Le double hachage utilise une seconde fonction pour calculer le pas de sondage.
Le facteur de charge (nombre d'éléments / taille du tableau) mesure le remplissage. Quand il depasse un seuil (souvent 0.75 en Python), le tableau est redimensionne (généralement double) et tous les éléments sont re-haches dans le nouveau tableau plus grand pour maintenir les performances. Cette opération de rehachage est en O(n) mais est suffisamment rare pour etre amortie.
Méthode — résoudre une collision par chainage externe
- Calculer l'indice : i = hash(clé) % taille
- Acceder a la liste chainee a table[i]
- Parcourir la liste pour vérifier si la clé existe deja
- Si oui : mettre a jour la valeur
- Si non : ajouter la paire (clé, valeur) en fin de liste
Exemple : Dans une table de taille 5 avec adressage ouvert (sondage linéaire), inserer les clés dont les hash modulo 5 sont : A->2, B->2, C->2, D->4. Montrer l'état de la table.
- Insertion de A : h(A) = 2. Table[2] est vide. Table[2] = A
- Insertion de B (collision) : h(B) = 2. Table[2] est occupee par A. Sondage linéaire : Table[3] est vide. Table[3] = B
- Insertion de C (collision) : h(C) = 2. Table[2] occupee, Table[3] occupee. Table[4] est vide. Table[4] = C
- Insertion de D (collision) : h(D) = 4. Table[4] est occupee par C. Table[0] est vide (sondage circulaire). Table[0] = D
⚠️ Attention : O(1) est la complexite MOYENNE, pas le pire cas. Si toutes les clés collisionnent (meme indice), la complexite degene en O(n). C'est pourquoi la fonction de hachage et le facteur de charge sont cruciaux.
3. Les dictionnaires Python
Le type dict de Python est implemente comme une table de hachage hautement optimisee. L'acces, l'insertion et la suppression sont en O(1) en moyenne. Dans le pire cas (toutes les clés collisionnent), ces opérations sont en O(n), mais cela est extremement rare avec une bonne fonction de hachage.
Les opérations principales sont : d[clé] = valeur (insertion ou modification), d[clé] (acces, leve KeyError si absent), del d[clé] (suppression), clé in d (test d'appartenance en O(1) moyen), d.keys() (les clés), d.values() (les valeurs), d.items() (les paires clé-valeur).
Les dictionnaires Python maintiennent l'ordre d'insertion depuis Python 3.7 (garanti par la specification). Attention : cet ordre n'est pas un tri, c'est simplement l'ordre dans lequel les clés ont ete ajoutees. Pour un parcours trie, il faut utiliser sorted(d).
La méthode get(clé, defaut) evite les KeyError en fournissant une valeur par defaut si la clé n'existe pas. Les comprehensions de dictionnaires {k: v for k, v in ...} permettent de creer des dictionnaires de maniere concise et sont tres utilisees en Python idiomatique.
Méthode — Compter les occurrences avec un dictionnaire
- Creer un dictionnaire vide : compteur = {}
- Parcourir chaque élément de la sequence
- Pour chaque élément, utiliser get pour obtenir le comptage actuel (0 par defaut)
- Incrementer : compteur[elem] = compteur.get(elem, 0) + 1
- Le dictionnaire contient les occurrences de chaque élément
Exemple : écrire une fonction qui prend une chaine de caracteres et retourne un dictionnaire contenant le nombre d'occurrences de chaque lettre. Appliquer a 'abracadabra'.
- Initialisation : compteur = {}
- Parcours et comptage : Pour chaque lettre de 'abracadabra' : compteur['a'] = 0+1 = 1, puis 2, 3, 4, 5 compteur['b'] = 0+1 = 1, puis 2 compteur['r'] = 0+1 = 1, puis 2 compteur['c'] = 0+1 = 1 compteur['d'] = 0+1 = 1
- Code : def compter_lettres(texte): compteur = {} for lettre in texte: compteur[lettre] = compteur.get(lettre, 0) + 1 return compteur
- résultat : compter_lettres('abracadabra')
⚠️ Attention : Le dictionnaire Python conserve l'ordre d'insertion (depuis 3.7) mais ce n'est PAS un tri. Ne pas confondre ordre d'insertion et ordre alphabetique/numerique.
4. Complexite et limites
La complexite en moyenne d'une table de hachage est O(1) pour la recherche, l'insertion et la suppression. C'est son avantage majeur par rapport aux tableaux tries (O(log n) en recherche par dichotomie) et aux listes chainees non triees (O(n) en recherche).
Dans le pire cas, si toutes les clés collisionnent (par exemple si la fonction de hachage est mauvaise), la complexite degene en O(n) car on se retrouve essentiellement avec une seule liste chainee. C'est pourquoi le choix de la fonction de hachage et la gestion du facteur de charge sont cruciaux.
Les tables de hachage ne permettent pas un parcours ordonne des clés (sauf si elles sont triees separement). Pour des opérations necessitant un ordre (minimum, maximum, parcours croissant), un arbre binaire de recherche equilibre est preferable car il offre O(log n) pour toutes les opérations tout en maintenant l'ordre.
La consommation memoire d'une table de hachage est supérieure a celle d'un simple tableau car le tableau sous-jacent doit etre surdimensionne pour maintenir un facteur de charge faible et minimiser les collisions. C'est le compromis classique temps-memoire en informatique.
Méthode — Choisir entre table de hachage et arbre de recherche
- Si besoin d'acces en O(1) sans ordre : table de hachage (dict)
- Si besoin de parcours ordonne (min, max, tri) : arbre de recherche
- Si les clés sont immuables : dict possible
- Si les clés sont mutables : impossible avec dict, utiliser une autre structure
- Si la memoire est critique : un tableau trie peut etre plus economique
Exemple : Comparer les complexites de recherche d'un élément dans : (a) un tableau non trie, (b) un tableau trie, (c) une table de hachage. Conclure sur le choix de structure.
- Tableau non trie : Recherche linéaire : parcourir élément par élément.
- Tableau trie : Recherche dichotomique : diviser l'espace de recherche par 2 a chaque étape.
- Table de hachage : Calcul de l'indice par hash puis acces direct (en moyenne).
- Comparaison numerique : Pour n = 1 000 000 éléments : Tableau non trie : ~1 000 000 comparaisons Tableau trie : ~20 comparaisons (log2(10^6) ≈ 20) Table de hachage : ~1 acces
⚠️ Attention : Ne pas confondre hash (hachage pour stockage en O(1)) et chiffrement (securite). La fonction hash() de Python n'est PAS une fonction cryptographique.
Conclusion
Les dictionnaires et tables de hachage offrent un acces en O(1) en moyenne grace au mecanisme de hachage. La gestion des collisions (chainage externe ou adressage ouvert) et le facteur de charge sont essentiels pour maintenir les performances. En Python, le type dict est omnipresent et constitue un outil fondamental. L'essentiel au BAC est de comprendre le fonctionnement interne, les complexites moyennes et pire cas, et les contraintes sur les clés (immuabilite).
Mots-clés