Java 101

Collections!?!? Listas, conjuntos e mapas... as classes mais usadas do Java!

Collections!?!? Listas, conjuntos e mapas... as classes mais usadas do Java!


Java 101
(série de 6 partes)

Como começar a aprender Java
A sintaxe do Java
Collections!?!? Listas, conjuntos e mapas... as classes mais usadas do Java!
OO: Eu vejo objetos por todos os cantos!
Java I/O
Concorrência e Paralelismo

No post anterior nós falamos sobre o que é a JVM e sobre como criar seu primeiro projeto Java. Se você não leu e não sabe escrever um código Java, volta aí no post anterior e veja.

Agora vamos dar um segundo passo, pois para quem está começando a entender Java uma das dificuldades é conhecer a extensa biblioteca que a JVM provê. Essa biblioteca trás para nos dá a capacidade de não reescrever códigos básicos para qualquer software, por isso não conhecer é um risco, pois podemos precisar reescrever código que já estão a nossa disposição. Precisamos também compreender alguns conceitos para usar bem os recursos a nossa disposição, vou dar um exemplo fora do contexto desse post, ninguém precisa implementa uma conexão socket, basta usar a classe java.net.Socket.

Na figura abaixo, temos a lista de todos os módulos da versão 17 do Java (uma versão é chamada de JDK, Java Development Kit). É essencial conhecermos o módulo java.base, já os demais módulos podem ser necessários para funcionalidades específica.

jdk libs
Figura 1. Módulos do JDK 17

— Tem muita biblioteca aí! Pode onde devo começar?

Eu recomendaria pelo que conhecemos como Collections. Ela não é especificamente um pacote, mas uma interface, a Collection, e uma série de classes que a usam. A Collections é praticamente onipresente em todo código Java.

Quando ouvimos falar das Java Collections, podemos assumir que estamos falando de classes da biblioteca padrão do Java que estendem a interface Collection, essa interface por sua vez irá implementar uma serie de métodos que são comuns em todas as classes que implementam ela. Mas ter métodos em comum não implica em comportamento similar. Para entender o comportamento, precisamo olhar para interfaces que estendem a interface Collection, as principais são List e Set.

Mas a biblioteca Collections não está restrita a interface Collection, outras interfaces podem ser incluídas como a Map e a Stream.

Vamos olhar como usar cada uma dessas interfaces e classes? No diagrama abaixo estão listadas as classes mais importantes, exceto a Stream da qual discutiremos no final.

Collections
Figura 2. Pacote Java Collections

Listas, Conjuntos e Mapas

Listas, Conjuntos e Mapas são os conceitos básicos da biblioteca Collections. Esses conceitos podem ser abstratos a primeira vista, mas a diferença é percebida quando perguntamos o que indexa cada um deles.

Se você não entendeu o significado de indexar (indexação), podemos assumir que estou falando da forma como os elementos são agrupados. Vamos pensar uma lista (List), nela os elementos são agrupados de forma sequencial, ou seja, indexados pela posição. Mas quando temos um conjuntos (Set), eles estão agrupados pela identidade própria deles, ou seja, elementos iguais não devem ser repetidos, sendo contado apenas uma vez. Já nos Mapas (Map), os elementos são indexados por uma chave externa a própria natureza do elemento, nesse caso podemos afirmar que temos um par de chave/valor. É por isso que List e Set estendem a interface Collection enquanto Map não estende, porque essa classe não é apenas uma coleção, mas uma indexação composta por dois valores.

indexação
Figura 3. Significado de indexação

— Cara, você falou um monte aí, mas eu não entendi nada!

OK! Então vamos demonstrar isso por código? No pequeno trecho abaixo estou inicializando uma lista, um conjunto e um mapa e usando eles para adicionar alguns valores. Você pode ser por exemplo Strings, tente executar o código abaixo usando a ferramenta jshell (ferramenta REPL excelente adicionada na JDK 9), preste bem atenção no trecho de código a esquerda e no resultado a direta ($x representa o resultado retornado pela operação).

import java.util.ArrayList;
import java.util.HashSet;
import java.util.HashMap;

var lista = new ArrayList<String>();       // lista ==> []
lista.add("Valor 1");                      // $5 ==> true
lista.add("Valor 2");                      // $6 ==> true
lista.add("Valor 1");                      // $7 ==> true
lista.size() == 3                          // $8 ==> true
lista;                                     // lista ==> [Valor 1, Valor 2, Valor 1]

var conjunto = new HashSet<String>();      // conjunto ==> []
conjunto.add("Valor 1");                   // $11 ==> true
conjunto.add("Valor 2");                   // $12 ==> true
conjunto.add("Valor 1");                   // $13 ==> false
conjunto;                                  // conjunto ==> [Valor 1, Valor 2]

