Table de hachage : fonctionnement et limites
Comprenez comment une table de hachage retrouve une valeur, gère les collisions et peut perdre ses performances. Avec des règles pratiques pour vos projets.
Une table de hachage, c'est un tableau qui calcule son index
Une table de hachage permet de retrouver une valeur à partir d'une clé, sans avoir à parcourir toutes les entrées. Vous donnez un identifiant, une adresse électronique ou une chaîne de caractères : la table calcule où chercher. C'est ce qui fait qu'avec un bon réglage, une table avec un million d'entrées peut répondre aussi vite qu'une table avec dix entrées.
Mais cette vitesse n'est ni magique ni automatique. Elle dépend d'un tableau, d'une fonction de hachage et d'une façon de gérer les collisions. Si les clés sont mal réparties, si la table doit grossir trop souvent, ou si une clé change une fois insérée, les performances - et parfois le comportement observé - peuvent se dégrader.
Comprendre ces mécanismes aide à choisir la bonne structure, à éviter des bugs pénibles à diagnostiquer et à dimensionner correctement une collection quand l'usage compte vraiment. L'idée simple : la table calcule une position, regarde ce qu'il y a à cet endroit, puis s'appuie sur quelques hypothèses pour que l'ensemble reste rapide.
Pourquoi une table de hachage retrouve-t-elle une valeur sans tout parcourir
Le point de départ, c'est une opération très simple : accéder à une case d'un tableau par son indice. Pour obtenir l'élément numéro 5, l'ordinateur calcule son adresse à partir de l'adresse de départ, de l'indice et de la taille d'un élément. Il n'a pas besoin de vérifier les cases 0 à 4.
Dans le modèle classique, accéder à une position précise revient donc à un temps constant. La taille du tableau n'ajoute pas, à elle seule, une étape de recherche. C'est différent d'une liste non indexée : pour retrouver une valeur, il faut souvent examiner les éléments un par un.
Le problème des clés, pas celui des tableaux
Un tableau sait accéder à une position. Une application, elle, travaille rarement avec des indices choisis au hasard. Elle cherche plutôt la valeur associée à une clé : l'identifiant d'un utilisateur, un code produit, le nom d'un paramètre, etc.
La table de hachage fait le pont entre ces deux logiques. Elle transforme la clé en nombre, puis ce nombre en indice dans le tableau. Au lieu de parcourir toutes les clés, elle calcule directement où regarder.
Le modèle simplifié revient à trois étapes :
- Calculer le hachage de la clé.
- Convertir ce résultat en une position valide dans le tableau.
- Vérifier que la clé stockée à cette position correspond à celle qu'on cherche.
La troisième étape compte vraiment : la position trouvée indique où commencer, pas forcément où se trouve « une unique » entrée certaine. Plusieurs clés peuvent tomber au même endroit.
Ce que veut dire vraiment O(1)
On décrit souvent la lecture et l'insertion dans une table de hachage comme des opérations en O(1), c'est-à-dire à temps constant. En pratique, cela veut dire : le coût moyen ne dépend pas directement du nombre total d'entrées, si certaines conditions sont réunies. Ça ne veut pas dire que chaque appel fait exactement le même travail, ni que la table « ne fait rien ».
Une recherche implique au minimum le calcul du hachage et une ou plusieurs comparaisons de clés. Si les clés sont bien réparties et que la table a assez de place, ces comparaisons restent généralement limitées. La documentation Java le dit d'ailleurs clairement : les performances attendues des opérations de base supposent une dispersion correcte des éléments dans les compartiments.
Donc, en production, retenez plutôt : « rapide en moyenne si tout est bien réglé », pas « toujours constant ». Cette nuance explique les collisions, les redimensionnements et les ralentissements ponctuels qu'on peut voir à l'usage.
Que se passe-t-il lorsqu'il y a une collision
Une collision arrive quand deux clés différentes finissent dans le même compartiment. Ce n'est pas un cas rarissime : le nombre de clés possibles dépasse largement le nombre de positions dans la plupart des tables. Même une fonction de hachage bien choisie ne peut pas supprimer toutes les collisions.
Ensuite, la table doit garder la clé et sa valeur, puis vérifier la clé lors d'une recherche. Sans cette vérification, deux entrées au même indice seraient impossibles à distinguer. En bref : la collision ne casse pas le principe, elle ajoute du travail dans le compartiment concerné.
Chaînage : plusieurs entrées dans un compartiment
Avec le chaînage, chaque compartiment contient plusieurs paires clé-valeur, souvent via une petite structure de données. La recherche calcule le compartiment, puis parcourt ces entrées jusqu'à trouver une clé égale.
Si les clés sont bien réparties, chaque liste reste courte et le parcours coûte peu. Si beaucoup de clés tombent dans le même compartiment, le parcours s'allonge. Le temps dépend alors du nombre de collisions accumulées à cet endroit.
C'est simple à comprendre et ça tolère des ensembles où le nombre d'entrées dépasse celui des compartiments. En revanche, il faut des structures supplémentaires et des accès mémoire qui ne sont pas forcément « contigus ».
Adressage ouvert : chercher une autre case
Avec l'adressage ouvert, les entrées restent dans le tableau lui-même. Si la position calculée est déjà occupée par une autre clé, l'algorithme cherche d'autres positions selon une règle définie, jusqu'à trouver soit la clé recherchée, soit une case disponible.
Cette approche peut être plus compacte en mémoire, mais elle devient sensible au taux de remplissage. Quand la table est presque pleine, il faut parfois vérifier plusieurs positions avant de réussir ou de conclure que la clé n'est pas présente.
CPython, l'implémentation de référence de Python, utilise l'adressage ouvert pour ses dictionnaires. C'est un détail d'implémentation : ce n'est ni une garantie universelle, ni une règle que votre code devrait supposer valide dans tous les langages.
Dans les deux modèles, le raisonnement est le même : le hachage mène à une position (ou une zone), puis la table gère les conflits. La différence, c'est le coût des étapes supplémentaires introduites par cette gestion.
Quand les performances d'une table de hachage se dégradent-elles
En pratique, deux causes reviennent souvent quand on passe d'un accès rapide à un parcours plus coûteux : une table trop remplie et une mauvaise distribution des hachages. Il faut aussi garder en tête la stabilité des clés et les variations de durée lors des redimensionnements. Mélanger tous ces sujets rend le diagnostic flou ; autant regarder séparément la charge, la qualité du hachage et le comportement des clés.
Le facteur de charge et le coût des redimensionnements
Le facteur de charge correspond au rapport entre le nombre d'entrées et le nombre de compartiments. Quand il augmente, les collisions deviennent plus probables, et les recherches peuvent demander plus de comparaisons. La table surveille généralement un seuil et agrandit la capacité quand il est dépassé.
Le redimensionnement a un coût : la structure alloue un tableau plus grand, puis redistribue les entrées dans les nouveaux emplacements. Dans l'implémentation Java HashMap, par exemple, la capacité initiale et le facteur de charge par défaut sont souvent 16 et 0,75. Ça aide à illustrer un compromis, mais ce n'est évidemment pas une règle universelle pour toutes les collections.
La plupart des insertions restent rapides. Mais l'insertion qui déclenche une reconstruction peut être beaucoup plus lente que les précédentes. D'où l'idée de coût amorti : réparti sur beaucoup d'insertions, le coût moyen reste raisonnable, même si certains appels « isolés » sont nettement plus lourds.
Si vous connaissez à peu près la taille attendue d'une collection volumineuse, préallouer une capacité adaptée peut réduire le nombre de redimensionnements. Ce n'est pas forcément nécessaire : surallouer gaspille de la mémoire, et une estimation trop optimiste peut empirer les choses. Le mieux reste de mesurer ce qui se passe chez vous.
Les collisions accidentelles ou provoquées
Si toutes les clés finissent dans le même compartiment, une recherche peut devoir comparer chaque entrée. Dans ce cas, le coût ressemble beaucoup à une recherche linéaire : ajouter des éléments augmente directement le travail nécessaire pour retrouver une valeur.
Ça peut venir d'une fonction de hachage mal adaptée à votre domaine. Et il y a aussi un risque de sécurité : si des entrées contrôlées par un utilisateur sont insérées dans une structure vulnérable aux collisions, un attaquant peut essayer de provoquer beaucoup de collisions et transformer une requête normalement peu coûteuse en traitement lourd. À l'échelle d'un service, cela peut contribuer à un déni de service.
Python ajoute une valeur aléatoire au hachage de certains types (notamment les chaînes et les octets) au démarrage du processus. L'objectif est de compliquer la préparation de collisions exploitables à l'avance. Cette randomisation ne remplace pas un dimensionnement correct, une validation des entrées, ni une stratégie pour limiter les requêtes coûteuses.
Ordre, stabilité et choix de structure
Une table de hachage répartit les entrées en fonction de leur hachage, pas selon l'ordre d'insertion. Donc, à moins que votre langage ou la collection l'assure explicitement, il ne faut pas compter sur un ordre lors de l'itération.
En Python, l'ordre d'insertion des dictionnaires est garanti par le langage depuis Python 3.7. En Java, HashMap ne garantit pas cet ordre. Si l'ordre est une exigence (par exemple pour afficher des étapes dans une interface ou produire un export déterministe), choisissez une collection qui documente cette propriété plutôt que de « jouer avec » un comportement observé.
Avant d'opter pour une table de hachage, regardez donc trois choses : vos clés sont-elles stables ? vos données sont-elles réparties correctement ? et l'ordre compte-t-il pour votre application ? Si l'ordre ne compte pas, son absence n'est pas forcément un problème. Le souci, c'est quand votre code s'appuie implicitement sur une garantie que la structure ne donne pas.
Conclusion
Une table de hachage n'est pas une boîte noire : c'est un tableau dont l'indice est calculé à partir d'une clé. Quand les hachages se répartissent bien et que la capacité est adaptée, cela évite de parcourir toutes les entrées.
Mais les limites comptent autant que le principe : les collisions ajoutent des comparaisons, les redimensionnements créent des pics de coût, une clé modifiable peut devenir presque introuvable, et l'ordre n'est pas toujours garanti. Pour un usage fiable, gardez des clés stables, vérifiez les garanties de votre langage, et dimensionnez selon le volume réellement attendu. C'est ce qui transforme une structure « rapide » en choix prévisible dans votre application.
Comment une fonction de hachage transforme-t-elle une clé en emplacement
Une fonction de hachage prend une clé - chaîne, nombre, objet - et produit un nombre. Pour servir une table de hachage, elle doit satisfaire deux points concrets : une même clé doit donner le même résultat pendant la vie de la table, et des clés différentes doivent être réparties aussi uniformément que possible.
Par exemple, imaginons que le hachage d'une clé tombe sur 3 742 909, et que le tableau ait huit cases. Le reste de la division par huit vaut 5 : la table commence donc la recherche au compartiment 5. La table ne peut pas contenir autant de cases que le résultat du hachage : elle réduit ce résultat pour obtenir un indice utilisable.
Du hachage au compartiment
Un schéma pédagogique ressemble à ça :
À l'insertion, la table fait le même calcul avant de stocker la clé (et sa valeur). À la lecture, elle refait le calcul, puis compare la clé demandée avec celles présentes dans le compartiment obtenu. Le hachage sert à localiser une zone ; il ne remplace pas la vérification d'égalité.
Selon le langage et les bibliothèques, les détails changent : certaines implémentations gèrent des valeurs de hachage négatives, d'autres utilisent des opérations binaires plutôt qu'un modulo direct. Le principe reste le même : convertir un grand espace de résultats en une plage d'indices limitée.
Pourquoi la distribution compte
Une fonction de hachage qui produit des résultats « trop proches » pour des clés similaires peut concentrer les entrées dans quelques compartiments. Du coup, la table perd son avantage : au lieu de trouver vite une petite zone, elle doit y vérifier beaucoup d'entrées.
Une bonne dispersion ne veut pas dire zéro collision. Avec un nombre de cases limité et un grand nombre de clés possibles, les collisions sont inévitables. Le but est surtout d'éviter qu'elles se regroupent de façon catastrophique.
Autre point : il faut distinguer la fonction de hachage utilisée pour une table de hachage de celles utilisées en cryptographie. Pour répartir des clés dans une collection, on n'a pas besoin des mêmes propriétés de sécurité. Une fonction « standard » n'est donc pas un choix pertinent pour protéger des mots de passe ou garantir l'intégrité de données.
Une clé doit rester stable
Pour retrouver une entrée, la table doit recalculer le même hachage au moment de la recherche qu'à l'insertion. Si l'objet utilisé comme clé est modifié et que cette modification change son hachage, la table cherchera ailleurs. L'entrée, elle, restera rangée à l'ancienne position : elle devient alors difficile, voire impossible, à retrouver.
C'est pour ça que les clés doivent être immuables, ou au minimum ne pas changer sur les propriétés qui déterminent leur hachage et leur égalité. Les chaînes et les nombres sont souvent un bon choix. Pour un objet métier, définissez clairement ce qui fait « l'identité », puis assurez-vous que ces propriétés ne bougent pas pendant qu'il sert de clé.