Diferencia entre HashMap, LinkedHashMap y TreeMap

¿Cuál es la diferencia entre HashMap , LinkedHashMap y TreeMap en Java? No veo ninguna diferencia en el resultado ya que los tres tienen keySet y values . ¿Qué son las Hashtable ?

 Map m1 = new HashMap(); m1.put("map", "HashMap"); m1.put("schildt", "java2"); m1.put("mathew", "Hyden"); m1.put("schildt", "java2s"); print(m1.keySet()); print(m1.values()); SortedMap sm = new TreeMap(); sm.put("map", "TreeMap"); sm.put("schildt", "java2"); sm.put("mathew", "Hyden"); sm.put("schildt", "java2s"); print(sm.keySet()); print(sm.values()); LinkedHashMap lm = new LinkedHashMap(); lm.put("map", "LinkedHashMap"); lm.put("schildt", "java2"); lm.put("mathew", "Hyden"); lm.put("schildt", "java2s"); print(lm.keySet()); print(lm.values()); 

Las tres clases implementan la interfaz Map y ofrecen principalmente la misma funcionalidad. La diferencia más importante es el orden en que se realizará la iteración a través de las entradas:

  • HashMap ofrece absolutamente ninguna garantía sobre el orden de iteración. Puede (e incluso) cambiará completamente cuando se agreguen nuevos elementos.
  • TreeMap acuerdo con el “orden natural” de las claves de acuerdo con su compareTo() (o un Comparator suministrado externamente). Además, implementa la interfaz SortedMap , que contiene métodos que dependen de este orden de clasificación.
  • LinkedHashMap repetirá en el orden en que las entradas se colocaron en el mapa

“Hashtable” es el nombre genérico de los mapas basados ​​en hash. En el contexto de la API de Java, Hashtable es una clase obsoleta desde los días de Java 1.1 antes de que existiera el marco de colecciones. Ya no debería usarse, porque su API está atestada de métodos obsoletos que duplican la funcionalidad, y sus métodos están sincronizados (lo que puede disminuir el rendimiento y, en general, es inútil). Use ConcurrentHashMap en lugar de Hashtable.

Prefiero la presentación visual:

 ╔══════════════╦═════════════════════╦═══════════════════╦═════════════════════╗ ║ Property ║ HashMap ║ TreeMap ║ LinkedHashMap ║ ╠══════════════╬═════════════════════╬═══════════════════╬═════════════════════╣ ║ Iteration ║ no guarantee order ║ sorted according ║ ║ ║ Order ║ will remain constant║ to the natural ║ insertion-order ║ ║ ║ over time ║ ordering ║ ║ ╠══════════════╬═════════════════════╬═══════════════════╬═════════════════════╣ ║ Get/put ║ ║ ║ ║ ║ remove ║ O(1) ║ O(log(n)) ║ O(1) ║ ║ containsKey ║ ║ ║ ║ ╠══════════════╬═════════════════════╬═══════════════════╬═════════════════════╣ ║ ║ ║ NavigableMap ║ ║ ║ Interfaces ║ Map ║ Map ║ Map ║ ║ ║ ║ SortedMap ║ ║ ╠══════════════╬═════════════════════╬═══════════════════╬═════════════════════╣ ║ ║ ║ ║ ║ ║ Null ║ allowed ║ only values ║ allowed ║ ║ values/keys ║ ║ ║ ║ ╠══════════════╬═════════════════════╩═══════════════════╩═════════════════════╣ ║ ║ Fail-fast behavior of an iterator cannot be guaranteed ║ ║ Fail-fast ║ impossible to make any hard guarantees in the presence of ║ ║ behavior ║ unsynchronized concurrent modification ║ ╠══════════════╬═════════════════════╦═══════════════════╦═════════════════════╣ ║ ║ ║ ║ ║ ║Implementation║ buckets ║ Red-Black Tree ║ double-linked ║ ║ ║ ║ ║ buckets ║ ╠══════════════╬═════════════════════╩═══════════════════╩═════════════════════╣ ║ Is ║ ║ ║ synchronized ║ implementation is not synchronized ║ ╚══════════════╩═══════════════════════════════════════════════════════════════╝ 

