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

Question

He visto algunas afirmaciones interesantes sobre SO re Java hashmaps 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 me compraron, siempre debe existir un conjunto de datos que contenga colisiones.

En cuyo caso, la búsqueda sería O(n) en lugar de O(1).

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

Answer 1

Una característica particular de un HashMap es que, a diferencia de, por ejemplo, á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 el caso de una colisión con respecto a qué tan completo está el mapa. Una colisión es bastante fácil de estimar.

p _colisión = n/capacidad

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

O (n) = O (k * n)

Podemos utilizar esta función para mejorar el rendimiento de la correlación hash. En cambio, podríamos pensar en la probabilidad de un máximo de 2 colisiones.

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

Esto es mucho menor. Como el costo de manejar una colisión extra es irrelevante para el rendimiento de Big O, ¡hemos encontrado una manera de mejorar el rendimiento sin cambiar realmente el algoritmo! Podemos generalzie esto a

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

Y ahora podemos pasar por alto un número arbitrario de colisiones y terminar con infinitamente pequeña probabilidad de más colisiones de las que estamos contabilizando. Puede obtener la probabilidad de 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-mapa tiene O (1) Acceso con alta probabilidad

Answer 2

En Java, HashMap funciona usando hashCode para localizar un segmento. Cada cubo es una lista de elementos que residen en ese cubo. Los elementos se escanean, usando iguales para comparar. Al agregar elementos, el HashMap se redimensiona una vez que se alcanza un determinado porcentaje de carga.

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

Answer 3

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 cada caso posible pero está en casos más).

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 eso es otra discusión) por lo que la posibilidad de colisiones es muy baja.

Answer 4

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 única búsqueda, por lo tanto, el tiempo de ejecución es O (1). Si hay colisiones, debe hacer más de una búsqueda, lo que reduce el rendimiento hacia O (n).

Answer 5

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. la cantidad de artículos en el contenedor. Entonces, si toma 4 comparaciones promedio para encontrar un artículo en un contenedor con 100 artículos, también debería 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 varianza, especialmente alrededor de los puntos en los que se repite la tabla hash, y cuando hay una cantidad muy pequeña de elementos).

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

Answer 6

Parece que mezcla el peor de los casos con el tiempo medio de ejecución (esperado). El primero es de hecho O (n) para tablas hash en general (es decir, no utiliza 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 variación muy estrecho.

Answer 7

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 somete a un hash 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 son mejores y los casos promedio permanecen constantes, es decir O (1).

Answer 8

Hemos establecido que la descripción estándar de consultas de tabla de hash siendo O (1) se refiere para el tiempo esperado promedio de caso, no el rendimiento del peor caso estricto. Para una tabla hash que resuelve las colisiones con el encadenamiento (como el hashmap de Java), esto es técnicamente O (1 + α) con a good hash function, donde α es el factor de carga de la tabla. Sigue siendo constante siempre que la cantidad de objetos que almacene 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 entradas que requieren O (n) búsquedas para cualquier función hash determinista.Pero también es interesante considerar el peor de los casos 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 le interesan los métodos teóricos para lograr las búsquedas del peor de los casos esperadas a tiempo constante, puede leer acerca de dynamic perfect hashing que resuelve las colisiones recursivamente con otra tabla hash.

Answer 9

Si el número de segmentos (call it b) se mantiene constante (el caso habitual), entonces la búsqueda es en realidad O (n).
Cuando 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 formas habituales (por ejemplo, la lista vinculada), la búsqueda es O (n/b) = O (n).

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

Answer 10

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 de tiempo de búsqueda.

Answer 11

Académicos lado, desde una perspectiva práctica, HashMaps deben ser aceptados como teniendo un impacto en el rendimiento intrascendente (a menos que su generador de perfiles le indique lo contrario.)

Answer 12

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) desde alpha es una constante.

Answer 13

Sé que esta es una pregunta antigua, pero en realidad hay una nueva respuesta.

Tiene razón de que un mapa hash no es realmente O(1), estrictamente hablando, porque como el número de elementos se vuelve arbitrariamente grande, con el tiempo 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) - porque no hay una regla que diga que los segmentos deben implementarse como una lista lineal.

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

Answer 14

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

Answer 15

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 único hash de una o más claves.
Mientras que la adición de una entrada en el HashMap, el código hash de la clave se utiliza para determinar la ubicación de la cubeta de la matriz, algo así como:

location = (arraylength - 1) & keyhashcode 

Aquí el & representa operador AND.

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

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

En el peor de los casos, todas las teclas tienen el mismo código hash y se almacenan en el mismo contenedor, esto da como resultado el recorrido por toda la lista que conduce a O (n).

En el caso de Java 8, el depósito de la Lista vinculada se reemplaza por un TreeMap si el tamaño aumenta a más de 8, esto reduce la peor eficiencia de búsqueda de casos a O (log n).