À retenir
- Permet un accès aux données quasi instantané (complexité constante).
- Repose sur un couple Clé / Valeur.
- Transforme une clé textuelle ou complexe en un index numérique.
- Gère les collisions pour éviter les pertes de données.
Une table de hachage est une méthode d'organisation des données qui fonctionne comme un dictionnaire géant : elle associe une clé unique (par exemple, un nom d'utilisateur) à une valeur (ses informations de profil). Grâce à une fonction mathématique, elle permet de trouver instantanément l'emplacement d'une donnée sans avoir à parcourir toute la liste, un peu comme si un majordome savait exactement sur quelle étagère se trouve chaque objet dès que vous lui donnez son nom.
Étymologie
Le terme provient de l'anglais hash table. Le mot « hachage » fait référence à l'action de « hacher » ou transformer la donnée d'entrée (la clé) en un nombre (l'index) via une fonction de hachage. Le mot « table » renvoie à la structure de tableau utilisée pour stocker ces informations de manière ordonnée en mémoire.
Exemples d'usage
- Le type
dicten Python ouMapen JavaScript, qui permettent de stocker des paires clé-valeur. - Le système d'indexation d'une base de données pour retrouver un client par son identifiant unique en un clin d'œil.
- La gestion des sessions sur un site web, où un identifiant de session complexe est relié aux données de l'utilisateur.
Cas d'usage
On utilise les tables de hachage partout où la vitesse de recherche est cruciale. Elles interviennent dans la création de caches (pour ne pas recalculer des données coûteuses), dans la gestion des tables de symboles lors de la compilation d'un programme, ou encore dans les systèmes de fichiers pour localiser rapidement les données sur un disque.
Bonnes pratiques
Il est essentiel de choisir une fonction de hachage efficace qui répartit bien les données pour éviter les « collisions » (quand deux clés pointent vers le même emplacement). Il faut également surveiller le taux de remplissage : si la table est trop pleine, ses performances chutent, et il devient nécessaire de l'agrandir.
Synonymes
Antonymes
Conseil
Si vous débutez, considérez la table de hachage comme l'outil ultime pour optimiser vos algorithmes. Dès que vous vous surprenez à faire une boucle dans une boucle pour chercher une information, demandez-vous si l'utilisation d'un dictionnaire (ou map) ne résoudrait pas le problème beaucoup plus rapidement.
Questions fréquentes
Qu'est-ce qu'une collision ?
Une collision survient lorsque deux clés différentes, après être passées par la fonction de hachage, obtiennent le même index de rangement. La table doit alors utiliser des techniques (comme le chaînage) pour stocker les deux éléments au même endroit.
Est-ce que l'ordre des éléments est conservé ?
Traditionnellement non. Dans une table de hachage classique, l'ordre d'insertion n'est pas garanti car l'emplacement dépend du résultat du hachage, pas du moment où vous avez ajouté la donnée.