var mapa = new HashMap<Integer, String>(); // mapa ==> {}
mapa.put(1, "Valor 1");                    // $16 ==> null
mapa.put(2, "Valor 2");                    // $17 ==> null
mapa.put(3, "Valor 1");                    // $18 ==> null
mapa.put(1, "Valor 3");                    // $19 ==> "Valor 1"
mapa;                                      // mapa ==> {1=Valor 3, 2=Valor 2, 3=Valor 1}

Dá pra ver claramente que em uma List podemos adicionar (add) elementos repetidos, mas ao adicionar um elemento repetido em um Set ele não é alterado. Apesar de nosso exemplo manter a ordem, um Set não garante a ordem dos elementos. Observe também que quando adicionamos um elemento em um Set o método add irá retornar se o valor já existia ou não no conjunto.

Para um Map temos o comportamento um pouco diferente. Temos que usar a operação put com uma chave e um valor como parâmetros. Valores repetidos podem ser adicionados desde que com chaves diferentes, mas quando reutilizamos uma chave, o antigo valor associado a ele é o retorno da operação.

Essas três classes são muito usadas e por isso é bom conhecer cada método dela. Recomendo ler o Javadoc mesmo que você não saiba ler em inglês, tente usar o Google Translator. Você deve ficar atento é a versão da documentação que você está lendo. Cada método e classe terá uma referência sobre a versão do Java na qual ela foi introduzida. Por exemplo, abaixo tempos o método Map#copyOf) que foi introduzida na JDK 9.

javadoc
Figura 4. Documentação da classe Map, método copyOf

Tipos de Listas

Como falamos anteriormente, listas servem para armazenar objetos sequencialmente. No nosso exemplo, usamos a class ArrayList, mas ela não é a única classe de lista existente, temos também a LinkedList. Vamos ver a diferença das duas?

Para compreender bem a diferença das duas classes, precisamos conhecer um pouco de como elas são implementadas.

A classe ArrayList é uma abstração de uma lista sobre um vetor. A classe é inicializada, por padrão, alocando um vetor de tamanho 10. Esse tamanho só será alterado quando a capacidade máxima dela for atingida, o que significa que a operação add pode significar que um vetor inteiro foi criado com o tamanho n + 1 e depois todos os elementos foram copiados para o novo vetor.

— Isso não me parece uma boa coisa…​

Exato! Se a classe é utilizada para uma lista que removemos e adicionamos elementos constantemente, ela terá uma péssima performance. Quando adicionamos um elemento, no melhor caso é uma operação de tempo constante, mas no pior caso pode ser que o tempo dessa operação dependa do tamanho da lista (aqui tem o conceito de Análise assintótica que vamos falar em outro post). Já para se remover um elemento é preciso copiar todos os elementos posteriores a posição do elemento removido, o que significa que essa operação só é ótima quando removemos o último elemento.

— Então a classe ArrayList é péssima!

Não! Nós só falamos as desvantagens dessa classe! Ela é a classe do Java Collection mais utilizada, pois ela é ótima quando você tem uma lista de acesso aleatório.

— Que raios é acesso aleatório?!?!

Acesso aleatório é quando você precisa acessar um elemento qualquer da lista sem nenhuma ordenação. Digamos que você deseja acessar a posição 541 de uma lista com 9172 elementos, o tempo de acesso é constante. O mesmo acontece se você precisa substituir um elemento dentro da lista.

Logo, essa classe é ótima para listas de tamanhos fixos (ou com pouca variação) e que precise de acesso aleatório. Se você já sabe o tamanho da lista que irá preencher, você pode já iniciar a classe com o tamanho deseja, isso vai poupar muito processamento do seu software!

A outra classe é a LinkedList, ela é bem mais complexa que a ArrayList. Se você abrir o código dela, vai ver que a classe só armazena o primeiro elemento, o último elemento e o tamanho da lista. Cada elemento é um nó da lista, que contém uma referência ao elemento posterior e anterior. Isso significa que para acessar um elemento, é preciso navegar na lista pelos nós.

— OI?!?!

Vamos demonstrar…​ Se tivermos uma lista com 10 elementos, e eu preciso acessar o elemento na 5ͣ a operação vai acessar os elementos 1, 2, 3, 4 e depois retornar o 5. Isso significa que qualquer operação que não seja na cabeça ou na calda da lista vai depender da posição do elemento.

— Então ela não serve para acesso aleatórios como a ArrayList?!?

