examples - hashmap java example
HashMap get/put complejidad (5)
Estamos acostumbrados a decir que las operaciones get/put HashMap son O (1). Sin embargo, depende de la implementación de hash. El hash de objeto predeterminado es en realidad la dirección interna en el montón de JVM. ¿Estamos seguros de que es lo suficientemente bueno para afirmar que el get/put es O (1)?
La memoria disponible es otro problema. Como entiendo de los javadocs, el load factor HashMap debería ser 0.75. ¿Qué pasa si no tenemos suficiente memoria en JVM y el load factor excede el límite?
Entonces, parece que O (1) no está garantizado. ¿Tiene sentido o me estoy perdiendo algo?
Depende de muchas cosas. Suele ser O (1), con un hash decente que a su vez es tiempo constante ... pero puede tener un hash que tarda mucho tiempo en computarse, y si hay varios elementos en el hash que devuelven el mismo código hash, get tendrá que iterar sobre ellos equals a cada uno de ellos para encontrar una coincidencia.
En el peor de los casos, un HashMap tiene una búsqueda O (n) debido a recorrer todas las entradas en el mismo cubo hash (por ejemplo, si todas tienen el mismo código hash). Afortunadamente, el peor de los casos no aparece muy a menudo en la vida real, en mi experiencia. Entonces, no, O (1) ciertamente no está garantizado, pero generalmente es lo que debe asumir al considerar qué algoritmos y estructuras de datos usar.
En JDK 8, HashMap ha sido ajustado de modo que si las claves se pueden comparar para ordenar, cualquier cubo densamente poblado se implementa como un árbol, por lo que incluso si hay muchas entradas con el mismo código hash, la complejidad es O ( log n). Eso puede causar problemas si tiene un tipo de clave donde la igualdad y el orden son diferentes, por supuesto.
Y sí, si no tienes suficiente memoria para el hash map, estarás en problemas ... pero eso será cierto independientemente de la estructura de datos que uses.
En la práctica, es O (1), pero esto en realidad es una simplificación terrible y matemáticamente sin sentido. La notación O () dice cómo se comporta el algoritmo cuando el tamaño del problema tiende a infinito. Hashmap get / put funciona como un algoritmo O (1) para un tamaño limitado. El límite es bastante grande desde la memoria de la computadora y desde el punto de vista del direccionamiento, pero lejos del infinito.
Cuando uno dice que hashmap get / put es O (1) realmente debería decir que el tiempo necesario para el get / put es más o menos constante y no depende de la cantidad de elementos en el hashmap en la medida en que el hashmap pueda ser presentado en el sistema informático real. Si el problema va más allá de ese tamaño y necesitamos un hashps más grande, después de un tiempo, ciertamente el número de bits que describen un elemento también aumentará a medida que se agoten los posibles elementos descriptibles diferentes. Por ejemplo, si usamos un hashmap para almacenar números de 32 bits y luego aumentamos el tamaño del problema para que tengamos más de 2 ^ 32 elementos bit en el hashmap, entonces los elementos individuales se describirán con más de 32 bits.
El número de bits necesarios para describir los elementos individuales es log (N), donde N es la cantidad máxima de elementos, por lo tanto, get y put son realmente O (log N).
Si lo compara con un conjunto de árboles, que es O (log n), el conjunto de hash es O (largo (max (n)) y simplemente sentimos que es O (1), porque en una determinada implementación max (n) es fijo, no cambia (el tamaño de los objetos que almacenamos medidos en bits) y el algoritmo que calcula el código hash es rápido.
Finalmente, si encontrar un elemento en cualquier estructura de datos fuera O (1) crearíamos información de la nada. Al tener una estructura de datos de n elemento, puedo seleccionar un elemento de una manera n diferente. Con eso, puedo codificar la información del bit log (n). Si puedo codificar eso en bit cero (eso es lo que significa O (1)), entonces creé un algoritmo ZIP de compresión infinita.
La operación HashMap es factor dependiente de la implementación de hashCode. Para el escenario ideal, digamos la buena implementación hash que proporciona un código hash único para cada objeto (sin colisión hash), entonces el mejor, peor y promedio caso sería O (1). Consideremos un escenario donde una mala implementación de hashCode siempre devuelve 1 o dicho hash que tiene colisión hash. En este caso, la complejidad del tiempo sería O (n).
Ahora, al llegar a la segunda parte de la pregunta sobre la memoria, entonces JVM se ocuparía de la restricción de la memoria.
No estoy seguro de que el código hash predeterminado sea la dirección: hace un tiempo leí el código fuente de OpenJDK para la generación de código hash, y recuerdo que es algo un poco más complicado. Todavía no es algo que garantice una buena distribución, tal vez. Sin embargo, eso es hasta cierto punto discutible, ya que pocas clases que usarías como claves en un hashmap usan el código hash predeterminado: proporcionan sus propias implementaciones, que deberían ser buenas.
Además de eso, lo que quizás no sepa (de nuevo, esto se basa en la fuente de lectura, no está garantizado) es que HashMap agita el hash antes de usarlo, para mezclar la entropía de toda la palabra en los bits de abajo, que es donde está Necesario para todos menos para los hashmaps más grandes. Eso ayuda a lidiar con hash que específicamente no lo hacen por sí mismos, aunque no puedo pensar en ningún caso común donde lo veas.
Finalmente, lo que sucede cuando la tabla está sobrecargada es que degenera en un conjunto de listas vinculadas paralelas: el rendimiento se convierte en O (n). Específicamente, la cantidad de enlaces atravesados será en promedio la mitad del factor de carga.
Ya se ha mencionado que los hashmaps son O(n/m) en promedio, si n es el número de elementos y m es el tamaño. También se ha mencionado que, en principio, todo el asunto podría colapsar en una lista individualmente vinculada con O(n) tiempo de consulta. (Todo esto supone que el cálculo del hash es tiempo constante).
Sin embargo, lo que no se menciona a menudo es que con una probabilidad de al menos 1-1/n (por lo que para 1000 elementos es 99.9% de probabilidad), el cubo más grande no se rellenará más que O(logn) . De ahí que coincida con la complejidad promedio de los árboles de búsqueda binarios. (Y la constante es buena, un límite más estricto es (log n)*(m/n) + O(1) ).
Todo lo que se requiere para este límite teórico es que use una función hash razonablemente buena (vea Wikipedia: Universal Hashing . Puede ser tan simple como a*x>>m ). Y, por supuesto, que la persona que le da los valores de hash no sepa cómo ha elegido sus constantes aleatorias.
TL; DR: con muy alta probabilidad, la peor complejidad de obtención / colocación de un hashmap es O(logn) .