Qu'est-ce qu'une collision de hachage et quels sont les méthodes pour la résoudre?

Une collision de hachage se produit lorsque deux valeurs d'entrée différentes donnent la même valeur de fonction de hachage. C'est inévitable, car l'ensemble des entrées possibles est généralement plus grand que l'ensemble des valeurs de hachage possibles.

Méthodes pour résoudre les collisions :

1. Adresse ouverte — en cas de collision, la prochaine cellule libre est recherchée selon une certaine séquence (sondage linéaire, quadratique, double hachage).
2. Chaînages — chaque cellule de la table de hachage contient une liste chaînée de tous les éléments avec la même valeur de hachage.
3. Rehachage — en cas de collision, une autre fonction de hachage est utilisée.

Exemple avec chaînages en Python :

table_de_hachage = [[] for _ in range(10)]

def inserer(cle, valeur):
    index = hash(cle) % 10
    table_de_hachage[index].append((cle, valeur))

inserer('pomme', 1)
inserer('mopp', 2)  # collision possible