Servir ela serve…​ Devemos usar a palavra ótimo! Ótimo é um conceito que sempre associamos a algo bom, mas na verdade ótimo é quando atingimos uma situação satisfatória de acordo com certos parâmetros. Servir não é um termo correto porque independente do uso as duas classes vão responder corretamente, mas se considerarmos o parâmetro velocidade, podemos escolher uma implementação de lista ótima.

Mas voltando a resposta…​ A LinkedList é ótima para usos em que elementos são adicionados/removidos no inicio e no final constantemente. É por esse motivo que a classe implementa duas interfaces que adicionam métodos importantes para o acesso direto desses elementos, a Queue e Deque.

Por fim podemos falar da PriorityQueue…​ Essa classe é especial porque ela pode funcionar como uma lista comum, mas podemos associar ela a um Comparator que irá definir a prioridade que os elementos devem ser acessados. Internamente os elementos são armazenados pela ordem de inserção, mas eles são retornados pelos métodos poll() de acordo com a ordem estabelecida pelo comparador usado no construtor, isso significa que você sempre inicializar com um comparador.

Vamos ver ela em execução? No exemplo abaixo vamos adicionar algumas Strings e ver como elas são retornadas pelo método poll().

var lista = new PriorityQueue<String>();  // lista ==> []
lista.add("a");                           // $2 ==> true
lista.add("d");                           // $3 ==> true
lista;                                    // lista ==> [a, d]
lista.add("b");                           // $5 ==> true
lista;                                    // lista ==> [a, d, b]
lista.add("d");                           // $7 ==> true
lista;                                    // lista ==> [a, d, b, d]
lista.poll();                             // $9 ==> "a"
lista.poll();                             // $10 ==> "b"
lista.poll();                             // $11 ==> "d"
lista.poll();                             // $12 ==> "b"

Observe que existe uma ordenação no retorno, tanto que a falta de ordem na adição foi resolvida. Essa classe é muito útil quando precisamos implementar uma lista de prioridades.

Tipos de Conjuntos

Os conjuntos são mais simples que as Listas, vamos ter duas classes importantes: HashSet e TreeSet.

HashSet deve ser usada quando a ordem dos elementos não é importante, tanto que a interface não dispõe de métodos para acesso sequencial aos elementos. Os elementos são tratados como um conjunto. Se você for abrir a implementação do HashSet, ela usa um HashMap internamente, a seguir veremos como o HashMap funciona. A adição/remoção em um HashSet são mais rápidas que em uma TreeSet.

Já a TreeSet é um conjunto ordenado, por isso existe a necessidade de um Comparator, isso significa que os elementos podem ser acessados em ordem, mas ao se adicionar há uma penalidade pois haverá uma operação de balanceamento da árvore interna.

Em resumo, use HashSet se a ordem não importa e TreeSet se a ordem importa!

Tipos de Mapas

Os mapas são a base de implementação dos conjuntos, HashMap terá o mesmo comportamento do HashSet exceto pelo fato de que ao invés de indexar pelo próprio elemento, ele será indexado pela chave. Já o TreeMap vai armazenar os elementos seguindo a ordenação das chaves.

Streams

Stream é uma interface pela qual teremos um post especifico futuramente pois essa foi uma das maiores contribuições do Java 8. Quando usamos o método stream() presente em cada Collection, nós não criamos uma nova coleção, nós apenas iniciamos o processo de criação de uma pipeline. O principal conceito de um Stream é que a construção da nova collection será postergada até que o final dela seja conhecido. Essa propriedade é o que chamamos de Lazy Evaluation, isso significa que existirá um algoritmo para criação dessa lista, mas ele só será executado ao final.

— Entendi bulhufas!

OK! Vamos demonstrar usando o JShell…​

var lista = Arrays.asList("a", "aaa", "b", "c", "aaaaa", "asdada");       // lista ==> [a, aaa, b, c, aaaaa, asdada]
lista.stream().filter(x -> x.contains("a")).collect(Collectors.toList()); // $2 ==> [a, aaa, aaaaa, asdada]

No código acima nós criamos uma lista e depois criamos um Stream baseado nela. Até chamar o método collect, o Stream não passava de uma sequência de operações sob a lista, depois se cria uma nova lista (poderia ser qualquer coisa) usando as operações. A lista original não é alterada!

Conclusão

Collections é uma biblioteca onipresente! Em qualquer código você verá vestígio dela. Experimente e conheça.

Java 101
(série de 6 partes)

Como começar a aprender Java
A sintaxe do Java
Collections!?!? Listas, conjuntos e mapas... as classes mais usadas do Java!
OO: Eu vejo objetos por todos os cantos!
Java I/O
Concorrência e Paralelismo
Originally published May 06, 2022