Combien de temps prend la recherche (par exemple, en utilisant la méthode contains) dans les collections List et Set?

Pour List, la recherche utilisant contains a une complexité de calcul de O(n), où n est le nombre d'éléments dans la liste. Cela est dû au fait que, dans le pire des cas, il faut parcourir tous les éléments de la liste pour déterminer si l'élément recherché est présent.

Pour Set, la recherche utilisant contains a une complexité moyenne de O(1). Cela est réalisé grâce à l'utilisation d'une table de hachage pour le stockage interne des éléments. Dans le cas idéal (bonne fonction de hachage et absence de collisions), la recherche prend un temps constant. Dans le pire des cas (beaucoup de collisions), la complexité peut se rapprocher de O(n), mais cela est rare en pratique.