Chaque fois que vous écrivez d["key"], une table de hachage est à l'œuvre. Le principe est simple : convertir la clé en un nombre, utiliser ce nombre comme index dans un tableau, puis accéder directement à la donnée.
Les collisions sont inévitables
L'espace des clés étant infini et les tableaux finis, il existe forcément deux clés différentes qui correspondent au même index. Il existe deux approches courantes pour gérer cela :
- Ajout à la liste : chaque case contient une liste ; en cas de collision, on ajoute l'élément à cette liste
- Recherche linéaire : si la case est déjà occupée, rechercher la case libre suivante
La deuxième méthode, plus respectueuse de la mémoire cache du processeur, est donc couramment utilisée dans les bibliothèques modernes, même si la suppression d'un élément s'avère plus complexe.
Le coefficient de charge détermine la vitesse
Le coefficient de charge correspond au rapport entre le nombre d'éléments et le nombre de cellules. Lorsqu'il dépasse un certain seuil — généralement autour de 0,7 —, le nombre de collisions augmente considérablement et les recherches deviennent plus lentes. À ce moment-là, le tableau doit allouer un nouveau tableau deux fois plus grand, puis procéder à un hachage complet.
L'insertion déclenchant un nouveau hachage peut être des milliers de fois plus lente que la normale. En moyenne, cela reste une constante, mais si vous développez un système sensible à la latence, ce surcoût peut vous être fatal.
Quelques conseils pratiques
- Si vous connaissez à l'avance le nombre d'éléments, allouez la capacité dès le départ pour éviter de devoir effectuer plusieurs hachages
- La clé doit être immuable — modifier la clé après l'insertion entraîne la perte de l'élément, car la valeur de hachage a changé
- La table de hachage ne préserve pas l’ordre d’insertion, sauf si le langage le garantit ; ne vous fiez pas à l’ordre observé par hasard
Thảo luận