Complexité de la recherche HashSet ?

Question

Une opération de recherche OU contains pour un seul peut être O(n) dans le pire des cas, n'est-ce pas ? Donc, pour n éléments recherchés dans hashSet seront O(n^2) ?

Answer 1

Oui, mais c'est vraiment le pire des cas : si tous les éléments du HashSet ont le même code de hachage (ou un code de hachage menant au même bucket). Avec un hashCode correctement écrit et un échantillon de clé normalement distribué, une recherche est O(1).

Answer 2

Oui, mais la raison pour laquelle nous avons des HashSets est que nous rencontrons ce pire des cas avec une probabilité très, très faible, et c'est généralement beaucoup plus rapide que le nlogn garanti pour un tas ou un TreeSet (auto-équilibré), ou le n^2 garanti pour une liste non triée.

Answer 3

lookp prend O(c)

c = valeur constante