TreeMap em Java

Se você está lendo este artigo, provavelmente está familiarizado com a interface do mapa e onde pode ser aplicado adequadamente. Se não, então venha aqui . Hoje falaremos sobre as características da implementação do Java TreeMap e, mais especificamente, como ele difere do HashMap e como usá-lo corretamente.

Comparando TreeMap, HashMap e LinkedHashMap

A implementação mais usada da interface Map é HashMap. É fácil de usar e garante acesso rápido aos dados, por isso é o melhor candidato para resolver a maioria dos problemas. A maioria, mas não todos. Às vezes, você precisa armazenar dados de maneira estruturada e poder navegar por eles. Nesse caso, outra implementação da interface Map (TreeMap) vem em socorro. TreeMap implementa a interface NavigableMap , que herda SortedMap , que por sua vez herda a interface Map. Ao implementar as interfaces NavigableMap e SortedMap , o TreeMap recebe funcionalidade adicional que não está disponível no HashMap, mas paga um preço em termos de desempenho. Há também o LinkedHashMapclass , que também permite armazenar dados em uma ordem específica (a ordem em que você os adiciona ao mapa). Para entender as diferenças entre essas três classes, observe esta tabela: Como você pode ver, essas classes têm muito em comum, mas também existem várias diferenças. Embora a classe TreeMap seja a mais versátil, ela nem sempre pode armazenar null como uma chave. Além disso, acessar os elementos de um TreeMap leva mais tempo. Portanto, se você não precisa armazenar dados em alguma ordem de classificação, é melhor usar HashMap ou LinkedHashMap .

árvore rubro-negra

Você provavelmente notou que, sob o capô, o TreeMap usa uma estrutura de dados chamada árvore rubro-negra. Armazenar dados nessa estrutura é precisamente o que fornece ordenação de dados. Então, que tipo de árvore é essa? Vamos descobrir! Imagine que você precise armazenar pares Number-String. Os números 16, 20, 52, 55, 61, 65, 71, 76, 81, 85, 90, 93 e 101 serão chaves. Se você armazenar dados em uma lista tradicional e precisar encontrar o elemento com a chave 101, precisará percorrer todos os 13 elementos para encontrá-lo. Para 13 elementos, isso não é grande coisa, mas ao trabalhar com um milhão, teremos grandes problemas. Para resolver esses problemas, os programadores usam estruturas de dados um pouco mais complexas. É aqui que a árvore rubro-negra entra em cena!A busca por um elemento começa na raiz da árvore, que no nosso caso é 61. Então comparamos os valores dos nós com o valor que estamos procurando. Se nosso valor for menor, vamos para a esquerda; se for maior, então vamos para a direita. Esse processo se repete até encontrarmos o valor desejado ou encontrarmos um elemento cujo valor seja nulo (uma folha da árvore). As cores vermelho e preto são usadas para simplificar a navegação e equilibrar a árvore. Existem regras que devem ser sempre observadas na construção de uma árvore rubro-negra:

• A raiz deve ser preta.
• As folhas da árvore devem ser pretas.
• Um nó vermelho deve ter dois nós filhos pretos.
• Um nó preto pode ter nós filhos de qualquer cor.
• Um caminho de um nó até suas folhas deve conter o mesmo número de nós pretos.
• Novos nós são adicionados às folhas.

Se você considerar as Regras 3, 4 e 5 juntas, poderá entender como a cor dos nós nos permite navegar na árvore mais rapidamente: um caminho pelos nós pretos é sempre mais curto do que um pelos nós vermelhos. Assim, o tamanho total da árvore é determinado pelo número de nós pretos, que é chamado de "altura preta". A estrutura de dados da árvore rubro-negra é implementada em várias linguagens de programação. Existem muitas implementações Java na Internet, então não vamos nos demorar aqui. Em vez disso, vamos continuar conhecendo a funcionalidade do TreeMap.

Métodos que vêm das interfaces SortedMap e NavigableMap

Assim como o HashMap, o TreeMap implementa a interface Map, o que significa que o TreeMap possui todos os métodos existentes no HashMap. Mas o TreeMap também implementa as interfaces SortedMap e NavigableMap e, portanto, obtém funcionalidades adicionais delas. SortedMap é uma interface que estende Map e adiciona métodos relevantes a um conjunto de dados classificado:

• firstKey() : retorna a chave do primeiro elemento no mapa
• lastKey() : retorna a chave do último elemento
• headMap(K end) : retorna um mapa que contém todos os elementos do mapa atual, desde o início até o elemento com a chave end
• tailMap(K start) : retorna um mapa que contém todos os elementos do mapa atual, do elemento inicial ao final
• subMap(K start, K ​​end) : retorna um mapa que contém todos os elementos do mapa atual, desde o elemento inicial até o elemento com a chave final.

NavigableMap é uma interface que estende SortedMap e adiciona métodos para navegar entre os elementos de um mapa:

