Collision de hachage
Définition : Qu'est-ce qu'une collision de hachage ?
Une collision de hachage se produit lorsque deux clés différentes produisent le même hash. Cela peut poser un problème car notre table de hachage dépend de l’unicité des hashes pour retrouver rapidement les valeurs associées à une clé donnée. Si deux clés différentes ont le même hash, alors la deuxième clé insérée écraserait la première.
Nous verrons dans ce cours deux implémentations différentes pour gérer les collisions.
Complément : Comment Python gère les collisions de hachage ?
Python utilise une méthode appelée « linear probing » pour gérer les collisions de hachage. Plus précisément, il utilise une variante du linear probing appelée « random probing ».
Lorsqu’une collision se produit, Python essaie de placer la deuxième clé à la position suivante dans la table de hachage. Si cette position est également occupée, il essaie la position suivante, et ainsi de suite, jusqu’à ce qu’il trouve une position libre.
Cela signifie que lors de la recherche d’une clé, Python peut avoir à parcourir plusieurs positions dans la table de hachage jusqu’à ce qu’il trouve la clé recherchée. Cependant, en pratique, les collisions sont relativement rares et la taille de la table de hachage est généralement beaucoup plus grande que le nombre d’éléments qu’elle contient, de sorte que le nombre moyen de positions que Python doit vérifier reste très faible.
Fondamental : Comment nous on gère les collisions de hachage ?
Une autre méthode pour gérer ces collisions existe et s'appelle « chaînage ».
Avec cette méthode, chaque position dans la table de hachage est associée à une liste chaînée de paires clé-valeur. Lorsqu’une collision se produit (c’est-à-dire que deux clés différentes produisent le même hash), la nouvelle paire clé-valeur est simplement ajoutée à la fin de la liste chaînée.