¿Complejidad de búsqueda de HashSet?

Question

Una operación de búsqueda O contains para uno solo puede ser O(n) en el peor de los casos, ¿verdad? Por lo tanto, para elementos n buscar en hashSet será O(n^2)?

Answer 1

Sí, pero en realidad es el peor de los casos: si todos los elementos de la HashSet tienen el mismo código hash (o un código hash que lleva a el mismo cubo). Con un hashCode correctamente escrito y una muestra de clave normalmente distribuida, una búsqueda es O (1).

Answer 2

lookp toma O (c)

c = valor constante

Answer 3

Sí, pero la razón por la que tenemos HashSets es que encontramos este peor caso con muy, muy baja probabilidad, y suele ser mucho más rápido que el nlogn garantizado para un montón o un TreeSet (autoequilibrado) o el garantizado n^2 para una lista desordenada.