Introdução à coleção TreeMap

Um dia, na universidade, precisei escrever um código para classificar os sobrenomes de meus colegas de classe, que serviam como chaves para seus dados pessoais, em ordem crescente. Passei muito tempo nisso. Mas se eu soubesse da classe TreeMap naquela época, teria concluído a tarefa muito mais rapidamente.

O que é um TreeMap ? É uma estrutura de dados semelhante a um dicionário que armazena elementos como pares chave-valor, classificando-os por chave.

Onde e como pode ser usado? Bem, teria sido ideal para a mesma tarefa com os sobrenomes dos meus colegas. Se eu precisar armazenar valores em ordem crescente, em vez de escrever meu próprio algoritmo de classificação, basta criar um TreeMap e colocar os valores nele.

Ele classifica tipos como Integer e String em ordem crescente. Mas se você quiser colocar seu próprio tipo personalizado em um TreeMap , sua classe precisará implementar a interface Comparable , para que ela implemente o método compareTo() , que indica como classificar instâncias de sua classe.

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 substituir o método compareTo() para que ele classifique os valores pelo primeiro nome em ordem alfabética inversa:

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

Os valores serão armazenados na seguinte ordem:

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

A classe TreeMap implementa a interface NavigableMap , que por sua vez estende a interface SortedMap . Isso permite que a classe TreeMap use árvores para armazenar valores em ordem de classificação.

Para simplificar, uma árvore rubro-negra é uma estrutura de dados que armazena valores na subárvore direita se forem maiores que a raiz e na subárvore esquerda se forem menores. Essa implementação pode procurar valores na estrutura muito rapidamente.

Uma árvore rubro-negra é auto-balanceada, portanto muda sua estrutura a cada novo valor inserido. O valor adicionado primeiro é inicialmente considerado a raiz, mas outro valor pode se tornar a raiz durante o processo de balanceamento.

Bem, agora você sabe o que é o TreeMap e como ele funciona.

Lembre-se de que TreeMap só pode armazenar objetos cuja classe implementa a interface Comparable e substitui o método compareTo() .

Mas e se estivermos usando classes de terceiros carregadas de várias bibliotecas e não pudermos implementar Comparable nelas? Existe uma solução para isso: escreva seu próprio Comparator .

Comparator é uma interface que possui um método compare(). Podemos usá-lo para comparar objetos e armazená-los em um 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);

Neste exemplo, criamos um Comparator personalizado e passamos um TreeMap para a classe.

A partir do Java 8, podemos escrever isso usando uma expressão lambda:

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

Em outras palavras, para armazenar valores em um TreeMap , você precisa especificar como classificá-los. Há duas maneiras de fazer isso: implementar Comparable ou implementar seu próprio Comparator .

Mas e se precisarmos colocar null em um TreeMap como uma chave? HashMap permite que você faça isso. Sim, mas como o TreeMap lida com isso?

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

Executar este código nos dá um erro:

O problema é que internamente a classe TreeMap compara valores usando o método compareTo() . Você certamente pode passar um valor nulo e o código será compilado. Mas em tempo de execução você receberá um erro, porque o método será chamado em um valor nulo , fazendo com que um NullPointerException seja lançado.

Comparação entre HashMap e TreeMap

Ao contrário do TreeMap , o HashMap permite armazenar null como uma chave. A estrutura possui um local específico para todas as chaves nulas . O HashMap é capaz de armazenar chaves nulas porque determina para onde elas vão com base em seu valor de hash, e o cálculo do valor de hash não requer comparações. Portanto, todas as chaves nulas têm seu lugar.

Aí está — agora você sabe o que usar quando precisar armazenar valores em ordem de classificação e como definir as regras de classificação.