Recursos do TreeMap em Java

Se você está lendo este artigo, é provável que esteja familiarizado com a interface do Mapa e seus usos. Se não, então aqui está. Hoje falaremos sobre os recursos de implementação do TreeMap e, mais especificamente, como ele difere do HashMap e como usá-lo corretamente.

Comparação de TreeMap, HashMap e LinkedHashMap

A implementação mais comumente usada da interface Map é HashMap . É fácil de usar e garante acesso rápido aos dados, tornando-o o melhor candidato para a maioria das tarefas. A maioria, mas não todos. Às vezes é necessário armazenar dados de forma estruturada com capacidade de navegação por eles. Nesse caso, outra implementação da interface Map vem em socorro - TreeMap . TreeMap implementa a interface NavigableMap , que herda de SortedMap , que por sua vez herda da interface Map . Ao implementar as interfaces NavigableMap e SortedMap , o TreeMap ganha funcionalidades adicionais que o HashMap não possui , mas isso tem um preço em termos de desempenho. Há também uma classe LinkedHashMap que também permite armazenar dados em uma determinada ordem - na ordem em que foram adicionados. Para ajudá-lo a 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 algumas diferenças. Embora a classe TreeMapseja a mais multifuncional, nem sempre ela pode ser armazenada nullcomo uma chave. Além disso, o tempo de acesso aos elementos do TreeMap será o mais longo. Portanto, se você não precisa armazenar dados de forma ordenada, é melhor usar HashMapou LinkedHashMap.

Árvore de ébano vermelho

Como você provavelmente notou, nos bastidores TreeMapele usa uma estrutura de dados chamada árvore vermelha e preta. É o armazenamento dos dados nesta estrutura que garante a ordem em que os dados são armazenados. O que é esta árvore? Vamos descobrir! Imagine que você precisa armazenar pares Number-String. Os números 16, 20, 52, 55, 61, 65, 71, 76, 81, 85, 90, 93, 101 serão as chaves. Se você armazena dados em uma lista tradicional e precisa encontrar um elemento com a chave 101, você precisará percorrer todos os 13 elementos para encontrá-lo. Para 13 elementos isso não é crítico; ao trabalhar com um milhão teremos grandes problemas. Para resolver esses problemas, os programadores usam estruturas de dados um pouco mais complexas. Portanto, conheça a árvore rubro-negra!

https://algorithmtutor.com/Data-Structures/Tree/Red-Black-Trees/

A busca pelo elemento requerido começa na raiz da árvore, no nosso caso é 61. A seguir é feita uma comparação com o valor requerido. Se o nosso valor for menor, vamos para a esquerda, se for maior, vamos para a direita. Isso acontece até encontrarmos o valor desejado ou atingirmos um elemento com valor null(uma folha de uma árvore). As cores vermelha e preta são usadas para facilitar a navegação e o equilíbrio da árvore. Existem regras que sempre devem ser seguidas 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 qualquer nó filho.
• O caminho de um nó até suas folhas deve conter o mesmo número de nós pretos.
• Novos nós são adicionados no lugar das folhas.

Se você observar as regras 3, 4 e 5 juntas, poderá entender como colorir os nós acelera a navegação pela árvore: o caminho pelos nós pretos é sempre mais curto do que pelos vermelhos. Portanto, o tamanho total da árvore é determinado pelo número de nós pretos, e esse tamanho é chamado de “altura preta”. A árvore rubro-negra é implementada em diferentes linguagens de programação. Existem muitas implementações para Java na Internet, então não vamos nos alongar muito sobre isso, mas continuaremos a nos familiarizar com a funcionalidade TreeMap.

Métodos derivados das interfaces SortedMap e NavigableMap

Da mesma forma HashMap, TreeMapele implementa a interface Map, o que significa que TreeMappossui todos os métodos que HashMap. Mas, além disso, TreeMapimplementa interfaces SortedMape NavigableMap, obtendo delas funcionalidades adicionais. SortedMap— uma interface que estende Mape adiciona métodos relevantes a um conjunto de dados ordenado:

