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

StackOverflow https://stackoverflow.com/questions/1055243

Pregunta

He visto algunas afirmaciones interesantes sobre los hashmaps SO re Java y su O(1) tiempo de búsqueda. ¿Alguien puede explicar por qué 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) en lugar de <=>.

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

¿Fue útil?

Solución

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 sobre la 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 cuán 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 un máximo de 2 colisiones.

  

p colisión x 2 = (n / capacidad) 2

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 para

  

p colisión x k = (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 hash-map tiene acceso O (1) con alta probabilidad

Otros consejos

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 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 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 examina un solo elemento; significa que el número promedio de elementos marcados permanece constante w.r.t. El número de artículos 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 alrededor de los puntos en los que la tabla hash se vuelve a ajustar y cuando hay una cantidad muy pequeña 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 a ella.

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

Pero no se sigue 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 como TreeMaps una vez que exceden un umbral, lo que hace que el tiempo real sea O(log n).

Si el número de cubos (llámelo b) se mantiene constante (el caso habitual), 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 aproximadamente constante, pero no podemos llamarlo O (1) porque O se define en términos de un límite como n & # 8594; & # 8734 ;.

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 que son O (1) se refiere al tiempo promedio esperado del caso, no al rendimiento estricto 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 + & # 945;) con una buena función hash , donde & # 945; 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 momento 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 & # 920; (log n / log log n ) cuando & # 945; = 1.

Si está interesado en formas teóricas para lograr búsquedas de tiempo constante en el peor de los casos, puede leer acerca de 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 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 amplificador &; 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 lleva a O (n).

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

Esto básicamente 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 utiliza un encadenamiento separado, 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).

Académicos aparte, desde una perspectiva práctica, se debe aceptar que HashMaps tiene un impacto en el rendimiento sin consecuencias (a menos que su generador de perfiles 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 rendimiento muy bueno (esto no es estrictamente O (1) en todos casos posibles pero está 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 cambie, pero también deshabilita el bloqueo sesgado, pero esa es otra discusión) por lo que la posibilidad de colisiones es muy bajo.

Licenciado bajo: CC-BY-SA con atribución
No afiliado a StackOverflow
scroll top