Los tres representan la asignación de claves únicas a valores y, por lo tanto, implementan la interfaz de Mapa .

  1. HashMap es un mapa basado en hash de las claves. Admite O (1) operaciones get / put. Las claves deben tener implementaciones consistentes de hashCode() y equals() para que esto funcione.

  2. LinkedHashMap es muy similar a HashMap, pero agrega conocimiento al orden en el que se agregan (o acceden), por lo que el orden de iteración es el mismo que el orden de inserción (o el orden de acceso, dependiendo de los parámetros de construcción).

  3. TreeMap es un mapeo basado en árbol. Sus operaciones put / get toman el tiempo O (log n). Requiere elementos para tener algún mecanismo de comparación, ya sea con Comparable o Comparador. El orden de iteración está determinado por este mecanismo.

Vea dónde está cada clase en la jerarquía de clases en el siguiente diagtwig ( más grande ). TreeMap implementa SortedMap y SortedMap mientras que HashMap no lo hace.

HashTable está obsoleto y se debe usar la clase ConcurrentHashMap correspondiente. enter image description here

Solo algunos comentarios más de mi propia experiencia con los mapas, sobre cuándo usaría cada uno:

  • HashMap: más útil cuando se busca una implementación de mejor rendimiento (rápida).
  • TreeMap (interfaz SortedMap): más útil cuando estoy preocupado por poder ordenar o iterar sobre las teclas en un orden particular que defino.
  • LinkedHashMap: combina las ventajas del pedido garantizado de TreeMap sin el mayor costo de mantener TreeMap. (Es casi tan rápido como HashMap). En particular, LinkedHashMap también proporciona un excelente punto de partida para crear un objeto Cache anulando el método removeEldestEntry() . Esto le permite crear un objeto de caché que puede caducar datos utilizando algunos criterios que defina.

HashMap

  • Tiene valores de par (claves, valores)
  • NO valores clave de duplicación
  • desordenado sin ordenar
  • permite una clave nula y más de un valor nulo

Tabla de picadillo

  • lo mismo que el hash map
  • no permite claves nulas y valores nulos

LinkedHashMap

  • Es la versión ordenada de la implementación del mapa
  • Basado en listas enlazadas y estructuras de datos hash

TreeMap

  • Versión pedida y clasificada
  • basado en estructuras de datos hash

Las tres clases HashMap , TreeMap y LinkedHashMap implementan la interfaz java.util.Map y representan la asignación de una clave única a los valores.

HashMap

  1. Un HashMap contiene valores basados ​​en la clave.

  2. Contiene solo elementos únicos.

  3. Puede tener una clave nula y múltiples valores nulos.

  4. No mantiene orden .

    public class HashMap extends AbstractMap implements Map, Cloneable, Serializable

LinkedHashMap

  1. Un LinkedHashMap contiene valores basados ​​en la clave.
  2. Contiene solo elementos únicos.
  3. Puede tener una clave nula y múltiples valores nulos.
  4. Es lo mismo que HashMap en cambio mantiene el orden de inserción . // Ver desaceleración de clase a continuación

    public class LinkedHashMap extends HashMap implements Map

TreeMap

  1. Un TreeMap contiene valores basados ​​en la clave. Implementa la interfaz NavigableMap y amplía la clase AbstractMap.
  2. Contiene solo elementos únicos.
  3. No puede tener una clave nula, pero puede tener múltiples valores nulos.
  4. Es lo mismo que HashMap cambio mantiene el orden ascendente ( ordenado usando el orden natural de su clave).

    public class TreeMap extends AbstractMap implements NavigableMap, Cloneable, Serializable

Tabla de picadillo

  1. Un Hashtable es una matriz de lista. Cada lista se conoce como un cubo. La posición de la cuchara se identifica llamando al método hashcode (). Un Hashtable contiene valores basados ​​en la clave.
  2. Contiene solo elementos únicos.
  3. Es posible que no tenga ninguna clave o valor nulo.
  4. Está sincronizado .
  5. Es una clase heredada.

    public class Hashtable extends Dictionary implements Map, Cloneable, Serializable