• firstKey(): retorna a chave do primeiro elemento do mapa;
• lastKey(): retorna a chave do último elemento;
• headMap(K end): retorna um mapa que contém todos os elementos do 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 atual, começando pelo elemento starte terminando no final;
• subMap(K start, K end): retorna um mapa que contém todos os elementos do atual, começando com o elemento starte terminando com o elemento com a chave end.

NavigableMap— uma interface que estende SortedMape adiciona métodos para navegar entre os elementos do mapa:

• firstEntry(): retorna o primeiro par de valores-chave;
• lastEntry(): retorna o último par de valores-chave;
• pollFirstEntry(): retorna e remove o primeiro par;
• pollLastEntry(): retorna e remove o último par;
• ceilingKey(K obj): Retorna a menor chave k que é maior ou igual à chave obj. Se não existir tal chave, retorna nulo;
• floorKey(K obj): Retorna a maior chave k que é menor ou igual à chave obj. Se não existir tal chave, retorna nulo;
• lowerKey(K obj): Retorna a maior chave k que é menor que a chave obj. Se não existir tal chave, retorna nulo;
• higherKey(K obj): Retorna a menor chave k que é maior que a chave obj. Se não existir tal chave, retorna nulo;
• ceilingEntry(K obj): semelhante ao método tetoKey(K obj), mas retorna um par chave-valor (ou nulo);
• floorEntry(K obj): semelhante ao método floorKey(K obj), mas retorna um par chave-valor (ou nulo);
• lowerEntry(K obj): semelhante ao método lowerKey(K obj), mas retorna um par chave-valor (ou nulo);
• higherEntry(K obj): semelhante ao método lowerKey(K obj), mas retorna 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 em ordem de armazenamento;
• headMap(K upperBound, boolean incl): retorna um mapa que contém pares desde o início até o elemento UpperBound. O argumento incl especifica se o elemento UpperBound deve ser incluído no mapa retornado;
• tailMap(K lowerBound, boolean incl): a funcionalidade é semelhante ao método anterior, apenas os pares do lowerBound ao final são retornados;
• subMap(K lowerBound, boolean lowIncl, K upperBound, boolean highIncl): como nos métodos anteriores, os pares de lowerBound para UpperBound são retornados, os argumentos lowIncl e highIncl especificam se os elementos de limite devem ser incluídos no novo mapa.

Na própria implementação TreeMap, além dos construtores que conhecemos, é adicionado mais um, que aceita uma instância do comparador. Este comparador será responsável pela ordem em que os elementos são armazenados.

Exemplos de uso do TreeMap

Essa abundância de métodos adicionais pode parecer desnecessária, mas muitas vezes eles acabam sendo muito mais úteis do que pareciam inicialmente. Vejamos este exemplo com você. Imagine que trabalhamos no departamento de marketing de uma grande empresa e temos um banco de dados de pessoas para quem queremos mostrar publicidade. Existem duas nuances nisso:

• precisamos acompanhar o número de impressões de cada pessoa;
• O algoritmo para exibição de publicidade para menores é diferente.

Vamos criar uma classe Personque armazenará todas as informações disponíveis sobre uma 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("Radion", "Pyatkin", 14), 0);
      map.put(new Person("Sergey", "Vashkevich", 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 Mainque criamos TreeMap, onde keyestá uma pessoa específica e valueé o número de impressões de anúncios neste mês. No construtor passamos um comparador que irá classificar as pessoas por idade. Preencha com mapvalores aleatórios. Agora precisamos obter uma referência ao primeiro adulto em nosso mini armazenamento de dados. Fazemos isso usando a API Stream. Depois disso, obtemos dois mapas independentes, que passamos aos métodos de exibição de publicidade. Existem muitas, muitas maneiras pelas quais esse problema poderia ser resolvido. O arsenal de métodos da aula TreeMappermite inventar soluções para todos os gostos. Não é necessário lembrar de todos eles, pois você sempre pode utilizar a documentação ou dicas do ambiente de desenvolvimento. Isso é tudo! Espero que a aula agora esteja TreeMapclara para você e que você encontre uma aplicação precisa para ela na resolução de problemas práticos.