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.
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 .
É 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.
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:HashMap | LinkedHashMap | TreeMap | |
---|---|---|---|
Ordenação de dados | Aleatório. Não há garantia de que o pedido será mantido ao longo do tempo. | Na ordem em que os dados são adicionados | Em ordem crescente ou com base em um comparador especificado |
Complexidade de tempo | O(1) | O(1) | O(log(n)) |
Interfaces implementadas | Mapa | Mapa | NavigableMap SortedMap Mapa |
Estrutura de dados | baldes | baldes | árvore rubro-negra |
Suporte para chave nula? | Sim | Sim | Sim, se você usar um comparador, isso permite null |
Discussão segura? | Não | Não | Não |
á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.
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.
- 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.
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.
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