Posterior a observar en diferentes repositorios y páginas al final nos encontramos con la respuesta que te enseñaremos aquí.
Solución:
se ejecuta en O(1) tiempo esperado, como cualquier tabla hash (suponiendo que la función hash sea decente). Está respaldado por un HashMap donde el key es el Objeto.
Dos objetos pueden tener el mismo código hash, pero el HashSet no pensaría que son idénticos, a menos que el equals método para estos objetos dice que son iguales (es decir, devuelve true).
los contains llamadas a métodos (indirectamente) getEntry de HashMapdonde key es el Object para el que desea saber si está en el HashSet.
Como puede ver a continuación, se pueden almacenar dos objetos en el HashMap/HashSet incluso si su key se asigna al mismo valor mediante la función hash. El método itera sobre todos keys que tienen el mismo valor hash, y realiza equals en cada uno para encontrar la coincidencia key.
final Entry getEntry(Object key)
int hash = (key == null) ? 0 : hash(key.hashCode());
for (Entry e = table[indexFor(hash, table.length)];
e != null;
e = e.next) (key != null && key.equals(k))))
return e;
return null;
El rendimiento en el peor de los casos de contains será O(log n) para Java 8 y O(n) para Java 7, pero el caso promedio se acercará más a O(1). Esto se debe a que el hashset está respaldado por un hashmap y, por lo tanto, tiene la misma eficacia que la búsqueda de hashmap (es decir, HashMap.get(…)). El mapeo real en un hashmap es de tiempo constante (O(1)), pero la necesidad de manejar colisiones trae el costo de iniciar sesión n. Es decir, múltiples elementos que hacen hash al mismo array El índice debe almacenarse en una estructura de datos secundaria (también conocida como depósito), y es este depósito el que determina el rendimiento en el peor de los casos. En Java, el manejo de colisiones de hashmap se implementa mediante un árbol autoequilibrado.
Los árboles autoequilibrados garantizan O(log n) para todas las operaciones, por lo tanto, la inserción y búsqueda en hashmap (y hashset) tiene un costo total de O(1) + O(log n) = O(log n). El uso de un árbol autoequilibrado para el manejo de colisiones se introdujo en Java 8 como una mejora sobre el encadenamiento (usado hasta Java 7), que usa una lista enlazada y tiene el peor caso de O(n) para búsqueda e inserción (ya que necesita atravesar la lista). Tenga en cuenta que el encadenamiento tendría un tiempo constante para la inserción (a diferencia de la búsqueda), ya que los elementos se pueden agregar a una lista enlazada en O(1), pero la propiedad set (sin duplicados) se impone en la lista enlazada en el caso de hashmap y, por lo tanto, debe atravesar la lista vinculada también en el caso de la inserción para garantizar que el elemento no exista ya en la lista/depósito, y terminamos con O(n) tanto para la inserción como para la búsqueda.
Referencias:
Esta clase implementa la interfaz Set, respaldada por una tabla hash (en realidad, una instancia de HashMap). https://docs.oracle.com/javase/8/docs/api/java/util/HashSet.html
Cubos que contienen un gran número de colisión keys almacenará sus entradas en un árbol equilibrado en lugar de una lista vinculada después de alcanzar cierto umbral. (https://www.nagarro.com/es/blog/post/24/mejora-del-rendimiento-para-hashmap-en-java-8)
Recuerda que puedes dar difusión a este ensayo si si solucionó tu problema.