Diferença entre HashMap, LinkedHashMap e TreeMap

958

Qual é a diferença entre HashMap, LinkedHashMape TreeMapem Java? Não vejo diferença na saída, pois todos os três têm keySete values. O que são 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());
Kevin
fonte

Respostas:

1161

Todas as três classes implementam a Mapinterface e oferecem principalmente a mesma funcionalidade. A diferença mais importante é a ordem na qual a iteração através das entradas ocorrerá:

  • HashMapnão oferece absolutamente nenhuma garantia sobre a ordem de iteração. Pode (e irá) mudar completamente quando novos elementos são adicionados.
  • TreeMapiterará de acordo com a "ordem natural" das chaves, de acordo com o compareTo()método (ou fornecido externamente Comparator). Além disso, ele implementa a SortedMapinterface, que contém métodos que dependem dessa ordem de classificação.
  • LinkedHashMap irá iterar na ordem em que as entradas foram colocadas no mapa

"Hashtable" é o nome genérico para mapas baseados em hash. No contexto da API Java, Hashtableé uma classe obsoleta desde os dias do Java 1.1 antes da existência da estrutura de coleções. Ele não deve mais ser usado, porque sua API está cheia de métodos obsoletos que duplicam a funcionalidade e seus métodos são sincronizados (o que pode diminuir o desempenho e geralmente é inútil). Use ConcurrentHashMap em vez de Hashtable.

Michael Borgwardt
fonte
2
O que é o Mapa atualmente e qual é a diferença entre Map, HashMap e Hashtables.
22410 Kevin
5
@ theband: o mapa é uma interface. O HashMap e o Hashtable os implementam; como escrevi, o Hashtable é uma classe herdada.
Michael Borgwardt
98
Uma diferença notável entre Hashtablee HashMapé que em um Hashtable, "nem a chave nem o valor podem ser nulos". Essa restrição não existe neste último.
aioobe
4
@AshkanN: Sim - de fato, essas são as formas padrão de implementar a classificação. O TreeMap possui um construtor que utiliza um Comparator e, se nenhum for fornecido, espera que todos os objetos adicionados implementem o Comparable.
Michael Borgwardt
4
Você pode escolher se deseja a iteração LinkedHashMap em ordem de inserção ou ordem de acesso.
lbalazscs
1608

Eu prefiro a apresentação 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               ║
╚══════════════╩═══════════════════════════════════════════════════════════════╝
Sergii Shevchyk
fonte
14
Além da ordem de inserção, o LinkedHashMap também oferece suporte à ordem de acesso (ao usar o construtor com o parâmetro booleano da ordem de acesso).
Eyal Schneider
5
Caçambas vinculadas duplas? Eu acho que isso adiciona uma sobrecarga desnecessária na pesquisa do balde para operações de inserção / remoção (porque ele precisa procurar o balde certo para colocar o objeto). Eu sempre pensei que as implementações do LinkedHashMap seriam semelhantes às de um mapa, mas com uma sobrecarga extra de "lista de entradas" (pode ser uma lista vinculada) usada para fins de iteração. Você tem certeza, shevchyk? Se sim, você pode me explicar ou fornecer alguns links on-line que apoiam sua declaração?
Sai Dubbaka
5
O @SaiDubbaka LinkedHashMap possui os buckets com link duplo MAS TAMBÉM a tabela de buckets que o HashMap possui. Não está substituindo. Isso significa que o acesso aos buckets é feito da mesma maneira que no HashMap, pois a lista vinculada existe para iteração apenas na ordem de inserção (ou ordem de acesso).
Gerardo Lastra
5
Pode valer a pena mencionar, que O (1) é o melhor cenário (que nós não costumamos chamar de O, consulte esta pergunta )
Sebastian S
4
Também vale a pena notar que O (1) nem sempre é melhor que O (log n); se você tiver uma chave muito longa, algo baseado em BSTs poderá ser muito mais rápido do que algo que precise executar um hash O (n) em toda a chave antes de poder fazer qualquer coisa.
Fund Monica's Lawsuit
65