Ref: http://javarevisited.blogspot.in/2015/08/difference-between-HashMap-vs-TreeMap-vs-LinkedHashMap-Java.html

HashMap no garantiza en absoluto el orden de iteración. Puede (e incluso) cambiará completamente cuando se agreguen nuevos elementos. TreeMap iterará de acuerdo con el “orden natural” de las claves de acuerdo con su método compareTo () (o un Comparador suministrado externamente). Además, implementa la interfaz SortedMap, que contiene métodos que dependen de este orden de clasificación. LinkedHashMap repetirá en el orden en que las entradas se colocaron en el mapa

Mira cómo varía el rendimiento … enter image description here

Mapa de árbol que es una implementación del mapa ordenado. La complejidad de las operaciones put, get y containsKey es O (log n) debido a la ordenación Natural

Déjame ponerlo simple:

  • HashMap se implementa como una tabla hash y no hay pedidos de claves o valores.
  • TreeMap se implementa en base a la estructura de árbol rojo-negro, y está ordenado por la clave.
  • LinkedHashMap conserva el orden de inserción
  • Hashtable está sincronizado, a diferencia de HashMap. Tiene una sobrecarga para la sincronización. Esta es la razón por la que se debe usar HashMap si el progtwig es seguro para subprocesos.

@Amit: SortedMap es una interfaz mientras que TreeMap es una clase que implementa la interfaz SortedMap . Eso significa que si sigue el protocolo que SortedMap le pide a sus implementadores que haga. Un árbol, a menos que esté implementado como árbol de búsqueda, no puede darle datos ordenados porque el árbol puede ser cualquier tipo de árbol. Para que TreeMap funcione como SortedMarket, implementa SortedMap (por ejemplo, Binary Search Tree – BST, BST balanceado como AVL y RB Tree, incluso Ternary Search Tree – usado principalmente para búsquedas iterativas de forma ordenada).

 public class TreeMap extends AbstractMap implements SortedMap, Cloneable, Serializable 

En NUT-SHELL HashMap : da datos en O (1), sin ordenar

TreeMap : da datos en O (log N), base 2. con claves ordenadas

LinkedHashMap : es la tabla Hash con la capacidad de la lista vinculada (pensar en Indexed-SkipList) para almacenar datos de la manera en que se inserta en el árbol. El más adecuado para implementar LRU (utilizado menos recientemente).

Las siguientes son las principales diferencias entre HashMap y TreeMap

  1. HashMap no mantiene ningún orden. En otras palabras, HashMap no ofrece ninguna garantía de que el elemento insertado primero se imprima primero, donde al igual que TreeSet, los elementos TreeMap también se ordenan de acuerdo con el orden natural de sus elementos

  2. Uso de implementación de HashMap interno Hashing y TreeMap usan internamente la implementación de árbol rojo-negro.

  3. HashMap puede almacenar una clave nula y muchos valores nulos. TreeMap no puede contener claves nulas, pero puede contener muchos valores nulos.

  4. HashMap toma rendimiento de tiempo constante para las operaciones básicas como get y put, es decir, O (1). De acuerdo con los documentos de Oracle, TreeMap proporciona un costo de tiempo de registro (n) garantizado para el método get y put.

  5. HashMap es mucho más rápido que TreeMap, ya que el tiempo de rendimiento de HashMap es constante en comparación con el tiempo de registro TreeMap para la mayoría de las operaciones.

  6. HashMap usa el método equals () en comparación mientras que TreeMap usa el método compareTo () para mantener el orden.

  7. HashMap implementa la interfaz Map mientras que TreeMap implementa la interfaz NavigableMap.

Estas son implementaciones diferentes de la misma interfaz. Cada implementación tiene algunas ventajas y algunas desventajas (inserción rápida, búsqueda lenta) o viceversa.

Para más detalles, consulte el javadoc de TreeMap , HashMap , LinkedHashMap .

El mapa Hash no conserva el orden de inserción.
Ejemplo. Hashmap Si está insertando claves como

 1 3 5 9 4 6 7 15 3 10 

