examples - ¿Es un hashmap de Java realmente O(1)?
hashmap java example (15)
Aparte de los aspectos académicos, desde una perspectiva práctica, se debe aceptar que HashMaps tiene un impacto de rendimiento sin consecuencias (a menos que su generador de perfiles le indique lo contrario).
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 ese caso, la búsqueda sería O(n) lugar de O(1) .
¿Alguien puede explicar si son O (1) y, de ser así, cómo lo logran?
Depende del algoritmo que elijas 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).
En Java, HashMap funciona usando hashCode para ubicar un cubo. 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.
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 malas funciones hash.
Si necesita hacer crecer la tabla cuando agrega elementos o no, no es relevante para la pregunta, ya que se trata de tiempo de búsqueda.
Establecimos que la descripción estándar de las búsquedas de tablas hash es O (1) se refiere al tiempo esperado promedio de caso, no al rendimiento estricto de peor caso. Para una tabla hash que resuelve las colisiones con el 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 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 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 de búsqueda promedio. Usar el encadenamiento es O (1 + la longitud de la cadena más larga), por ejemplo Θ (log n / log log n ) cuando α = 1.
Si le interesan las formas teóricas para lograr búsquedas esperadas en el peor de los casos, puede leer acerca del hash dinámico perfecto que resuelve las colisiones recursivamente con otra tabla hash.
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í mismo 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).
Los elementos dentro de HashMap se almacenan como una matriz de lista vinculada (nodo), cada lista vinculada de la matriz representa un depósito para el valor único de hash 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 como:
location = (arraylength - 1) & keyhashcode
Aquí el & representa el operador AND bit a bit.
Por ejemplo: 100 & "ABC".hashCode() = 64 (location of the bucket for the key "ABC")
Durante la operación de obtención, usa la misma manera para determinar la ubicación del cucharón para 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 claves tienen el mismo código hash y se almacenan en el mismo contenedor, lo que da como resultado un recorrido por toda la lista que conduce a O (n).
En el caso de Java 8, el depósito de Lista enlazada 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).
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 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 varianza muy estrecho.
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 muy buen rendimiento (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 cambie, pero también deshabilita el bloqueo sesgado, pero eso es otra discusión) por lo que la posibilidad de colisiones es muy bajo.
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 con respecto al número de elementos 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).
Por lo tanto, 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.
Sé que esta es una vieja pregunta, pero en realidad hay una nueva respuesta.
Tiene razón en que un hash map no es realmente O(1) , estrictamente hablando, porque a medida que 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 TreeMaps como TreeMaps una vez que exceden un umbral, lo que hace que el tiempo real sea O(log n) .
Si el número de segmentos (call it b) se mantiene constante (el caso habitual), entonces la búsqueda es en realidad O (n).
A medida que n crece, 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 sobre 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 → ∞.
Solo en el caso teórico, cuando los códigos hash son siempre diferentes y el cubo para cada código hash también es diferente, existirá O (1). De lo contrario, es de orden constante, es decir, al aumentar hashmap, su orden de búsqueda permanece constante.
Una característica particular de un HashMap es que, a diferencia de, digamos, á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
Por lo tanto, es 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 eso para cualquier constante arbitraria, fija k.
O (n) = O (k * n)
Podemos usar esta característica 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 mas bajo 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 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 mínimamente diminuta de más colisiones de las que estamos contando. 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-map tiene O (1) acceso con alta probabilidad
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.