Todos os três representam o mapeamento de chaves exclusivas para valores e, portanto, implementam a interface Map .

  1. HashMap é um mapa baseado no hash das teclas. Ele suporta operações O / 1 get / put. As chaves devem ter implementações consistentes hashCode()eequals() para que isso funcione.

  2. O LinkedHashMap é muito semelhante ao HashMap, mas adiciona reconhecimento à ordem na qual os itens são adicionados (ou acessados), portanto, a ordem de iteração é igual à ordem de inserção (ou ordem de acesso, dependendo dos parâmetros de construção).

  3. TreeMap é um mapeamento baseado em árvore. Suas operações put / get levam tempo O (log n). Requer que os itens tenham algum mecanismo de comparação, seja com Comparável ou Comparador. A ordem da iteração é determinada por esse mecanismo.

Eyal Schneider
fonte
1
Portanto, se entendi corretamente, a única diferença entre o LinkedHashMap e o TreeMap é o desempenho, uma vez que a ordem de inserção é igual à ordem natural?
Moshe Shaham
19
@ MosheShaham Como ele disse no item 2: LinkedHashMapiterará na ordem de inserção, não na ordem natural. Portanto, se você adicionar (2,5,3)um a LinkedHashMape fizer um para cada um deles, ele retornará 2,5,3. Se fosse 2,5,3para um, TreeMapele retornará 2,3,5.
grinch
2
O mapa de árvores também tem muitos outros truques legais. Como mapas de cabeça e cauda.
Thomas Ahle
private TreeMap <String, Inteiro> mySection2 = new TreeMap <> (); mySection2.put ("abc1", 2); mySection2.put ("abc2", 5); mySection2.put ("abc3", 3); for (Inteiro x: mySection2.values ​​()) {Log.e ("LOG", "TreeMap ====" + x); } Isso está me dando o mesmo pedido em que os itens foram inseridos? Sugira como é diferente do LinkedHashMaps?
B.shruti
2
@ B.shruti: Isso ocorre porque seu pedido de inserção corresponde à ordem lexicográfica de suas chaves ("abc1", "abc2", "abc3"). Se você inserir em uma ordem diferente, seu código ainda iterará de acordo com a ordem lexicográfica.
Eyal Schneider
47

Veja onde cada classe está na hierarquia de classes no diagrama a seguir ( maior ). TreeMap implementa SortedMape NavigableMapenquanto HashMapnão.

HashTableé obsoleto e a ConcurrentHashMapclasse correspondente deve ser usada. insira a descrição da imagem aqui

pierrotlefou
fonte
38

HashMap

  • Possui valores de par (chaves, valores)
  • SEM valores-chave de duplicação
  • não ordenado não classificado
  • permite uma chave nula e mais de um valor nulo

HashTable

  • mesmo que mapa de hash
  • não permite chaves e valores nulos

LinkedHashMap

  • É uma versão ordenada da implementação do mapa
  • Baseado em estruturas de dados de lista vinculada e hash

TreeMap

  • Versão ordenada e ordenada
  • com base em estruturas de dados de hash
Prem Kumar
fonte
3
O HashTable também é sincronizado. De qualquer forma ,, eu gosto da sua resposta, limpa e clara.
Surasin Tancharoen 8/11
35

Apenas mais algumas informações da minha própria experiência com mapas, sobre quando eu usaria cada um:

  • HashMap - Mais útil para procurar uma implementação (rápida) de melhor desempenho.
  • TreeMap (interface SortedMap) - Mais útil quando estou preocupado em poder classificar ou iterar sobre as chaves em uma ordem específica que eu defino.
  • LinkedHashMap - Combina vantagens de pedidos garantidos do TreeMap sem o aumento do custo de manutenção do TreeMap. (É quase tão rápido quanto o HashMap). Em particular, o LinkedHashMap também fornece um excelente ponto de partida para a criação de um objeto Cache, substituindo o removeEldestEntry()método. Isso permite criar um objeto de cache que pode expirar dados usando alguns critérios que você define.
