Introducción a la colección TreeMap

Un día en la universidad, necesitaba escribir un código para ordenar los apellidos de mis compañeros, que servían como claves para sus datos personales, en orden alfabético ascendente. Dediqué mucho tiempo a esto. Pero si hubiera conocido la clase TreeMap en ese entonces, habría terminado la tarea mucho más rápido.

¿Qué es un TreeMap? Es una estructura de datos similar a un diccionario que almacena elementos como pares clave-valor, ordenándolos por clave.

¿Dónde y cómo se puede utilizar? Bueno, habría sido ideal para la misma tarea con los apellidos de mis compañeros. Si necesito almacenar valores en orden ascendente, en lugar de escribir mi propio algoritmo de ordenamiento, todo lo que tengo que hacer es crear un TreeMap y colocar los valores en él.

Ordena tipos como Integer y String en orden ascendente. Pero si desea colocar su propio tipo personalizado en un TreeMap, entonces su clase debe implementar la interfaz Comparable, de modo que implemente el método compareTo(), el cual indica cómo ordenar las instancias de su clase.

public class Person implements Comparable<Person> {
 
    private String firstName;
    private String lastName;
 
    public Person(String firstName, String lastName) {
        this.firstName = firstName;
        this.lastName = lastName;
    }
 
    public String getFirstName() {
        return firstName;
    }
 
    public void setFirstName(String firstName) {
        this.firstName = firstName;
    }
 
  …
 
    @Override
    public int compareTo(Person person) {
        return person.getFirstName().compareTo(firstName);
    }
 
    @Override
    public String toString() {
        return "Person{" +
                "firstName='" + firstName + '\'' +
                ", lastName='" + lastName + '\'' +
                '}';
    }
}

Vamos a sobrescribir el método compareTo() para que ordene los valores por nombre en orden alfabético inverso:

TreeMap map = new TreeMap<Person, String>();
 
map.put(new Person("AA","BB"), "aa");
map.put(new Person("BB","BB"), "aa");
map.put(new Person("DD","BB"), "aa");
map.put(new Person("CC","BB"), "aa");

Los valores se almacenan en el siguiente orden:

Person{firstName='DD', lastName='BB'}
Person{firstName='CC', lastName='BB'}
Person{firstName='BB', lastName='BB'}
Person{firstName='AA', lastName='BB'}

La clase TreeMap implementa la interfaz NavigableMap, la cual a su vez extiende la interfaz SortedMap. Esto permite que la clase TreeMap utilice árboles para almacenar valores en orden.

En términos simples, un árbol rojo-negro es una estructura de datos que almacena valores en el subárbol derecho si son mayores que la raíz y en el subárbol izquierdo si son menores. Esta implementación puede buscar valores en la estructura muy rápidamente.

Un árbol rojo-negro es autoequilibrado, por lo que cambia su estructura a medida que se inserta cada nuevo valor. El valor agregado primero se considera inicialmente la raíz, pero otro valor puede convertirse en la raíz durante el proceso de equilibrio.

Bien, ahora sabes qué es un TreeMap y cómo funciona.

Recuerda que TreeMap solo puede almacenar objetos cuya clase implemente la interfaz Comparable y anule el método compareTo().

Pero, ¿qué pasa si estamos usando clases de terceros cargadas desde varias bibliotecas y no podemos implementar Comparable en ellas? Hay una solución para esto: escribir tu propio Comparator.

Comparator es una interfaz que tiene un método compare(). Podemos usarlo para comparar objetos y almacenarlos en un TreeMap.

Comparator<Person> comparator = new Comparator<Person>() {
 
    @Override
    public int compare(Person person1, Person person2) {
        return person1.getFirstName().compareTo(person2.getFirstName());
    }
};
 
 
TreeMap map = new TreeMap<Person, String>(comparator);

En este ejemplo, creamos un Comparator personalizado y lo pasamos a un TreeMap.

A partir de Java 8, podemos escribir esto utilizando una expresión lambda:

TreeMap map = new TreeMap<Person, String>((Person person1, Person person2) -> person1.getFirstName().compareTo(person2.getFirstName()));

En otras palabras, para almacenar valores en un TreeMap, necesitas especificar cómo ordenarlos. Hay dos formas de hacerlo: implementar Comparable o implementar tu propio Comparator.

Pero, ¿qué sucede si necesitamos poner null en un TreeMap como clave? HashMap te permite hacer esto. Sí, pero, ¿cómo maneja esto TreeMap?

TreeMap map = new TreeMap<Person, String>();
map.put (null, "Person");

Ejecutar este código nos da un error:

El problema es que internamente la clase TreeMap compara valores utilizando el método compareTo(). Ciertamente puede pasar un valor null y el código compilará. Pero en tiempo de ejecución se producirá un error, ya que se llamará al método en un valor null, lo que provocará la generación de una NullPointerException.

Comparación de HashMap y TreeMap

A diferencia de TreeMap, HashMap permite almacenar null como clave. La estructura tiene un lugar específico para todas las claves null. HashMap puede almacenar claves null porque determina dónde deben ir en función de su valor hash, y el cálculo del valor hash no requiere comparaciones. Así que todas las claves null tienen su lugar.

Ahora ya sabes qué usar cuando necesitas almacenar valores en orden clasificado y cómo establecer las reglas para clasificar.