TreeMap o HashMap? [duplicar]
Esta pregunta ya tiene una respuesta aquí:
- Diferencia entre HashMap, LinkedHashMap y TreeMap 16 respuestas
- ¿Cuál es la diferencia entre un HashMap y un TreeMap? [duplicar] 8 respuestas
Cuándo usar hashmaps o diagramas de árbol?
Sé que puedo usar TreeMap para iterar sobre los elementos cuando necesito ordenarlos. ¿Pero es solo eso? No hay optimización cuando solo quiero consultar los mapas,o algunos usos específicos óptimos?
5 answers
Los hashtables (generalmente) realizan operaciones de búsqueda (buscar) limitadas dentro de la complejidad de O(n)<=T(n)<=O(1), con una complejidad de caso promedio de O(1 + n/k); sin embargo, los árboles de búsqueda binarios, (BST), realizan operaciones de búsqueda (buscar) limitadas dentro de la complejidad de O(n)<=T(n)<=O(log_2(n)), con una complejidad de caso promedio de O(log_2(n)). La implementación para cada (y cada) estructura de datos debe ser conocida (por usted), para comprender las ventajas, los inconvenientes, la complejidad temporal de las operaciones y la complejidad del código.
Para por ejemplo, el número de entradas en una tabla hash a menudo tiene un número fijo de entradas (alguna parte de las cuales puede no estar llena en absoluto) con listas de colisiones. Los árboles, por otro lado, generalmente tienen dos punteros (referencias) por nodo, pero esto puede ser más si la implementación permite más de dos nodos hijos por nodo, y esto permite que el árbol crezca a medida que se agregan nodos, pero puede no permitir duplicados. (La implementación predeterminada de Java TreeMap no permite duplicados)
Allí por ejemplo, ¿qué pasa si el número de elementos de una estructura de datos en particular aumenta sin límite o se acerca al límite de una parte subyacente de la estructura de datos? ¿Qué pasa con las operaciones amortizadas que realizan alguna operación de reequilibrio o limpieza?
Por ejemplo, en una tabla hash, cuando el número de elementos de la tabla se vuelve suficientemente grande, y puede ocurrir un número arbitrario de colisiones. Por otro lado, los árboles suelen requerir venir procedimiento de reequilibrio después de una inserción (o eliminación).
Entonces, si usted tiene algo como un cache (Ex. el número de elementos en acotado, o el tamaño es conocido) entonces una tabla hash es probablemente su mejor apuesta; sin embargo, si usted tiene algo más parecido a un diccionario (Ej. poblada una vez y levantada la vista muchas veces) luego usaría un árbol.
Esto es solo en el caso general, sin embargo, (no se dio información). Tienes que entender el proceso que sucede cómo suceden para tomar la decisión correcta al decidir qué estructura de datos utilizar.
Cuando necesito un mapa múltiple (búsqueda a distancia) o un aplanamiento ordenado de una colección, entonces no puede ser una tabla hash.
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/ajaxhispano.com/template/agent.layouts/content.php on line 61
2012-12-13 17:36:54
TreeMap proporciona tiempo de búsqueda garantizado O(log n) (e inserción, etc.), mientras que HashMap proporciona tiempo de búsqueda O(1) si el código hash dispersa las claves apropiadamente.
A menos que necesite ordenar las entradas, me quedaría con HashMap. O hay ConcurrentHashMap por supuesto. No puedo recordar los detalles de las diferencias entre todos ellos, pero HashMap es una opción "por defecto" perfectamente razonable:)
Para completar, debo señalar que hubo una discusión sobre el desbordamiento de pila un mes más o menos hace sobre los aspectos internos de varios mapas. Ver los comentarios en esta pregunta, que voy a copiar en esta respuesta si bestsss está feliz de que lo haga.
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/ajaxhispano.com/template/agent.layouts/content.php on line 61
2017-05-23 12:17:54
La mayor diferencia entre los dos es la estructura subyacente utilizada en la implementación.
Los HashMaps usan un array y una función hashing para almacenar elementos. Cuando intenta insertar o eliminar un elemento en la matriz, la función hash convierte la clave en un índice en la matriz donde se almacena/debe almacenar el objeto (ignorando los conflictos). Si bien los hashmaps son generalmente muy rápidos porque no necesitan iterar sobre grandes cantidades de datos, se ralentizan cuando se llenan porque necesitan copiar todas las claves / valores en una nueva matriz.
Los TreeMaps almacenan los datos en una estructura de árbol ordenada. Si bien esto significa que nunca tendrán que asignar más espacio y copiarlo, las operaciones requieren que parte de los datos ya almacenados se iteren. A veces cambiando grandes cantidades de la estructura.
De los dos Hashmaps generalmente tendrá un mejor rendimiento cuando no necesite ordenar.
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/ajaxhispano.com/template/agent.layouts/content.php on line 61
2014-01-29 10:41:08
No olvide que también hay LinkedHashMap que es casi tan rápido como HashMap para las operaciones agregar/contiene/eliminar, pero también mantiene el orden de inserción.
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/ajaxhispano.com/template/agent.layouts/content.php on line 61
2011-03-16 17:52:12
Insertar nuevos elementos en un HashMap será, en promedio, mucho más rápido que insertar elementos en un TreeMap. A menos que necesites tus elementos ordenados, yo iría con el HashMap.
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/ajaxhispano.com/template/agent.layouts/content.php on line 61
2011-03-16 17:42:40