data structures - framework - ¿Por qué la búsqueda de hashmap es O(1), es decir, tiempo constante?
hashmap java (3)
Bajo los supuestos apropiados sobre la función hash que se está utilizando, podemos decir que las búsquedas en la tabla hash llevan el tiempo O (1) esperado . Esto significa que, en promedio , la cantidad de trabajo que realiza una tabla hash para realizar una búsqueda es, a lo sumo, algo constante.
Intuitivamente, si tiene una "buena" función hash, esperaría que los elementos se distribuyeran más o menos uniformemente en toda la tabla hash, lo que significa que el número de elementos en cada grupo estará cerca del número de elementos dividido por el número de cubos. Si la implementación de la tabla hash mantiene este número bajo (por ejemplo, al agregar más cubetas cada vez que la proporción de elementos a cubetas supera alguna constante), entonces la cantidad esperada de trabajo que se realiza termina siendo una cantidad de referencia para elegir qué cubeta debe escanearse, luego hacer "no demasiado" el trabajo mirando los elementos allí, porque a la expectativa solo habrá un número constante de elementos en ese cubo.
Esto no significa que las tablas hash hayan garantizado el comportamiento O (1). De hecho, en el peor de los casos, el esquema de hash degenerará y todos los elementos terminarán en un cubo, haciendo que las búsquedas tomen el tiempo Θ (n) en el peor de los casos. Por eso es importante diseñar buenas funciones hash.
Para obtener más información, es posible que desee leer un libro de texto de algoritmos para ver la derivación formal de por qué las tablas hash admiten búsquedas de manera tan eficiente. Esto generalmente se incluye como parte de un curso universitario típico sobre algoritmos y estructuras de datos, y hay muchos buenos recursos en línea.
¡Espero que esto ayude!
Si miramos desde la perspectiva de Java, podemos decir que la búsqueda de hashmap lleva tiempo constante. Pero ¿qué pasa con la implementación interna? Todavía tendría que buscar a través de un grupo particular (para qué hashcode de clave coincidente) diferentes claves coincidentes. Entonces, ¿por qué decimos que la búsqueda de hashmap lleva tiempo constante? Por favor explique.
La clave está en esta declaración en los documentos:
Si se deben almacenar muchas asignaciones en una instancia de HashMap, crearla con una capacidad suficientemente grande permitirá que las asignaciones se almacenen de manera más eficiente que permitir que se realicen cambios automáticos según sea necesario para hacer crecer la tabla.
y
El factor de carga es una medida de qué tan llena está permitida la tabla hash antes de que su capacidad se incremente automáticamente. Cuando el número de entradas en la tabla hash excede el producto del factor de carga y la capacidad actual, la tabla hash se vuelve a lavar (es decir, se reconstruyen las estructuras de datos internas) para que la tabla hash tenga aproximadamente el doble de cubetas.
http://docs.oracle.com/javase/6/docs/api/java/util/HashMap.html
La estructura interna del cucharón realmente se reconstruirá si se excede el factor de carga , lo que permite que el costo amortizado de obtener y poner sea O (1).
Tenga en cuenta que si se reconstruye la estructura interna, eso introduce una penalización de rendimiento que probablemente sea O (N), por lo que es posible que se requiera obtener y poner antes de que el costo amortizado se acerque a O (1) nuevamente. Por esa razón, planifique la capacidad inicial y el factor de carga de manera adecuada, de modo que no desperdicie espacio ni desencadene una reconstrucción evitable de la estructura interna.
Para seguir los comentarios de templatetypedef también:
La implementación de tiempo constante de una tabla hash podría ser un mapa hash, con el que puede implementar una lista de arreglos booleanos que indique si un elemento en particular existe en un cubo. Sin embargo, si está implementando una lista enlazada para su hashmap, el peor de los casos requeriría que revise cada grupo y tenga que atravesar los extremos de las listas.