Diferencia entre HashMap, LinkedHashMap y TreeMap

¿Cuál es la diferencia entre HashMap, LinkedHashMapy TreeMapen Java? No veo ninguna diferencia en la salida ya que los tres tienen keySety values. ¿Qué son los Hashtables?

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 Mapinterfaz y ofrecen principalmente la misma funcionalidad. La diferencia más importante es el orden en que ocurrirá la iteración a través de las entradas:

• HashMapno garantiza en absoluto el orden de iteración. Puede (y lo hará) incluso cambiar por completo cuando se agregan nuevos elementos.
• TreeMapiterará de acuerdo con el "orden natural" de las teclas de acuerdo con su compareTo()método (o un suministrado externamente Comparator). Además, implementa la SortedMapinterfaz, que contiene métodos que dependen de este orden de clasificación.
• LinkedHashMap iterará 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, Hashtablees una clase obsoleta de los días de Java 1.1 antes de que existiera el marco de colecciones. Ya no debe usarse, porque su API está abarrotada de métodos obsoletos que duplican la funcionalidad, y sus métodos están sincronizados (lo que puede disminuir el rendimiento y generalmente 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 Map .

1. HashMap es un mapa basado en el hash de las claves. Admite operaciones de obtención / colocación de O (1). Las claves deben tener implementaciones consistentes de hashCode()yequals() para que esto funcione.

2. LinkedHashMap es muy similar a HashMap, pero agrega conciencia al orden en el que se agregan los elementos (o se accede a ellos), por lo que el orden de iteración es el mismo que el orden de inserción (u orden de acceso, según los parámetros de construcción).

3. TreeMap es un mapeo basado en árboles. Sus operaciones put / get toman tiempo O (log n). Requiere que los elementos tengan algún mecanismo de comparación, ya sea con Comparable o Comparator. 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 diagrama ( uno más grande ). TreeMap implementa SortedMapy NavigableMapmientras HashMapque no.

HashTablees obsoleto y se ConcurrentHashMapdebe usar la clase correspondiente .

HashMap

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

Tabla de picadillo

• igual que el mapa hash
• no permite claves nulas y valores nulos

LinkedHashMap

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

TreeMap

• Versión ordenada y ordenada
• basado en estructuras de datos hash

Solo un poco más de información 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 me preocupa poder ordenar o iterar sobre las teclas en un orden particular que defino.
• LinkedHashMap: combina las ventajas de un pedido garantizado de TreeMap sin el aumento del costo de mantenimiento de TreeMap. (Es casi tan rápido como el HashMap). En particular, LinkedHashMap también proporciona un excelente punto de partida para crear un objeto Cache al anular el removeEldestEntry()método. Esto le permite crear un objeto de caché que puede expirar datos utilizando algunos criterios que defina.

Las tres clases HashMap, TreeMape LinkedHashMapimplementa la java.util.Mapinterfaz, y representa la asignación de clave única a valores.

HashMap

1. A HashMapcontiene 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<K,V> extends AbstractMap<K,V> implements Map<K,V>, Cloneable, Serializable

LinkedHashMap

1. A LinkedHashMapcontiene 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 su lugar mantiene el orden de inserción . // Ver la desaceleración de la clase a continuación

   public class LinkedHashMap<K,V> extends HashMap<K,V> implements Map<K,V>

TreeMap

1. A TreeMapcontiene valores basados ​​en la clave. Implementa la interfaz NavigableMap y extiende la clase AbstractMap.
2. Contiene solo elementos únicos.
3. No puede tener clave nula pero puede tener múltiples valores nulos.

4. Es lo mismo que en su HashMaplugar mantiene el orden ascendente (Ordenado usando el orden natural de su clave).

   public class TreeMap<K,V> extends AbstractMap<K,V> implements NavigableMap<K,V>, Cloneable, Serializable

Tabla de picadillo

1. Una tabla hash es una matriz de lista. Cada lista se conoce como un cubo. La posición del depósito se identifica llamando al método hashcode (). Una tabla hash contiene valores basados ​​en la clave.
2. Contiene solo elementos únicos.
3. Es posible que no tenga ninguna clave o valor nulo.
4. Se sincroniza .

5. Es una clase heredada.

   public class Hashtable<K,V> extends Dictionary<K,V> implements Map<K,V>, 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 (y lo hará) incluso cambiar por completo cuando se agregan nuevos elementos. TreeMap iterará de acuerdo con el "orden natural" de las teclas 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 iterará en el orden en que las entradas se colocaron en el mapa

Mira cómo varía el rendimiento ...

Mapa de árbol que es una implementación del mapa ordenado. La complejidad de la operación de poner, obtener y contiene clave es O (log n) debido al orden natural

@Amit: SortedMapes una interfaz, mientras que TreeMapes una clase que implementa la SortedMapinterfaz. Eso significa que sigue el protocolo que SortedMaple pide a sus implementadores que hagan. Un árbol, a menos que se implemente como árbol de búsqueda, no puede proporcionarle datos ordenados porque el árbol puede ser cualquier tipo de árbol. Entonces, para que TreeMap funcione como orden ordenado, implementa SortedMap (por ejemplo, Binary Search Tree - BST, BST balanceado como AVL y RB Tree, incluso Ternary Search Tree, utilizado principalmente para búsquedas iterativas en forma ordenada).

public class TreeMap<K,V>
extends AbstractMap<K,V>
implements SortedMap<K,V>, 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 una tabla Hash con capacidad de lista vinculada (piense en indexed-SkipList) para almacenar datos en la forma en que se insertan en el árbol. El más adecuado para implementar LRU (menos utilizado recientemente).

Los siguientes son las principales diferencias entre HashMap y TreeMap

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

2. La implementación interna de HashMap usa Hashing y TreeMap usa 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 un rendimiento de tiempo constante para las operaciones básicas como get and put, es decir, O (1). Según 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 con respecto al 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 desventajas (inserción rápida, búsqueda lenta) o viceversa.

Para obtener más información, 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 llaves. 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

• HashMap:

  • El orden no se mantiene
  • Más rápido que LinkedHashMap
  • Se utiliza para almacenar el montón de objetos.

• LinkedHashMap:

  • Se mantendrá el orden de inserción de 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 árboles
  • TreeMap seguirá el orden natural de las claves
  • Más lento que HashMap y LinkedHashMap
  • Use TreeMap cuando necesite mantener un orden natural (predeterminado)

Todos ofrecen un mapa clave-> valor y una forma de recorrer 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 itera por las teclas, el orden de las teclas es esencialmente arbitrario. Se implementa mediante una serie de listas vinculadas.
2. TreeMap ofrece búsqueda e inserción de O (log N). Las claves están ordenadas, por lo que si necesita recorrer las claves en orden ordenado, puede hacerlo. Esto significa que las claves deben implementar la interfaz comparable. TreeMap se implementa mediante un árbol rojo-negro.
3. LinkedHashMap ofrece 0 (1) búsqueda e inserción. Las claves se ordenan por su orden de inserción. Se implementa mediante cubos doblemente vinculados.

Imagina que pasaste un TreeMap, HashMap y LinkedHashMap vacíos a la siguiente función:

void insertAndPrint(AbstractMap<Integer, String> 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 para cada uno se verá como los resultados a continuación.

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

Si bien hay muchas respuestas excelentes aquí, me gustaría presentar mi propia tabla que describe las diversas Mapimplementaciones incluidas con Java 11.

Podemos ver estas diferencias en el gráfico de la tabla:

• HashMapes el propósito general Map comúnmente usado cuando no tienes necesidades especiales.
• LinkedHashMapse extiende HashMap, agregando este comportamiento: Mantiene un orden, el orden en que se agregaron originalmente las entradas . La alteración del valor para la entrada de valor clave no altera su lugar en el orden.
• TreeMaptambién mantiene un orden, pero usa (a) el orden "natural" , que significa el valor del compareTométodo en los objetos clave definidos en la Comparableinterfaz, o (b) invoca una Comparatorimplementación que usted proporciona.
  • TreeMapimplementa tanto la SortedMapinterfaz como su sucesor, la NavigableMapinterfaz.
• NULL s: TreeMapQué no permiten un NULL como la clave , mientras que HashMapy LinkedHashMaplo hacen.
  • Los tres permiten NULL como valor.
• HashTablees heredado , de Java 1 . Suplantado por la ConcurrentHashMapclase. Citando el Javadoc: ConcurrentHashMapobedece la misma especificación funcional Hashtablee incluye versiones de los métodos correspondientes a cada método de Hashtable.

HashMap
puede contener una clave nula.

HashMap no mantiene ningún orden.

TreeMap

TreeMap no puede contener ninguna clave nula.

TreeMap mantiene el orden ascendente.

LinkedHashMap

LinkedHashMap se puede utilizar para mantener el orden de inserción, en el que se insertan las claves en el Mapa o también se puede utilizar para mantener un orden de acceso, en el que se accede a las claves.

Ejemplos ::

1) Mapa de HashMap = nuevo 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) Mapa de TreeMap = nuevo 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) Mapa LinkedHashMap = nuevo 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());
    }

