SortedMap

En esta lección, estudiaremos la interfaz SortedMap. Exploraremos los nuevos métodos que aparecen en esta interfaz, así como las características de una implementación de SortedMap - TreeMap - y las diferencias entre las implementaciones, así como sus ventajas en comparación con HashMap.

Veamos cómo se ve la jerarquía de los mapas. Preste especial atención a la interfaz SortedMap y su implementación TreeMap - son nuestro foco hoy:

La interfaz SortedMap extiende la interfaz Map. En muchos aspectos, es similar a SortedSet (que a su vez extiende Set), ya que ambas describen una funcionalidad similar para almacenar y utilizar valores ordenados.

SortedSet trabaja con y almacena objetos <TValue>, pero SortedMap almacena pares <TKey, TValue>. Es un mapa que almacena todos sus elementos en orden ascendente de sus claves.

La interfaz SortedMap extiende Map. Agrega los siguientes métodos:

MétodoDescripción
TKey firstKey() Devuelve la clave del primer elemento del mapa
TKey lastKey() Devuelve la clave del último elemento del mapa
SortedMap<TKey, TValue> headMap(TKey end) Devuelve un SortedMap que contiene todos los elementos del SortedMap original hasta e incluyendo el elemento con la clave end
SortedMap<TKey, Tvalue> tailMap(K start) Devuelve un SortedMap que contiene todos los elementos del SortedMap original, comenzando en el elemento con la clave start (inclusive)
SortedMap<TKey, TValue> subMap(TKey start, TKey end) Devuelve un SortedMap que contiene todos los elementos del SortedMap original, desde el elemento con la clave start hasta el elemento con la clave end (no incluyendo end)

Clase TreeMap

La clase TreeMap es una implementación de la interfaz SortedMap. Es decir, TreeMap implementa todos los métodos agregados por SortedMap así como los estándar de la interfaz Map.

Puede crear un objeto TreeMap utilizando constructores como estos:

  • TreeMap(): crea un mapa vacío implementado como un árbol;

  • TreeMap(Map<? extends TKey, ? extends TValue> map): crea un árbol y agrega todos los elementos del mapa de entrada;

  • TreeMap(SortedMap<TKey, ? extends TValue> smap): crea un árbol y agrega todos los elementos del mapa ordenado de entrada;

  • TreeMap(Comparator<? super TKey> comparator): crea un árbol vacío; el comparador se utilizará para ordenar todos los elementos que se agreguen posteriormente.

Aquí, TKey es el tipo de las claves en los pares almacenados y TValue es el tipo de los valores en los pares almacenados en el TreeMap.

Comparator es bastante importante para SortedMap/TreeMap. Establece las reglas para ordenar o clasificar nuestro mapa. Si no proporcionamos un comparador, entonces el orden natural de nuestras claves se utilizará cuando creemos un SortedMap.

Agregar elementos a un TreeMap

Los elementos se agregan a un mapa como pares utilizando el método put(). La clave se pasa como primer argumento y el valor como segundo. Por ejemplo, supongamos que queremos crear una lista de estudiantes y sus calificaciones.


SortedMap<String, Integer> map =new TreeMap <String,Integer>();

map.put("Anthony", 5);
map.put("Sara", 5);
map.put("Roxy", 5);
map.put("Jeff", 4);
map.put("Nick", 4);
map.put("Oliver", 3);
map.put("Oliver", 5);

System.out.println(map);

Resultado:

{Nick=4, Jeff=4, Sara=5, Anthony=5, Roxy=5, Oliver=5}

Cuando agregamos un par clave-valor, si la clave ya existe en la colección, entonces el valor antiguo se reemplaza por el nuevo valor. Este comportamiento se ilustra en nuestro ejemplo con dos pares que tienen la misma clave - ("Oliver", 3) y ("Oliver", 5).

Veamos un ejemplo con un Comparator que creamos. Supongamos que queremos almacenar los elementos ordenados por la longitud de la cadena de clave. Si la longitud de las claves es igual, entonces las ordenaremos alfabéticamente (el orden natural de las cadenas):


class LengthComparator implements Comparator<String> {
  public int compare(String o1, String o2) {
    Integer lenghComparedResult = Integer.compare(o1.length(), o2.length());
    return lenghComparedResult != 0 ? lenghComparedResult : o1.compareTo(o2);
  }
}

SortedMap<String, Integer> lengthComparedMap = new TreeMap<String, Integer>(new LengthComparator());

lengthComparedMap.put("Jeff", 4);
lengthComparedMap.put("Oliver", 5);
lengthComparedMap.put("Roxy", 4);
lengthComaredMap.put("Jan", 4);

Aquí está la secuencia resultante:

lengthComparedMap: {Jan=4, Jeff=4, Roxy=4, Oliver=5}

