¿Es un hashmap de Java realmente O (1)?

He visto algunas afirmaciones interesantes sobre los hashmaps SO re Java y su O(1)tiempo de búsqueda. ¿Alguien puede explicar por qué esto es así? A menos que estos hashmaps sean muy diferentes de cualquiera de los algoritmos de hash que compré, siempre debe existir un conjunto de datos que contenga colisiones.

En cuyo caso, la búsqueda sería O(n)más que O(1).

¿Alguien puede explicar si son O (1) y, de ser así, cómo logran esto?

Una característica particular de un HashMap es que, a diferencia de, por ejemplo, los árboles equilibrados, su comportamiento es probabilístico. En estos casos, generalmente es más útil hablar de complejidad en términos de la probabilidad de que ocurra el peor de los casos. Para un mapa hash, ese es, por supuesto, el caso de una colisión con respecto a qué tan lleno está el mapa. Una colisión es bastante fácil de estimar.

p _colisión = n / capacidad

Por lo tanto, es muy probable que un mapa hash con incluso un número modesto de elementos experimente al menos una colisión. La notación Big O nos permite hacer algo más convincente. Observe que para cualquier constante arbitraria, fija k.

O (n) = O (k * n)

Podemos usar esta función para mejorar el rendimiento del mapa hash. En cambio, podríamos pensar en la probabilidad de como máximo 2 colisiones.

p _{colisión x 2} = (n / capacidad) ²

Esto es mucho más bajo. Dado que el costo de manejar una colisión adicional es irrelevante para el rendimiento de Big O, ¡hemos encontrado una manera de mejorar el rendimiento sin cambiar realmente el algoritmo! Podemos generalizar esto a

p _{colisión xk} = (n / capacidad) ^k

Y ahora podemos ignorar un número arbitrario de colisiones y terminar con una probabilidad muy pequeña de que haya más colisiones de las que estamos contando. Puede obtener la probabilidad a un nivel arbitrariamente pequeño eligiendo la k correcta, todo sin alterar la implementación real del algoritmo.

Hablamos de esto diciendo que el mapa hash tiene acceso O (1) con alta probabilidad

Parece mezclar 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 utiliza un hashing perfecto), pero esto rara vez es relevante en la práctica.

Cualquier implementación confiable de la tabla hash, 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 variación muy estrecho.

En Java, HashMap funciona utilizando hashCode para ubicar un depósito. 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 cambia de tamaño una vez que se alcanza un cierto porcentaje de carga.

Entonces, a veces tendrá que comparar con algunos elementos, pero generalmente está mucho más cerca de O (1) que de O (n). Para fines prácticos, eso es todo lo que debe saber.

Recuerde que o (1) no significa que cada búsqueda solo examine un solo elemento, significa que el número promedio de elementos marcados permanece constante y el número de elementos en el contenedor. Por lo tanto, si se necesitan un promedio de 4 comparaciones para encontrar un artículo en un contenedor con 100 artículos, también debe tomar un promedio de 4 comparaciones para encontrar un artículo en un contenedor con 10000 artículos, y para cualquier otro número de artículos (siempre hay un un poco de variación, especialmente en torno a los puntos en los que la tabla hash se reajusta y cuando hay un número muy pequeño de elementos).

Por lo tanto, las colisiones no evitan que el contenedor tenga operaciones o (1), siempre que 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.

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

Pero no se deduce que la complejidad en tiempo real sea, O(n)porque no hay una regla que diga que los cubos deben implementarse como una lista lineal.

De hecho, Java 8 implementa los cubos TreeMapsuna vez que exceden 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 en realidad O (n).
A medida que n aumenta, el número de elementos en cada cubo promedia n / b. Si la resolución de colisión se realiza de una de las formas habituales (lista vinculada, por ejemplo), la búsqueda es O (n / b) = O (n).

La notación O se trata 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 buen ejemplo. Elegimos el número de depósitos en función de cuántos elementos esperamos tratar. Cuando n es aproximadamente del mismo tamaño que b, entonces la búsqueda es más o menos constante, pero no podemos llamarlo O (1) porque O se define en términos de un límite como n → ∞.

O(1+n/k) dónde k es el número de cubos

Si los conjuntos de aplicación k = n/alpha, entonces es O(1+alpha) = O(1)ya alphaes una constante.

Hemos establecido que la descripción estándar de las búsquedas de tablas hash que son O (1) se refiere al tiempo promedio esperado del caso, no al estricto desempeño del peor de los casos. Para una tabla hash que resuelve 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 que 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 se ha explicado que, estrictamente hablando, es posible construir una entrada que requiera búsquedas O ( n ) para cualquier función hash determinista. Pero también es interesante considerar el peor tiempo esperado , que es diferente al tiempo promedio de búsqueda. El uso de encadenamiento 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 de tiempo constante en el peor de los casos, puede leer sobre hashing dinámico perfecto que resuelve colisiones recursivamente con otra tabla hash.

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

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.

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

location = (arraylength - 1) & keyhashcode

Aquí el & representa el operador AND a nivel de bit.

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

Durante la operación de obtención, utiliza la misma forma para determinar la ubicación del depósito de la clave. En el mejor de los casos, cada clave tiene un código hash único y da como resultado un depósito único para cada clave, en este caso el método get dedica tiempo solo para determinar la ubicación del depósito y recuperar el valor que es constante O (1).

En el peor de los casos, todas las claves tienen el mismo código hash y se almacenan en el mismo depósito, lo que resulta en recorrer toda la lista que conduce a O (n).

En el caso de Java 8, el segmento Lista enlazada se reemplaza con un TreeMap si el tamaño aumenta a más de 8, esto reduce la eficiencia de búsqueda del peor caso a O (log n).

Básicamente, esto se aplica 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 realmente.

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, debe 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 usa un encadenamiento separado, entonces el peor de los casos ocurre cuando cada elemento de datos se codifica con el mismo valor (por ejemplo, una mala elección de la función hash). 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 ocurra es insignificante y las búsquedas de casos mejores y promedio permanecen constantes, es decir, O (1).

Dejando a un lado los aspectos académicos, desde una perspectiva práctica, se debe aceptar que HashMaps tiene un impacto en el rendimiento sin consecuencias (a menos que su perfilador le indique lo contrario).

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

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 manera tal que la posibilidad de colisiones es muy baja, tendrá un muy buen rendimiento (esto no es estrictamente O (1) en todos los casos posibles, pero es en la mayoría 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 cambie, pero también deshabilita el bloqueo sesgado, pero esa es otra discusión), por lo que la posibilidad de colisiones es muy bajo.