SortedMap

SortedMap

Nesta lição, estudaremos a interface SortedMap . Exploraremos novos métodos que aparecem nessa interface, bem como os recursos de uma implementação do SortedMap — TreeMap — e as diferenças entre as implementações, bem como suas vantagens em relação ao HashMap .

Vamos ver como é a hierarquia dos mapas. Preste atenção especial à interface SortedMap e sua implementação TreeMap — eles são nosso foco hoje:

A interface SortedMap estende a interface Map . De muitas maneiras, é semelhante a SortedSet (que por sua vez estende Set ), pois ambos descrevem funcionalidade semelhante para armazenar e usar valores classificados.

SortedSet funciona com e armazena<TValue>, mas SortedMap armazenapares<TKey, TValue>É um mapa que armazena todos os seus elementos em ordem crescente de suas chaves.

A interface SortedMap estende Map . Ele adiciona os seguintes métodos:

Classe TreeMap

A classe TreeMap é uma implementação da interface SortedMap . Ou seja, TreeMap implementa todos os métodos adicionados por SortedMap , bem como os padrões da interface Map .

Você pode criar um objeto TreeMap usando construtores como estes:

• TreeMap() : cria um mapa vazio implementado como uma árvore;

• TreeMap(Map<? extends TKey, ? extends TValue> map) : cria uma árvore e adiciona todos os elementos do mapa de entrada;

• TreeMap(SortedMap<TKey, ? extends TValue> smap) : cria uma árvore e adiciona todos os elementos do mapa classificado de entrada;

• TreeMap(Comparator<? super TKey> comparador) : cria uma árvore vazia — o comparador será usado para classificar todos os elementos à medida que são adicionados posteriormente.

Aqui TKey é o tipo das chaves nos pares armazenados e TValue é o tipo dos valores nos pares armazenados no TreeMap .

Comparator é muito importante para SortedMap / TreeMap . Ele estabelece as regras para classificar — ou ordenar — nosso mapa. Se não fornecermos um comparador, a ordem natural de nossas chaves será usada quando criarmos um SortedMap .

Adicionando elementos a um TreeMap

Os elementos são adicionados a um mapa como pares usando o método put() . A chave é passada como o primeiro argumento e o valor é passado como o segundo. Por exemplo, suponha que queremos criar uma lista de alunos e suas notas.

SortedMap<String, Integer> map =new TreeMap <String,Integer>();

map.put("Anthony", 5);
map.put("Sara", 5);
map.put("Roxy", 5);
map.put("Jeff", 4);
map.put("Nick", 4);
map.put("Oliver", 3);
map.put("Oliver", 5);

System.out.println(map);

Resultado:

Quando adicionamos um par chave-valor, se a chave já existir na coleção, o valor antigo é substituído pelo novo valor. Esse comportamento é ilustrado em nosso exemplo com dois pares que possuem a mesma chave — ("Oliver", 3) e ("Oliver", 5) .

Vejamos um exemplo com um Comparator que criamos. Suponha que queremos armazenar os elementos classificados pelo comprimento da string de chave. Se o comprimento das chaves for igual, classificaremos alfabeticamente (a ordem natural das strings):

class LengthComparator implements Comparator<String> {
  public int compare(String o1, String o2) {
    Integer lenghComparedResult = Integer.compare(o1.length(), o2.length());
    return lenghComparedResult != 0 ? lenghComparedResult : o1.compareTo(o2);
  }
}

SortedMap<String, Integer> lengthComparedMap = new TreeMap<String, Integer>(new LengthComparator());

lengthComparedMap.put("Jeff", 4);
lengthComparedMap.put("Oliver", 5);
lengthComparedMap.put("Roxy", 4);
lengthComaredMap.put("Jan", 4);

Aqui está a sequência resultante:

Esse comportamento torna um TreeMap como uma matriz ou lista classificada cujos índices são palavras ( String ) em vez de números.

Métodos SortedMap na classe TreeMap

1. Se você precisa obter a chave do primeiro aluno, pode usar o método firstKey() :

   
   String firstKey = map.firstKey();
   	System.out.println("First key → " + firstKey);
   

   Resultado: Primeira chave → Anthony

