Estaba leyendo los javadocs en HashSet cuando me encontré con la interesante declaración:

Esta clase ofrece un rendimiento de tiempo constante para las operaciones básicas (agregar, eliminar, contiene y tamaño)

Esto me confunde enormemente, ya que no entiendo cómo uno podría obtener tiempo constante, O (1), rendimiento para una operación de comparación. Aquí están mis pensamientos:

Si esto es cierto, no importa cuántos datos descargue en mi HashSet, podré acceder a cualquier elemento en tiempo constante. Es decir, si pongo 1 elemento en mi HashSet, llevará la misma cantidad de tiempo encontrarlo que si tuviera un googolplex de elementos.

Sin embargo, esto no sería posible si tuviera un número constante de cubos, o una función hash consistente, ya que para cualquier número fijo de cubos, el número de elementos en ese cubo crecerá linealmente (aunque lentamente, si el número es grande suficiente) con el número de elementos en el conjunto.

Entonces, la única forma de que esto funcione es tener una función hash cambiante cada vez que inserte un elemento (o cada pocas veces). Una función hash simple que nunca colisiones satisfaría esta necesidad. Un ejemplo de juguete para las cadenas podría ser: tomar el valor ASCII de las cadenas y concatenarlas juntas (porque sumar podría generar un conflicto).

Sin embargo, esta función hash y cualquier otra función hash de este tipo probablemente fallará para cadenas o números lo suficientemente grandes, etc. El número de cubos que puede formar está limitado inmediatamente por la cantidad de espacio de pila / montón que tiene, etc. , omitir ubicaciones en la memoria no se puede permitir indefinidamente, por lo que eventualmente tendrá que llenar los vacíos.

Pero si en algún momento hay un nuevo cálculo de la función hash, esto solo puede ser tan rápido como encontrar un polinomio que pase por N puntos u O (nlogn).

Así llega mi confusión. Si bien creeré que el HashSet puede acceder a elementos en tiempo O (n / B), donde B es el número de cubos que ha decidido usar, no veo cómo un HashSet podría realizar funciones de agregar u obtener en O ( 1 vez.

Nota:Esta publicación yesta publicación ambos no abordan las preocupaciones que enumeré ...