Comment la complexité temporelle de l'opération d'ajout d'un élément dans une table de hachage est-elle déterminée?

La complexité temporelle de l'opération d'ajout d'un élément dans une table de hachage est généralement considérée comme amortie O(1). Cela signifie qu'en moyenne, l'ajout se fait en temps constant, car l'élément est immédiatement placé dans le seau correspondant selon le hachage. Cependant, dans le pire des cas, si une collision se produit (plusieurs éléments dans un même seau), ou lorsque la table doit être agrandie (ré-hachage), l'opération peut prendre O(n) temps, où n est le nombre d'éléments dans la table. Mais grâce à un bon hachage et au contrôle de la charge de la table, de tels cas sont rares.