Este comportamiento hace que un TreeMap sea como una matriz o lista ordenada cuyos índices son palabras (String) en lugar de números.

Es importante tener en cuenta que casi cualquier tipo puede ser KeyType o ValueType. Hay algunos requisitos adicionales pequeños para KeyType, y aprenderá sobre ellos cuando estudie las colecciones con mayor detalle.

Métodos SortedMap en la clase TreeMap

  1. Si necesita obtener la clave del primer estudiante, puede usar el método firstKey():

    
    String firstKey = map.firstKey();
    	System.out.println("First key → " + firstKey);
    

    Resultado: Primer clave → Anthony

  2. Si necesitas obtener la clave del último estudiante, puedes usar el método lastKey():

    
    String lastKey = map.lastKey();
    System.out.println("Last key → " + lastKey);
    

    Resultado: Last Key → Jeff

  3. Obtener todos los objetos que vienen después del objeto con la llave "Sara":

    
    Map<String, Integer> tailMap = map.tailMap("Sara");
             	System.out.println("tailMap: " + tailMap);
    

    Resultado: tailMap: {Sara=5, Jeff=4}

  4. Obtener todos los objetos que vienen después del objeto con la llave "Nick":

    
    System.out.println("headMap: " + headMap);
     Map<String, Integer> headMap = map.headMap("Nick");
    

    Resultado: headMap: {Anthony=5}

  5. Obtener todos los objetos que vienen después del objeto con la llave "Oliver" and come before the object with the key "Sara":

    
    Map<String, Integer> subMap = map.subMap("Oliver", "Sara");	
    System.out.println("subMap: " + subMap);
    

    Resultado: subMap: {Oliver=5, Roxy=5}

Comparación de HashMap y SortedMap/TreeMap

Hablemos sobre cómo se ordenan y almacenan los elementos:

  • Dado que HashMap no nos da garantías sobre el orden al iterar, el orden puede cambiar completamente cuando se agregan nuevos elementos.

  • En TreeMap, el orden se basa en el "orden natural" de las claves de acuerdo con su método compareTo() (o un Comparator que proporcionamos). Además, no olvides que TreeMap implementa la interfaz SortedMap, que contiene métodos que dependen de este orden de clasificación.

Ahora pasamos a considerar el rendimiento y la velocidad:

  • HashMap es un mapa basado en la hashing de las claves. Puede insertar y obtener elementos en O(1), tiempo constante. Para admitir esto, las claves deben implementar hashCode() y equals().

  • TreeMap es un mapa basado en árbol. Sus operaciones de inserción y recuperación tardan tiempo logarítmico, es decir, O(log n), lo que depende del número de elementos en el mapa. Esto es necesario para que los elementos tengan algún mecanismo de comparación proporcionado por nuestra clave o un Comparador externo. Este mecanismo determina el orden de iteración.

Y estos factores nos ayudan a decidir qué colecciones usar y cuándo.

Si necesitamos almacenar valores en un cierto orden, la elección es obvia: necesitamos un SortedMap. Aunque es un poco más lento que HashMap, realiza tareas importantes para nosotros.

Como se mencionó anteriormente, SortedMap puede darnos la primera (o última) clave, valor o par clave-valor en nuestro mapa, independientemente de cuándo se agregó ese valor. La implementación de HashMap no puede hacer esto

Por ejemplo, consideremos un mapa con claves (nombres de estudiantes) y valores (sus notas). Digamos que queremos trabajar con una lista en orden alfabético inverso.

1.


SortedMap<String, Integer> sorted = new TreeMap<String,Integer>(Comparator.reverseOrder());
sorted.put("Anthony", 5);
sorted.put("Sara", 5);
sorted.put("Jeff", 4);

String firstKeyFromSortedMapVariant = sorted.firstKey();

Integer markFromSortedMap = sorted.get(firstKeyFromSortedMapVariant);
System.out.println(firstKeyFromSortedMapVariant + " - " + markFromSortedMap);

2.


HashMap<String, Integer> hash = new HashMap<String,Integer>();
hash.put("Anthony", 5);
hash.put("Sara", 5);
hash.put("Jeff", 4);

SortedSet<String> keySetOfHashMap = new TreeSet<String>(Comparator.reverseOrder());
// Or sort manually, storing elements in an array or list (preserving the insertion order)
keySetOfHashMap.addAll(hash.keySet());
String firstKeyFromHashMapVariant = keySetOfHashMap.first();


Integer markFromHashMap = hash.get(firstKeyFromHashMapVariant);
System.out.println(firstKeyFromHashMapVariant + " - " + markFromHashMap);

El ejemplo muestra que el uso de un HashMap hace que la tarea sea más complicada, ya que HashMap no garantiza ni el orden de almacenamiento ni el orden de obtención de elementos del mapa.