Quelle est la complexité de vérifier la présence d'un élément dans un ensemble dans le pire cas, lorsque tous les éléments ont le même hash?

Dans le pire des cas, lorsque tous les éléments d'un ensemble ont un hachage identique, la structure de données, généralement implémentée sous forme de table de hachage, se dégrade en une liste chaînée. Cela se produit parce que tous les éléments tombent dans une même case (bucket).

Dans ce cas, vérifier la présence d'un élément nécessite de parcourir tous les éléments de cette case, ce qui donne une complexité de O(n), où n est le nombre d'éléments dans l'ensemble.

Ainsi, dans le pire des cas, la recherche d'un élément dans un ensemble est une recherche linéaire dans la liste, et non un temps constant comme dans le cas moyen.