HashMap y TreeMap en Java

HashMap y TreeMap son parte del marco de la colección .

 HashMap<K, V> hmap = new HashMap<K, V>();

Consideremos el siguiente ejemplo en el que tenemos que contar las ocurrencias de cada número entero en una array dada de números enteros.

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

Producción:

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

Puntos clave

• HashMap no mantiene ningún orden ni en función de la clave ni en función del valor. Si queremos que las claves se mantengan ordenadas, debemos usar TreeMap.
• Complejidad : las operaciones get/put/containsKey() son O(1) en el caso promedio, pero no podemos garantizarlo, ya que todo depende de cuánto tiempo lleva calcular el hash.

Aplicación:
HashMap es básicamente una implementación de hashing . Entonces, donde sea que necesitemos hash con pares de valores clave, podemos usar HashMap. Por ejemplo, en las aplicaciones web, el nombre de usuario se almacena como una clave y los datos del usuario se almacenan como un valor en HashMap, para una recuperación más rápida de los datos del usuario correspondientes a un nombre de usuario.

 TreeMap<K, V> hmap = new TreeMap<K, V>();

A continuación se muestra la implementación basada en TreeMap del mismo problema. Esta solución tiene más complejidad de tiempo O(nLogn) en comparación con la anterior que tiene O(n). La ventaja de este método es que obtenemos elementos ordenados.

/* 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);
    }
}

Producción:

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

Puntos clave

• Para operaciones como agregar, eliminar, contiene clave, la complejidad del tiempo es O (log n donde n es el número de elementos presentes en TreeMap.
• TreeMap siempre mantiene los elementos en un orden ordenado (creciente), mientras que los elementos en un HashMap no tienen ningún orden. TreeMap también proporciona algunos métodos geniales para la primera, la última, el piso y el techo de las teclas.

1. HashMap implementa la interfaz Map mientras que TreeMap implementa la interfaz SortedMap. Una interfaz de Mapa ordenado es un elemento secundario de Mapa.
2. HashMap implementa Hashing, mientras que TreeMap implementa Red-Black Tree (un árbol de búsqueda binario autoequilibrado). Por lo tanto , aquí se aplican todas las diferencias entre Hashing y Balanced Binary Search Tree .
3. Tanto HashMap como TreeMap tienen sus contrapartes HashSet y TreeSet. HashSet y TreeSet implementan la interfaz Set . En HashSet y TreeSet, solo tenemos clave, sin valor, estos se usan principalmente para ver presencia/ausencia en un conjunto. Para el problema anterior, no podemos usar HashSet (o TreeSet) ya que no podemos almacenar recuentos. Un problema de ejemplo en el que preferiríamos HashSet (o TreeSet) sobre HashMap (o TreeMap) es imprimir todos los elementos distintos en una array.

Artículos relacionados

• LinkedHashmap en Java
• Diferencias entre TreeMap, HashMap y LinkedHashMap en Java
• Diferencias entre HashMap y HashTable en Java

Referencias:
https://docs.oracle.com/javase/7/docs/api/java/util/Collection.html

Este artículo es una contribución de Chirag Agrawal . Si le gusta GeeksforGeeks y le gustaría contribuir, también puede escribir un artículo y enviarlo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.

Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.