Es un hashmap de Java realmente O (1)?

Parece que confunde el comportamiento del peor de los casos con el tiempo de ejecución promedio (esperado). El primero es de hecho O (n) para las tablas hash en general (es decir, no usar un hash perfecto), pero esto rara vez es relevante en la práctica.

Cualquier implementación de tabla hash confiable, junto con un hash medio decente, tiene un rendimiento de recuperación de O(1) con un factor muy pequeño (2, de hecho) en el caso esperado, dentro de un margen de varianza muy estrecho.

En Java, HashMap funciona usando hashCode para localizar un bucket. Cada cubo es una lista de elementos que residen en ese cubo. Los elementos se escanean, utilizando iguales para la comparación. Al agregar elementos, el HashMap se redimensiona una vez que se alcanza un cierto porcentaje de carga.

Por lo tanto, a veces tendrá que comparar con unos pocos elementos, pero generalmente está mucho más cerca de O(1) que O(n). Para propósitos prácticos, eso es todo lo que necesitas saber.

Recuerde que o(1) no significa que cada búsqueda solo examine un solo elemento - significa que el número promedio de elementos revisados permanece constante w.r.t. el número de elementos en el contenedor. Así que si se necesita un promedio de 4 comparaciones para encontrar un elemento en un contenedor con 100 elementos, también debe tomar un promedio de 4 comparaciones para encontrar un elemento en un contenedor con 10000 elementos, y para cualquier otro número de elementos (siempre hay un poco de variación, especialmente alrededor de los puntos en los que tabla rehashes, y cuando hay un número muy pequeño de elementos).

Por lo tanto, las colisiones no impiden que el contenedor tenga operaciones o(1), siempre y cuando el número promedio de claves por cubo permanezca dentro de un límite fijo.

Sé que esta es una vieja pregunta, pero en realidad hay una nueva respuesta a ella.

Tiene razón en que un mapa hash no es realmente O(1), estrictamente hablando, porque como el número de elementos se vuelve arbitrariamente grande, eventualmente no podrá buscar en tiempo constante (y la notación O se define en términos de números que pueden ser arbitrariamente grandes).

Pero no se sigue que la complejidad en tiempo real sea O(n) because porque no hay ninguna regla que diga que los cubos tienen que ser implementado como una lista lineal.

De hecho, Java 8 implementa los cubos como TreeMaps una vez que superan un umbral, lo que hace que el tiempo real O(log n).

Si el número de cubos (llámelo b) se mantiene constante (el caso habitual), entonces la búsqueda es realmente O(n).
A medida que n se hace grande, el número de elementos en cada cubo promedia n/b. Si la resolución de colisión se realiza de una de las maneras habituales (lista vinculada, por ejemplo), entonces la búsqueda es O(n/b) = O(n).

La notación O es acerca de lo que sucede cuando n se hace más y más grande. Puede ser engañoso cuando se aplica a ciertos algoritmos,y las tablas hash son un ejemplo. Elegimos el número de cubos basados en cuántos elementos esperamos tratar. Cuando n es aproximadamente del mismo tamaño que b, entonces la búsqueda es aproximadamente tiempo constante, pero no podemos llamarlo O (1) porque O se define en términos de un límite como n → ∞.

O(1+n/k) donde k es el número de cubos.

Si la implementación establece k = n/alpha entonces es O(1+alpha) = O(1) ya que alpha es una constante.

Hemos establecido que la descripción estándar de las búsquedas de tablas hash siendo O(1) se refiere al tiempo esperado en el caso promedio, no al rendimiento estricto en el peor de los casos. Para una tabla hash resolviendo colisiones con encadenamiento (como el hashmap de Java) esto es técnicamente O (1 + α) con una buena función hash, donde α es el factor de carga de la tabla. Sigue siendo constante, siempre y cuando el número de objetos que está almacenando no sea más que un factor constante mayor que el tamaño de la tabla.