Salmo Ogro33
fonte
10
Para ser mais preciso, o TreeMap não mantém os elementos em ordem. Mantém as chaves em ordem.
LS
17

Todas as três classes HashMap, TreeMape LinkedHashMapimplementa java.util.Mapa interface, e representa o mapeamento de chave única de valores.

HashMap

  1. A HashMapcontém valores com base na chave.

  2. Ele contém apenas elementos exclusivos.

  3. Pode ter uma chave nula e vários valores nulos.

  4. Não mantém nenhuma ordem .

    public class HashMap<K,V> extends AbstractMap<K,V> implements Map<K,V>, Cloneable, Serializable

LinkedHashMap

  1. A LinkedHashMapcontém valores com base na chave.
  2. Ele contém apenas elementos exclusivos.
  3. Pode ter uma chave nula e vários valores nulos.
  4. É o mesmo que o HashMap, em vez disso, mantém a ordem de inserção . // Veja a desaceleração da classe abaixo

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

TreeMap

  1. A TreeMapcontém valores com base na chave. Ele implementa a interface NavigableMap e estende a classe AbstractMap.
  2. Ele contém apenas elementos exclusivos.
  3. Ele não pode ter chave nula, mas pode ter vários valores nulos.
  4. É o mesmo que HashMapmanter a ordem crescente (ordenada usando a ordem natural de sua chave).

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

Hashtable

  1. Um Hashtable é uma matriz de lista. Cada lista é conhecida como balde. A posição do bucket é identificada chamando o método hashcode (). Um Hashtable contém valores com base na chave.
  2. Ele contém apenas elementos exclusivos.
  3. Pode não ter nenhuma chave ou valor nulo.
  4. Está sincronizado .
  5. É uma classe herdada.

    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

roottraveller
fonte
A notação Big-O do HashMap não deve ser O (1). Esse é o melhor caso, e as hashtables têm O (n) como seu pior cenário. Isso é suportado pelo seu link.
Haakon Løtveit 11/08/19
@ HaakonLøtveit Eu também irá sugerir para ir para o código real aqui - grepcode.com/file/repository.grepcode.com/java/root/jdk/openjdk/...
roottraveller
AINDA diz que é O (n) no pior caso. É um conceito matemático, e você não pode dizer que é O (1), a menos que seja realmente O (1). Você também está assumindo algumas funções de hash realmente boas aqui. Quero dizer, poderíamos usar algo como a classe TerribleHashKey {@Override hashCode () {return 4; / * Determinado pelo lançamento justo de dados * /}} e use isso como uma chave para outras coisas divertidas. Ter uma alta probabilidade de O (1) e ter O (1) não é o mesmo. As pessoas vêm aqui para obter ajuda com a lição de casa. Não vamos estragar suas notas ..;)
Haakon Løtveit
E vale a pena notar que no Java 8 você tem o pior caso de O (log (n)) se tiver mais de 8 buckets, consulte grepcode.com/file/repository.grepcode.com/java/root/jdk/openjdk /… Para detalhes sobre isso.
Haakon Løtveit 11/08/19
14

O HashMap não garante absolutamente nada sobre a ordem da iteração. Pode (e irá) mudar completamente quando novos elementos são adicionados. O TreeMap irá iterar de acordo com a "ordem natural" das chaves, de acordo com o método compareTo () (ou um Comparador fornecido externamente). Além disso, implementa a interface SortedMap, que contém métodos que dependem dessa ordem de classificação. O LinkedHashMap iterará na ordem em que as entradas foram colocadas no mapa

Veja como o desempenho varia. insira a descrição da imagem aqui

Mapa em árvore que é uma implementação do mapa Ordenado. A complexidade da operação put, get e containsKey é O (log n) devido à ordem Natural

Ruchira Gayan Ranaweera
fonte
9