Puede almacenarlo como

 4 6 5 9 3 10 1 3 7 15 

Linked Hashmap conserva el orden de inserción.

Ejemplo.
Si está insertando claves

 1 3 5 9 4 6 7 15 3 10 

Lo almacenará como

 1 3 5 9 4 6 7 15 3 10 

lo mismo que insertamos.

El mapa de árbol almacena los valles en orden creciente de claves. Ejemplo.
Si está insertando claves

 1 3 5 9 4 6 7 15 3 10 

Lo almacenará como

 1 3 3 10 4 6 5 9 7 15 

Todos ofrecen un mapa de clave-> valor y una forma de iterar a través de las teclas. La distinción más importante entre estas clases son las garantías de tiempo y el orden de las claves.

  1. HashMap ofrece 0 (1) búsqueda e inserción. Sin embargo, si repites las teclas, el orden de las teclas es esencialmente arbitrario. Se implementa mediante una matriz de listas vinculadas.
  2. TreeMap ofrece la búsqueda e inserción de O (log N). Las claves están ordenadas, por lo que si necesita repetir las claves en orden ordenado, puede hacerlo. Esto significa que las claves deben implementar la interfaz Comparable. TreeMap es implementado por un Árbol Rojo-Negro.
  3. LinkedHashMap ofrece 0 (1) búsqueda e inserción. Las claves se ordenan según su orden de inserción. Se implementa mediante cubos doblemente vinculados.

Imagine que pasó un TreeMap, HashMap y LinkedHashMap vacíos en la siguiente función:

 void insertAndPrint(AbstractMap map) { int[] array= {1, -1, 0}; for (int x : array) { map.put(x, Integer.toString(x)); } for (int k: map.keySet()) { System.out.print(k + ", "); } } 

El resultado de cada uno se verá como los resultados a continuación.

Para HashMap, el resultado fue, en mis propias pruebas, {0, 1, -1}, pero podría ser cualquier pedido. No hay garantía en el pedido.
Treemap, la salida fue, {-1, 0, 1}
LinkedList, el resultado fue {1, -1, 0}

  • HashMap:

    • La orden no se mantiene
    • Más rápido que HashMap y LinkedHashMap
    • Se usa para almacenar un montón de objetos
  • LinkedHashMap:

    • Se mantendrá el orden de inserción LinkedHashMap
    • Más lento que HashMap y más rápido que TreeMap
    • Si desea mantener un orden de inserción, use esto.
  • TreeMap:

    • TreeMap es un mapeo basado en árbol
    • TreeMap seguirá el orden natural de la clave
    • Más lento que HashMap y LinkedHashMap
    • Use TreeMap cuando necesite mantener un orden natural (predeterminado)

HashMap
puede contener una clave nula.

HashMap no mantiene orden.

TreeMap

TreeMap no puede contener ninguna tecla nula.

TreeMap mantiene el orden ascendente.

LinkedHashMap

LinkedHashMap se puede usar para mantener el orden de inserción, en qué teclas se insertan en Map o también se puede usar para mantener una orden de acceso, a qué teclas se accede.

Ejemplos ::

1) HashMap map = new HashMap ();

  map.put(null, "Kamran"); map.put(2, "Ali"); map.put(5, "From"); map.put(4, "Dir");`enter code here` map.put(3, "Lower"); for (Map.Entry m : map.entrySet()) { System.out.println(m.getKey() + " " + m.getValue()); } 

2) TreeMap map = new TreeMap ();

  map.put(1, "Kamran"); map.put(2, "Ali"); map.put(5, "From"); map.put(4, "Dir"); map.put(3, "Lower"); for (Map.Entry m : map.entrySet()) { System.out.println(m.getKey() + " " + m.getValue()); } 

3) LinkedHashMap map = new LinkedHashMap ();

  map.put(1, "Kamran"); map.put(2, "Ali"); map.put(5, "From"); map.put(4, "Dir"); map.put(3, "Lower"); for (Map.Entry m : map.entrySet()) { System.out.println(m.getKey() + " " + m.getValue()); }