También ha sido explicó que estrictamente hablando es posible construir entradas que requieren búsquedas O(n) para cualquier función hash determinista. Pero también es interesante considerar el tiempo esperado en el peor de los casos, que es diferente al tiempo promedio de búsqueda. Usando encadenamiento esto es O ( 1 + la longitud de la cadena más larga), por ejemplo Θ(log n / log log n) cuando α=1.

Si está interesado en formas teóricas para lograr búsquedas constantes en el peor de los casos, puede leer sobre el hashing dinámico perfecto que resuelve colisiones recursivamente con otra tabla hash!

Es O(1) solo si su función de hash es muy buena. La implementación de la tabla hash de Java no protege contra malas funciones hash.

Si necesita hacer crecer la tabla cuando agrega elementos o no, no es relevante para la pregunta porque se trata del tiempo de búsqueda.

Esto se aplica básicamente a la mayoría de las implementaciones de tablas hash en la mayoría de los lenguajes de programación, ya que el algoritmo en sí no cambia.

Si no hay colisiones presentes en la tabla, solo tiene que hacer una sola búsqueda, por lo tanto, el tiempo de ejecución es O(1). Si hay colisiones presentes, tiene que hacer más de una búsqueda, lo que reduce el rendimiento hacia O(n).

Depende del algoritmo que elija para evitar colisiones. Si su implementación utiliza encadenamiento separado, entonces el peor escenario ocurre cuando cada elemento de datos se hash al mismo valor (mala elección de la función hash, por ejemplo). En ese caso, la búsqueda de datos no es diferente de una búsqueda lineal en una lista vinculada, es decir, O(n). Sin embargo, la probabilidad de que eso suceda es insignificante y las búsquedas de casos mejores y promedio permanecen constantes, es decir, O(1).

Aparte de lo académico, desde una perspectiva práctica, se debe aceptar que los HashMaps tienen un impacto intrascendente en el rendimiento (a menos que su generador de perfiles le indique lo contrario.)

Solo en el caso teórico, cuando los hashcodes son siempre diferentes y el bucket para cada código hash también es diferente, el O(1) existirá. De lo contrario, es de orden constante, es decir, en el incremento de hashmap, su orden de búsqueda permanece constante.

Los elementos dentro del HashMap se almacenan como una matriz de lista vinculada (nodo), cada lista vinculada en la matriz representa un cubo para el valor hash único de una o más claves.
Al agregar una entrada en el HashMap, el hashcode de la clave se usa para determinar la ubicación del bucket en el array, algo así como:

location = (arraylength - 1) & keyhashcode

Aquí el & representa bitwise Y operador.

Por ejemplo: 100 & "ABC".hashCode() = 64 (location of the bucket for the key "ABC")

Durante la operación get utiliza la misma manera para determinar la ubicación del cubo para clave. En el mejor de los casos, cada hashcode es único y da como resultado un bucket único para cada clave, en este caso el método get pasa tiempo solo para determinar la ubicación del bucket y recuperar el valor que es la constante O(1).

En el peor de los casos, todas las claves tienen el mismo hashcode y se almacenan en el mismo cubo, esto resulta en atravesar toda la lista que conduce a O(n).

En el caso de java 8, el bucket de la lista enlazada se reemplaza con un mapa de árbol si el tamaño crece a más de 8, esto reduce la eficiencia de búsqueda en el peor de los casos a O(log n).

Por supuesto, el rendimiento del hashmap dependerá de la calidad de la función hashCode() para el objeto dado. Sin embargo, si la función se implementa de tal manera que la posibilidad de colisiones es muy baja, tendrá un rendimiento muy bueno (esto no es estrictamente O(1) en todos los casos posibles, pero lo es en la mayoría de los casos).

Por ejemplo, la implementación predeterminada en Oracle JRE es usar un número aleatorio (que se almacena en la instancia del objeto para que no cambia , pero también desactiva el bloqueo sesgado, pero esa es otra discusión), por lo que la posibilidad de colisiones es muy baja.