HashMap get/put complejidad

Question

Estamos acostumbrados a decir que HashMapget/put operaciones 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 HashMapload factor debería ser 0.75. ¿Qué pasa si no tenemos suficiente memoria en JVM y el load factor excede el límite?

Parece que O (1) no está garantizado. ¿Tiene sentido o me estoy perdiendo algo?

Answer 1

Depende de muchas cosas. Es por lo general O (1), con un hash decente que a su vez es tiempo constante ... pero puede tener un hash que tarda mucho tiempo en calcular, y si hay varios elementos en el mapa hash que devuelven el mismo código hash, get tendrá que iterar sobre ellos llamando al equals en cada uno de ellos para encontrar una coincidencia.

En el peor de los casos, un HashMap tiene una búsqueda O (n) al 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 se ha modificado para que, si se pueden comparar las claves para el pedido, cualquier cubo densamente poblado se implemente como un árbol, de modo 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 mapa hash, estarás en problemas ... pero eso será cierto independientemente de la estructura de datos que uses.

Answer 2

No estoy seguro de que el código hash predeterminado sea la dirección: hace un tiempo leí la fuente 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 inferiores, que es donde se necesita 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.

Answer 3

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 vinculada individualmente 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 (entonces para 1000 artículos hay un 99,9% de probabilidad) ¡el cubo más grande no se llenará más de 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).

Answer 4

La operación de HashMap es un 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 que viene a la segunda parte de la pregunta sobre la memoria, entonces sí, la restricción de la memoria correrá a cargo de JVM.