@Mit: SortedMapé uma interface, enquanto que TreeMapé uma classe que implementa a SortedMapinterface. Isso significa que se segue o protocolo que SortedMapsolicita aos implementadores. Uma árvore, a menos que seja implementada como árvore de pesquisa, não pode fornecer dados ordenados porque a árvore pode ser qualquer tipo de árvore. Portanto, para fazer o TreeMap funcionar como a ordem classificada, ele implementa o SortedMap (por exemplo, Árvore de pesquisa binária - BST, BST balanceada como AVL e RB Tree, e até Árvore de pesquisa ternária - usada principalmente para pesquisas iterativas de maneira ordenada).

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

Em NUT-SHELL HashMap: fornece dados em O (1), sem pedidos

TreeMap : fornece dados em O (log N), base 2. com chaves ordenadas

LinkedHashMap: é a tabela Hash com capacidade de lista vinculada (pense em SkipList indexado) para armazenar dados da maneira que são inseridos na árvore. Mais adequado para implementar a LRU (usada menos recentemente).

siddhusingh
fonte
6

A seguir, estão as principais diferenças entre o HashMap e o TreeMap

  1. O HashMap não mantém nenhum pedido. Em outras palavras, o HashMap não fornece nenhuma garantia de que o elemento inserido primeiro será impresso primeiro, onde, assim como o TreeSet, os elementos do TreeMap também são classificados de acordo com a ordem natural de seus elementos.

  2. A implementação interna do HashMap usa Hashing e o TreeMap internamente usa a implementação da árvore Vermelho-Preto.

  3. O HashMap pode armazenar uma chave nula e muitos valores nulos.TreeMap não pode conter chaves nulas, mas pode conter muitos valores nulos.

  4. O HashMap possui desempenho em tempo constante para operações básicas como get e put, ou seja, O (1). De acordo com os documentos do Oracle, o TreeMap fornece um custo garantido de log (n) para o método get e put.

  5. O HashMap é muito mais rápido que o TreeMap, pois o tempo de desempenho do HashMap é constante em relação ao tempo de log do TreeMap na maioria das operações.

  6. O HashMap usa o método equals () em comparação, enquanto o TreeMap usa o método compareTo () para manter a ordem.

  7. O HashMap implementa a interface Map, enquanto o TreeMap implementa a interface NavigableMap.

Vijay Barot
fonte
5

Estas são implementações diferentes da mesma interface. Cada implementação tem algumas vantagens e algumas desvantagens (inserção rápida, pesquisa lenta) ou vice-versa.

Para obter detalhes, consulte o javadoc do TreeMap , HashMap , LinkedHashMap .

tangens
fonte
O que são Hashtables, na verdade, e o que as diferencia de um Mapa.
22710 Kevin
5

O mapa de hash não preserva o pedido de inserção.
Exemplo. Hashmap Se você estiver inserindo chaves como

1  3
5  9
4   6
7   15
3   10

Pode armazená-lo como

4  6
5  9
3  10
1  3
7  15

O Hashmap vinculado preserva o pedido de inserção.

Exemplo.
Se você estiver inserindo chaves

1  3
5  9
4   6
7   15
3   10

Ele irá armazená-lo como

1  3
5  9
4   6
7   15
3   10

mesmo que inserimos.

O mapa em árvore armazena os valores em Ordem crescente de chaves. Exemplo.
Se você estiver inserindo chaves

1  3
5  9
4   6
7   15
3   10

Ele irá armazená-lo como

1  3
3  10
4   6
5   9
7   15
Shivam Shukla
fonte
4
  • HashMap:

    • O pedido não mantém
    • Mais rápido que o LinkedHashMap
    • Usado para armazenar heap de objetos
  • LinkedHashMap:

    • O pedido de inserção do LinkedHashMap será mantido
    • Mais lento que o HashMap e mais rápido que o TreeMap
    • Se você deseja manter um pedido de inserção, use isso.
  • TreeMap:

    • TreeMap é um mapeamento baseado em árvore
    • O TreeMap seguirá a ordem natural das teclas
    • Mais lento que HashMap e LinkedHashMap
    • Use o TreeMap quando precisar manter a ordem natural (padrão)
