HashMap e TreeMap fazem parte da estrutura de coleção .

HashMap
A classe java.util.HashMap é uma implementação baseada em Hashing. No HashMap, temos uma chave e um par de valores<key value="">.</key> 
 HashMap<K, V> hmap = new HashMap<K, V>();

Vamos considerar o exemplo abaixo onde temos que contar as ocorrências de cada inteiro em um determinado array de inteiros.

Input: arr[] = {10, 3, 5, 10, 3, 5, 10};
Output: Frequency of 10 is 3
        Frequency of 3 is 2
        Frequency of 5 is 2

/* Java program to print frequencies of all elements using 
   HashMap */
import java.util.*;
  
class Main
{
    // This function prints frequencies of all elements
    static void printFreq(int arr[])
    {
        // Creates an empty HashMap
        HashMap<Integer, Integer> hmap = 
                     new HashMap<Integer, Integer>();
  
        // Traverse through the given array
        for (int i = 0; i < arr.length; i++)
        {
            Integer c = hmap.get(arr[i]);
  
            // If this is first occurrence of element 
            if (hmap.get(arr[i]) == null)
               hmap.put(arr[i], 1);
  
            // If elements already exists in hash map
            else 
              hmap.put(arr[i], ++c);
        }
  
        // Print result
        for (Map.Entry m:hmap.entrySet())
          System.out.println("Frequency of " + m.getKey() + 
                             " is " + m.getValue());
    }
  
    // Driver method to test above method
    public static void main (String[] args)
    {
        int arr[] = {10, 34, 5, 10, 3, 5, 10};
        printFreq(arr);
    }
}

Saída:

Frequency of 34 is 1
Frequency of 3 is 1
Frequency of 5 is 2
Frequency of 10 is 3

Pontos chave

  • O HashMap não mantém nenhuma ordem, nem com base na chave, nem com base no valor. Se quisermos que as chaves sejam mantidas em uma ordem de classificação, precisamos usar TreeMap.
  • Complexidade : as operações get / put / containsKey() são O (1) no caso médio, mas não podemos garantir isso, pois tudo depende de quanto tempo leva para calcular o hash.

Aplicação:
HashMap é basicamente uma implementação de hashing . Portanto, sempre que precisarmos de hash com pares de valores-chave, podemos usar HashMap. Por exemplo, em aplicativos da Web, o nome de usuário é armazenado como uma chave e os dados do usuário são armazenados como um valor no HashMap, para uma recuperação mais rápida dos dados do usuário correspondentes a um nome de usuário.

TreeMap
TreeMap pode ser um pouco útil quando precisamos apenas armazenar elementos únicos em uma ordem de classificação. Java.util.TreeMap usa um árvore vermelho-preto no fundo, o que garante que não haja duplicatas; além disso, ele também mantém os elementos em uma ordem de classificação. 
 TreeMap<K, V> hmap = new TreeMap<K, V>();

Abaixo está a implementação baseada em TreeMap do mesmo problema. Esta solução tem mais complexidade de tempo O (nLogn) do que a anterior que possui O (n). A vantagem desse método é que obtemos os elementos em ordem de classificação.

/* Java program to print frequencies of all elements using 
   TreeMap */
import java.util.*;
  
class Main
{
    // This function prints frequencies of all elements
    static void printFreq(int arr[])
    {
        // Creates an empty TreeMap
        TreeMap<Integer, Integer> tmap =
                     new TreeMap<Integer, Integer>();
  
        // Traverse through the given array
        for (int i = 0; i < arr.length; i++)
        {
            Integer c = tmap.get(arr[i]);
  
            // If this is first occurrence of element   
            if (tmap.get(arr[i]) == null)
               tmap.put(arr[i], 1);
  
            // If elements already exists in hash map
            else
              tmap.put(arr[i], ++c);
        }
  
        // Print result
        for (Map.Entry m:tmap.entrySet())
          System.out.println("Frequency of " + m.getKey() + 
                             " is " + m.getValue());
    }
  
    // Driver method to test above method
    public static void main (String[] args)
    {
        int arr[] = {10, 34, 5, 10, 3, 5, 10};
        printFreq(arr);
    }
}

Saída:

Frequency of 3 is 1
Frequency of 5 is 2
Frequency of 10 is 3
Frequency of 34 is 1

Pontos chave

  • Para operações como add, remove, containsKey, a complexidade do tempo é O (log n onde n é o número de elementos presentes no TreeMap.
  • TreeMap sempre mantém os elementos em uma ordem de classificação (crescente), enquanto os elementos em um HashMap não têm ordem. TreeMap também fornece alguns métodos interessantes para o primeiro, último, piso e teto de chaves.

Visão geral:
  1. HashMap implementa a interface Map enquanto TreeMap implementa a interface SortedMap. Uma interface de Mapa Ordenado é filha de Mapa.
  2. HashMap implementa Hashing, enquanto TreeMap implementa Red-Black Tree (uma árvore de busca binária de auto-equilíbrio). Portanto, todas as diferenças entre Hashing e árvore de pesquisa binária balanceada se aplicam aqui.
  3. Ambos HashMap e TreeMap têm suas contrapartes HashSet e TreeSet. HashSet e TreeSet implementam a interface Set . Em HashSet e TreeSet, temos apenas a chave, nenhum valor, estes são usados ​​principalmente para ver a presença / ausência em um conjunto. Para o problema acima, não podemos usar HashSet (ou TreeSet), pois não podemos armazenar contagens. Um exemplo de problema em que preferiríamos HashSet (ou TreeSet) em vez de HashMap (ou TreeMap) é imprimir todos os elementos distintos em um array.

coleção_interfaces

Artigos relacionados

Referências:
https://docs.oracle.com/javase/7/docs/api/java/util/Collection.html

Este artigo é uma contribuição de Chirag Agrawal . Se você gosta de GeeksforGeeks e gostaria de contribuir, você também pode escrever um artigo e enviá-lo para contrib@geeksforgeeks.org. Veja o seu artigo na página principal do GeeksforGeeks e ajude outros Geeks.

Escreva comentários se encontrar algo incorreto ou se quiser compartilhar mais informações sobre o tópico discutido acima