El más importante entre los tres es cómo guardan el orden de las entradas.

HashMap- No guarda el orden de las entradas. p.ej.

public static void main(String[] args){
        HashMap<String,Integer> hashMap = new HashMap<>();
        hashMap.put("First",1);// First ---> 1 is put first in the map
        hashMap.put("Second",2);//Second ---> 2 is put second in the map
        hashMap.put("Third",3); // Third--->3 is put third in the map
        for(Map.Entry<String,Integer> entry : hashMap.entrySet())
        {
            System.out.println(entry.getKey()+"--->"+entry.getValue());
        }
    }

LinkedHashMap: Guarda el orden en que se hicieron las entradas. p.ej:

public static void main(String[] args){
        LinkedHashMap<String,Integer> linkedHashMap = new LinkedHashMap<>();
        linkedHashMap.put("First",1);// First ---> 1 is put first in the map
        linkedHashMap.put("Second",2);//Second ---> 2 is put second in the map
        linkedHashMap.put("Third",3); // Third--->3 is put third in the map
        for(Map.Entry<String,Integer> entry : linkedHashMap.entrySet())
        {
            System.out.println(entry.getKey()+"--->"+entry.getValue());
        }
    }

TreeMap: Guarda las entradas en orden ascendente de las teclas. p.ej:

public static void main(String[] args) throws IOException {
        TreeMap<String,Integer> treeMap = new TreeMap<>();
        treeMap.put("A",1);// A---> 1 is put first in the map
        treeMap.put("C",2);//C---> 2 is put second in the map
        treeMap.put("B",3); //B--->3 is put third in the map
        for(Map.Entry<String,Integer> entry : treeMap.entrySet())
        {
            System.out.println(entry.getKey()+"--->"+entry.getValue());
        }
    }