Premraj
fonte
1

Todos oferecem um mapa de chave-> valor e uma maneira de iterar pelas chaves. A distinção mais importante entre essas classes são as garantias de tempo e a ordem das chaves.

  1. O HashMap oferece 0 (1) pesquisa e inserção. Se você percorrer as chaves, no entanto, a ordem das chaves é essencialmente arbitrária. É implementado por uma matriz de listas vinculadas.
  2. O TreeMap oferece pesquisa e inserção de O (log N). As chaves são ordenadas; portanto, se você precisar percorrer as chaves em ordem ordenada, poderá fazê-lo. Isso significa que as chaves devem implementar a interface Comparable.TreeMap é implementada por uma Árvore Vermelho-Preta.
  3. O LinkedHashMap oferece 0 (1) pesquisa e inserção. As chaves são ordenadas por ordem de inserção. É implementado por buckets duplamente vinculados.

Imagine que você passou um TreeMap, HashMap e LinkedHashMap vazios para a seguinte função:

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 + ", ");
  }
}

A saída de cada um será semelhante aos resultados abaixo.

Para o HashMap, a saída foi, em meus próprios testes, {0, 1, -1}, mas pode ser qualquer ordem. Não há garantia no pedido.
Treemap, a saída foi {-1, 0, 1}
LinkedList, a saída foi {1, -1, 0}

Jitendra
fonte
1

Embora haja muitas respostas excelentes aqui, gostaria de apresentar minha própria tabela descrevendo as várias Map implementações incluídas no Java 11.

Podemos ver essas diferenças listadas no gráfico da tabela:

  • HashMapé o uso Map geral usado quando você não tem necessidades especiais.
  • LinkedHashMapestende HashMap, adicionando este comportamento: Mantém um pedido, o pedido em que as entradas foram originalmente adicionadas . Alterar o valor da entrada do valor-chave não altera seu lugar no pedido.
  • TreeMaptambém mantém uma ordem, mas usa (a) a ordem "natural" , significando o valor do compareTométodo nos objetos-chave definidos na Comparableinterface ou (b) chama uma Comparatorimplementação você fornece.
  • NULL s: TreeMapse não permitir que um NULL como a chave , enquanto HashMap&LinkedHashMap fazer.
    • Todos os três permitem NULL como o valor.
  • HashTableé legado , do Java 1 . Suplantado pela ConcurrentHashMapclasse. A citação do Javadoc: ConcurrentHashMapobedece à mesma especificação funcional que Hashtablee inclui versões dos métodos correspondentes a cada método de Hashtable.

Tabela de implementações de mapas no Java 11, comparando seus recursos

Basil Bourque
fonte
0

HashMap
pode conter uma chave nula.

O HashMap não mantém pedidos.

TreeMap

O TreeMap não pode conter nenhuma chave nula.

O TreeMap mantém a ordem crescente.

LinkedHashMap

O LinkedHashMap pode ser usado para manter a ordem de inserção, na qual as chaves são inseridas no Map ou também para manter uma ordem de acesso, na qual as chaves são acessadas.

Exemplos ::

1) mapa HashMap = novo 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 do TreeMap = novo 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 = novo 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());
    }
Kamran
fonte
0

O mais importante entre todos os três é como eles salvam a ordem das entradas.

HashMap- Não salva a ordem das entradas. por exemplo.

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());
        }
    }

Saída para HashMap

LinkedHashMap: Salva a ordem na qual as entradas foram feitas. por exemplo:

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());
        }
    }

Saída do LinkedHashMap

TreeMap: Salva as entradas em ordem crescente das teclas. por exemplo:

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());
        }
    }

Saída do TreeMap

Animesh Jaiswal
fonte