mapa - map ordenado java




Diferença entre HashMap, LinkedHashMap e TreeMap (10)

Qual é a diferença entre HashMap , LinkedHashMap e LinkedHashMap em Java? Eu não vejo nenhuma diferença na saída como todos os três tem keySet e values . O que são 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());

O HashMap não faz absolutamente nenhuma garantia sobre a ordem de iteração. Ele pode (e vai) até mudar completamente quando novos elementos são adicionados. O TreeMap irá iterar de acordo com a "ordenação natural" das chaves de acordo com o método compareTo () (ou com um Comparador fornecido externamente). Além disso, ele implementa a interface SortedMap, 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

Veja como o desempenho varia.

Mapa de árvore que é uma implementação do mapa ordenado. A complexidade da operação put, get e containsKey é O (log n) devido ao ordenamento Natural


HashMap

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

HashTable

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

LinkedHashMap

  • É ordenado versão da implementação de mapa
  • Baseado em estruturas de dados de lista e hash vinculadas

TreeMap

  • Versão ordenada e filtrada
  • baseado em estruturas de dados de hashing

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 TreeMap também são classificados de acordo com a ordenação natural de seus elementos.

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

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

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

  5. O HashMap é muito mais rápido que o TreeMap, já que o tempo de desempenho do HashMap é constante em relação ao tempo de registro TreeMap para a 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 ordenação.

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


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

  • HashMap - Mais útil ao procurar uma implementação de melhor desempenho (rápida).
  • TreeMap (interface SortedMap) - Mais útil quando estou preocupado em classificar ou iterar as chaves em uma ordem específica que eu defino.
  • LinkedHashMap - Combina vantagens de ordenação garantida 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, sobrescrevendo o método removeEldestEntry() . Isso permite criar um objeto Cache que pode expirar os dados usando alguns critérios definidos por você.

Eu prefiro 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               ║
╚══════════════╩═══════════════════════════════════════════════════════════════╝

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

1  3
5  9
4   6
7   15
3   10

Pode armazenar como

4  6
5  9
3  10
1  3
7  15

Hashmap vinculado preserva a ordem de inserção.

Exemplo.
Se você está 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 nós inserimos.

Mapa de árvore armazena os vales em Ordem crescente de chaves. Exemplo.
Se você está 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

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

  • HashMap faz absolutamente nenhuma garantia sobre a ordem de iteração. Ele pode (e vai) até mudar completamente quando novos elementos são adicionados.
  • TreeMap irá iterar de acordo com a "ordenação natural" das chaves de acordo com o método compareTo() (ou com um Comparator fornecido externamente). Além disso, ele implementa a interface SortedMap , 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, o Hashtable é uma classe obsoleta dos dias do Java 1.1 antes da existência do framework de coleções. Ele não deve mais ser usado, porque sua API está repleta 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 vez de Hashtable.


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

  1. HashMap oferece 0 (1) pesquisa e inserção. Se você percorrer as chaves, a ordem das chaves é essencialmente arbitrária. Ele é implementado por uma matriz de listas vinculadas.
  2. TreeMap oferece pesquisa e inserção de O (log N). As chaves são ordenadas, então se você precisar iterar pelas chaves na ordem de classificação, você pode. Isso significa que as chaves devem implementar a interface Comparable. O TreeMap é implementado por uma Red-Black Tree.
  3. LinkedHashMap oferece 0 (1) pesquisa e inserção. As chaves são ordenadas por seu pedido de inserção. É implementado por baldes duplamente ligados.

Imagine que você tenha passado por um TreeMap, HashMap e LinkedHashMap vazios na 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 para cada um será semelhante aos resultados abaixo.

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


Veja onde cada classe está na hierarquia de classes no diagrama a seguir ( maior ). O SortedMap implementa SortedMap e SortedMap enquanto o HashMap não.

HashTable é obsoleto e a classe ConcurrentHashMap correspondente deve ser usada.


HashMap
pode conter uma chave nula.

HashMap não mantém nenhum pedido.

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, no qual as chaves são inseridas no Mapa ou também para manter uma ordem de acesso, na qual as chaves são acessadas.

Exemplos ::

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




map