Redimensionnement
Pourquoi le redimensionnement est nécessaire ?
Lorsque nous ajoutons des éléments à un dictionnaire, la table de hachage peut finir par manquer d’espace. Si nous continuons à ajouter des éléments sans augmenter la taille de la table de hachage, nous finirons par avoir de nombreuses collisions de hachage, ce qui ralentira les opérations de recherche, d’insertion et de suppression.
Pour éviter cela, on augmente donc la taille de la table de hachage lorsque le nombre d’éléments atteint un certain seuil. Cela permet de maintenir un faible taux de remplissage de la table de hachage, ce qui minimise le nombre de collisions de hachage et permet d’obtenir des performances optimales.
Méthode : Et comment on redimensionne ?
Lorsque le nombre d’éléments dans un dictionnaire dépasse un certain seuil, on crée une nouvelle table de hachage de taille plus grande. On parcourt ensuite tous les éléments de l’ancienne table de hachage et les insère dans la nouvelle table de hachage. C'est tout.
Attention : Mais c'est long à faire !
Il est important de noter que le redimensionnement d’une table de hachage est une opération coûteuse, car elle nécessite la création d’une nouvelle table de hachage et le repositionnement de tous les éléments. Cependant, puisque le redimensionnement double généralement la taille de la table de hachage, le nombre de redimensionnements nécessaires est logarithmique par rapport au nombre d’éléments insérés. Cela signifie que le coût du redimensionnement est amorti sur un grand nombre d’opérations d’insertion, de sorte que le coût moyen par opération reste constant.