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

159

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?

paxdiablo
fuente
1
Sé que esto podría no ser una respuesta, pero recuerdo que Wikipedia tiene un muy buen artículo sobre esto. No te pierdas la sección de análisis de rendimiento
victor hugo
28
La notación Big O proporciona un límite superior para el tipo particular de análisis que está haciendo. Aún debe especificar si está interesado en peor de los casos, caso promedio, etc.
Dan Homerick

Respuestas:

127

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) 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 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

SingleNegationElimination
fuente
Incluso con HTML, todavía no estoy muy contento con las fracciones. Límpielos si puede pensar en una buena manera de hacerlo.
SingleNegationElimination
44
En realidad, lo que dice lo anterior es que los efectos O (log N) están enterrados, para valores no extremos de N, por la sobrecarga fija.
Hot Licks
Técnicamente, ese número que proporcionó es el valor esperado del número de colisiones, que puede ser igual a la probabilidad de una sola colisión.
Simon Kuang
1
¿Es esto similar al análisis amortizado?
lostsoul29
1
@ OleV.V. El buen rendimiento de un HashMap siempre depende de una buena distribución de su función hash. Puede intercambiar una mejor calidad de hash por velocidad de hash mediante el uso de una función de hash criptográfica en su entrada.
SingleNegationElimination
38

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.

Konrad Rudolph
fuente
66
Siempre pensé que el límite superior era el peor de los casos, pero parece que me equivoqué: puede tener el límite superior para el caso promedio. Por lo tanto, parece que las personas que reclaman O (1) deberían haber dejado en claro que era para un caso promedio. El peor de los casos es un conjunto de datos donde hay muchas colisiones que lo convierten en O (n). Eso tiene sentido ahora.
paxdiablo
2
Probablemente debería dejar en claro que cuando usa la notación O grande para el caso promedio, está hablando de un límite superior en la función de tiempo de ejecución esperada, que es una función matemática claramente definida. De lo contrario, su respuesta no tiene mucho sentido.
ldog
1
gmatt: No estoy seguro de entender su objeción: la notación big-O es un límite superior de la función por definición . ¿Qué más podría decir por lo tanto?
Konrad Rudolph
3
bueno, por lo general, en la literatura informática se ve una gran notación O que representa un límite superior en las funciones de tiempo de ejecución o complejidad espacial de un algoritmo. En este caso, el límite superior está en realidad en la expectativa, que en sí mismo no es una función, sino un operador de funciones (variables aleatorias) y, de hecho, es una integral (lebesgue). Por supuesto y no es trivial.
ldog
31

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.

FogleBird
fuente
11
Bueno, dado que se supone que big-O especifica los límites, no importa si está más cerca de O (1) o no. Incluso O (n / 10 ^ 100) sigue siendo O (n). Entiendo su punto de vista sobre la eficiencia, reduciendo la relación, pero eso todavía pone el algoritmo en O (n).
paxdiablo
44
El análisis de mapas de hash generalmente se encuentra en el caso promedio, que es O (1) (con colusiones) En el peor de los casos, puede tener O (n), pero ese no suele ser el caso. con respecto a la diferencia: O (1) significa que obtiene el mismo tiempo de acceso independientemente de la cantidad de elementos en el gráfico, y ese es generalmente el caso (siempre que haya una buena proporción entre el tamaño de la tabla y 'n ')
Liran Orevi
44
También vale la pena señalar que todavía es exactamente O (1), incluso si el escaneo del cubo lleva un tiempo porque ya hay algunos elementos en él. Mientras los cubos tengan un tamaño máximo fijo, esto es solo un factor constante irrelevante para la clasificación O (). Pero, por supuesto, puede haber aún más elementos con claves "similares" agregadas, de modo que estos cubos se desborden y ya no pueda garantizar una constante.
sth
@sth ¿Por qué los cubos tendrían un tamaño máximo fijo?
Navin
31

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.

Daniel James
fuente
16

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).

ajb
fuente
4

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 → ∞.

IJ Kennedy
fuente
4

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.

Satyanarayana Kakollu
fuente
1
¿Qué significa la constante alfa ?
Prahalad Deshpande
2

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.

jtb
fuente
2

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.

Antti Huima
fuente
2

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).

Ramprabhu
fuente
1

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).

Tobias Svensson
fuente
1
Eso supone que el tiempo de ejecución está limitado por el tiempo de búsqueda. En la práctica, encontrará muchas situaciones en las que la función hash proporciona el límite (String)
Stephan Eggermont
1

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).

Nizar Grira
fuente
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).

Ryan Emerle
fuente
44
No en aplicaciones prácticas. Tan pronto como use una cadena como clave, notará que no todas las funciones hash son ideales, y algunas son realmente lentas.
Stephan Eggermont
1

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.

sn.anurag
fuente
0

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.

Pantera gris
fuente
"es en la mayoría de los casos". Más específicamente, el tiempo total tenderá hacia K veces N (donde K es constante) ya que N tiende hacia el infinito.
ChrisW
77
Esto está mal. El índice en la tabla hash se determinará a través de lo hashCode % tableSizeque significa que ciertamente puede haber colisiones. No estás aprovechando al máximo los 32 bits. Ese es el punto de las tablas hash ... reduce un gran espacio de indexación a uno pequeño.
FogleBird
1
"tiene garantizado que no habrá colisiones" No, no lo es porque el tamaño del mapa es menor que el tamaño del hash: por ejemplo, si el tamaño del mapa es dos, entonces se garantiza una colisión (no importa qué es el hash) si / cuando intento insertar tres elementos.
ChrisW
Pero, ¿cómo se convierte de una clave a la dirección de memoria en O (1)? Me refiero a como x = array ["clave"]. La clave no es la dirección de memoria, por lo que aún tendría que ser una búsqueda de O (n).
paxdiablo
1
"Creo que si no implementa hashCode, usará la dirección de memoria del objeto". Podría usar eso, pero el código hash predeterminado para Oracle Java estándar es en realidad un número aleatorio de 25 bits almacenado en el encabezado del objeto, por lo que 64/32 bits no tiene ninguna consecuencia.
Boann