• firstEntry() : retorna o primeiro par chave-valor
• lastEntry() : retorna o último par chave-valor
• pollFirstEntry() : retorna e exclui o primeiro par
• pollLastEntry() : retorna e exclui o último par
• tetoKey(K obj) : retorna a menor chave k que é maior ou igual à chave obj. Se não houver tal chave, retorna null
• floorKey(K obj) : retorna a maior chave k que é menor ou igual à chave obj. Se não houver tal chave, retorna null
• lowerKey(K obj) : retorna a maior chave k que é menor que a chave obj. Se não houver tal chave, retorna null
• upperKey(K obj) : retorna a menor chave k que é maior que a chave obj. Se não houver tal chave, retorna null
• tetoEntry(K obj) : semelhante ao método tetoKey(K obj), retorna apenas um par chave-valor (ou nulo)
• floorEntry(K obj) : semelhante ao método floorKey(K obj), retorna apenas um par chave-valor (ou null)
• lowerEntry(K obj) : semelhante ao método lowerKey(K obj), retorna apenas um par chave-valor (ou nulo)
• upperEntry(K obj) : semelhante ao método upperKey(K obj), retorna apenas um par chave-valor (ou nulo)
• descendingKeySet() : retorna um NavigableSet contendo todas as chaves classificadas em ordem inversa
• descendingMap() : retorna um NavigableMap contendo todos os pares classificados em ordem inversa
• navigableKeySet() : retorna um objeto NavigableSet contendo todas as chaves na ordem em que estão armazenadas
• headMap(K upperBound, boolean incl) : retorna um mapa que contém pares desde o início até o elemento upperBound. O parâmetro incl indica se o elemento upperBound deve ser incluído no mapa retornado
• tailMap(K lowerBound, boolean incl) : funcionalidade semelhante ao método anterior, retorna apenas pares de lowerBound até o final
• subMap(K lowerBound, boolean lowIncl, K upperBound, boolean highIncl) : como nos métodos anteriores, retorna pares de lowerBound para upperBound; os argumentos lowIncl e highIncl indicam se os elementos de limite devem ser incluídos no novo mapa.

Além dos construtores usuais, o TreeMap possui outro construtor que aceita uma instância de um comparador. Este comparador é responsável pela ordem em que os elementos são armazenados.

Exemplos de TreeMap

Essa abundância de métodos extras pode parecer desnecessária, mas eles acabam sendo muito mais úteis do que você imagina à primeira vista. Vamos explorar o seguinte exemplo juntos. Imagine que trabalhamos no departamento de marketing de uma grande empresa e temos um banco de dados de pessoas para as quais queremos exibir anúncios. Há dois detalhes a ter em conta:

• Precisamos acompanhar o número de impressões para cada pessoa
• O algoritmo para exibir anúncios para menores é diferente.

Vamos criar uma classe Person , que armazenará todas as informações relevantes sobre cada pessoa:

public class Person {
   public String firstName;
   public String lastName;
   public int age;

   public Person(String firstName, String lastName, int age) {
       this.firstName = firstName;
       this.lastName = lastName;
       this.age = age;
   }
}

Implementamos a lógica na classe Main :

import java.util.Comparator;
import java.util.Map;
import java.util.TreeMap;

public class Main {
   public static void main(String[] args) {
      TreeMap<Person, Integer> map = new TreeMap<>(Comparator.comparingInt(o -> o.age));
      map.put(new Person("John", "Smith", 17), 0);
      map.put(new Person("Ivan", "Petrenko", 65), 0);
      map.put(new Person("Pedro", "Escobar", 32), 0);
      map.put(new Person("Shirley", "Hatfield", 14), 0);
      map.put(new Person("Abby", "Parsons", 19), 0);

      Person firstAdultPerson = map.navigableKeySet().stream().filter(person -> person.age>18).findFirst().get();

       Map<Person, Integer> youngPeopleMap = map.headMap(firstAdultPerson, false);
       Map<Person, Integer> adultPeopleMap = map.tailMap(firstAdultPerson, true);
       showAdvertisementToYoung(youngPeopleMap);
       showAdvertisementToAdult(adultPeopleMap);
   }

   public static void showAdvertisementToYoung(Map map) {}
   public static void showAdvertisementToAdult(Map map) {}
}

Na classe Main, crie um TreeMap, no qual cada chave representa uma pessoa específica e cada valor é o número de impressões de anúncios neste mês. Passamos ao construtor um comparador que classifica as pessoas por idade. Preenchemos o mapa com valores arbitrários. Agora queremos obter uma referência ao primeiro adulto em nosso pequeno repositório de dados. Fazemos isso usando a API Stream. Em seguida, obtemos dois mapas separados, que passamos para os métodos que exibem anúncios. Há muitas, muitas maneiras pelas quais poderíamos ter realizado essa tarefa. O arsenal de métodos da classe TreeMap nos permite criar soluções personalizadas para cada necessidade. Você não precisa se lembrar de todos, pois sempre pode usar a documentação ou as dicas do seu IDE. Para reforçar o que você aprendeu, sugerimos que você assista a uma vídeo aula do nosso Curso de Java É tudo por agora! Espero que a classe TreeMap esteja clara para você agora e que você a aplique adequadamente na resolução de tarefas práticas de codificação.