2. Se você precisa obter a chave do último aluno, pode usar o método lastKey() :

   
   String lastKey = map.lastKey();
   System.out.println("Last key → " + lastKey);
   

   Resultado: Última Chave → Jeff

3. Obtenha todos os objetos que vêm depois do objeto com a chave " Sara ":

   
   Map<String, Integer> tailMap = map.tailMap("Sara");
            	System.out.println("tailMap: " + tailMap);
   

   Resultado: tailMap: {Sara=5, Jeff=4}

4. Obtenha todos os objetos que vêm antes do objeto com a chave " Nick ":

   
   System.out.println("headMap: " + headMap);
    Map<String, Integer> headMap = map.headMap("Nick");
   

   Resultado: headMap: {Anthony=5}

5. Obtenha todos os objetos que vêm depois do objeto com a chave " Oliver " e vêm antes do objeto com a chave " Sara ":

   
   Map<String, Integer> subMap = map.subMap("Oliver", "Sara");	
   System.out.println("subMap: " + subMap);
   

   Resultado: subMapa: {Oliver=5, Roxy=5}

Comparação entre HashMap e SortedMap/TreeMap

Vamos falar sobre como os elementos são ordenados e armazenados:

• Como o HashMap não nos dá nenhuma garantia sobre a ordem durante a iteração, a ordem pode mudar completamente quando novos elementos são adicionados.

• Em TreeMap , a ordem é baseada na "ordem natural" das chaves de acordo com seu método compareTo() (ou um Comparator que fornecemos). Além disso, não esqueça que TreeMap implementa a interface SortedMap , que contém métodos que dependem dessa ordem de classificação.

Agora nos voltamos para uma consideração de desempenho e velocidade:

• HashMap é um mapa baseado em chaves de hash. Pode inserir e obter elementos emO(1), tempo constante. Para suportar isso, as chaves devem implementarhashCode()eequals().

• TreeMap é um mapa baseado em árvore. Suas operações de inserção e busca levam tempo logarítmico, ou seja,O(log n), que depende do número de elementos no mapa. Isso é necessário para que os elementos tenham algum tipo de mecanismo de comparação fornecido por nossa chave ou por um Comparator externo. Este mecanismo determina a ordem de iteração.

E esses fatores nos ajudam a decidir quais coleções usar e quando.

Se precisarmos armazenar valores em uma determinada ordem, a escolha é óbvia — precisamos de um SortedMap . Embora seja um pouco mais lento que o HashMap , ele executa tarefas importantes para nós.

Conforme mencionado anteriormente, SortedMap pode nos fornecer a primeira (ou última) chave, ou valor, ou par chave-valor em nosso mapa, independentemente de quando esse valor foi adicionado. A implementação do HashMap não pode fazer isso.

Por exemplo, considere um mapa com chaves (nomes dos alunos) e valores (suas notas). Digamos que queremos trabalhar com uma lista em ordem alfabética inversa.

1.

SortedMap<String, Integer> sorted = new TreeMap<String,Integer>(Comparator.reverseOrder());
sorted.put("Anthony", 5);
sorted.put("Sara", 5);
sorted.put("Jeff", 4);

String firstKeyFromSortedMapVariant = sorted.firstKey();

Integer markFromSortedMap = sorted.get(firstKeyFromSortedMapVariant);
System.out.println(firstKeyFromSortedMapVariant + " - " + markFromSortedMap);

2.

HashMap<String, Integer> hash = new HashMap<String,Integer>();
hash.put("Anthony", 5);
hash.put("Sara", 5);
hash.put("Jeff", 4);

SortedSet<String> keySetOfHashMap = new TreeSet<String>(Comparator.reverseOrder());
// Or sort manually, storing elements in an array or list (preserving the insertion order)
keySetOfHashMap.addAll(hash.keySet());
String firstKeyFromHashMapVariant = keySetOfHashMap.first();


Integer markFromHashMap = hash.get(firstKeyFromHashMapVariant);
System.out.println(firstKeyFromHashMapVariant + " - " + markFromHashMap);

O exemplo mostra que usar um HashMap torna a tarefa mais complicada, pois o HashMap não garante nem a ordem de armazenamento nem a ordem de obtenção dos elementos do mapa.