Atenção: esse artigo tem um vídeo complementar. Clique e assista!
É exposto o funcionamento interno das principais implementações da interface Collection: ArrayList, LinkedList, HashSet, TreeSet, HashMap e TreeMap. Neste artigo é detalhado principalmente sobre quais estruturas de dados cada uma dessas classes foi desenvolvida. Além disso, outros detalhes de implementação (bem como conceitos de computação) vêm à tona.
Em que situação o tema é útil:
No mundo da tecnologia, a demanda por softwares melhores e inovadores exige que os desenvolvedores de software não apenas conheçam bem as estruturas de dados mais usadas, mas também que sejam versáteis o suficiente para saber implementar novas estruturas ou estender estruturas existentes de acordo com a necessidade do projeto. Nessas situações, para as quais devemos estar sempre preparados, o conhecimento exato sobre as estruturas e classes existentes passa a ser básico.
Resumo DevMan:
Entre as interfaces do Java Collections Framework, as mais usadas são List, Set e Map. Suas implementações principais, no entanto, merecem atenção especial em seus detalhes.
Por exemplo, ArrayList e LinkedList são classes estruturalmente diferentes, visto que ArrayList é construída sobre um array e usa métodos internos para redimensioná-lo quando necessário, enquanto LinkedList representa uma lista duplamente encadeada, onde cada elemento aponta para o próximo e para o anterior.
HashSet e TreeSet, por sua vez, possuem uma similaridade: ambas as classes foram construídas utilizando suas similares, respectivamente HashMap e TreeMap. Sendo assim, HashSet provê operações com acesso direto aos seus itens (complexidade de tempo linear), mas não guarda uma ordem específica deles. TreeSet, por outro lado, guarda seus elementos de forma ordenada, não oferecendo, no entanto, operações tão eficientes quanto HashSet. A classe HashMap foi desenvolvida com base em tabelas hash, utilizando o hashCode() dos objetos inseridos e fazendo um rehash muito interessante desse código de modo a se proteger contra colisões. Já objetos do tipo TreeMap têm como base árvores rubro-negras, que possuem um forte mecanismo de auto balanceamento, impedindo que a estrutura degenere e garantindo buscas em tempo logarítmico mesmo no pior caso.
Uma coleção é dito de forma simples, uma estrutura que agrupa vários objetos em um único. Todas as linguagens de programação possuem uma forma de expressar essa abstração tão necessária ao desenvolver sistemas, e em Java não seria diferente: temos o Collections Framework, introduzido desde a versão 1.2 da plataforma. Neste contexto, vamos abordar aqui alguns tópicos relativos ao funcionamento interno das classes que fazem parte das interfaces-chave da API: List, Set e Map.
Você já se perguntou quando usar um ArrayList ao invés de um LinkedList? Um HashMap ao invés de TreeMap? Qual a diferença fundamental entre as diferentes implementações?
Além de analisar o desempenho das classes mais conhecidas de cada uma dessas interfaces, iremos compreender as estruturas de dados que as caracterizam e que funcionam realmente como “esqueleto” delas.
Com um conhecimento mais profundo da implementação das classes, o leitor poderá se beneficiar quando for necessário tomar decisões técnicas em seu projeto de software, levando em conta os tradeoffs existentes entre as classes. Principalmente em projetos onde desempenho é crucial, conhecer a anatomia das classes pode salvar a sua pele e a de sua equipe.
List
Assim que você começa a ter um pouco mais de prática com programação, você logo para de usar array para guardar objetos e começa a utilizar algo mais fácil de manipular, listas por exemplo. No caso de Java, listas são representadas pela interface java.util.List, que é, com certeza, uma das interfaces mais utilizadas na linguagem. Mas, como essa interface funciona como uma abstração do conceito de listas? Responderemos essa pergunta a seguir e aprenderemos o mecanismo por trás das duas implementações mais conhecidas de List.
Representação
Como o próprio nome já diz, a interface java.util.List representa uma lista de elementos. Assim como uma lista de filmes prediletos ou uma lista de compras, listas possuem um primeiro elemento e um último, tendo assim, uma ordem definida. Uma lista pode possuir elementos repetidos e também aumentar de tamanho. Elas funcionam basicamente como vetores (ou arrays), adicionando, acessando e removendo elementos, no entanto, mais flexíveis, dado que podem aumentar ou diminuir de tamanho. O conceito dessa estrutura é realmente bem simples, por isso, vamos logo explicar os detalhes sobre suas implementações principais: ArrayList e LinkedList.
ArrayList
ArrayList é uma implementação de List que usa um array para guardar os elementos, onde executa operações de redimensionamento sempre que necessário. Toda vez que o construtor de ArrayList é chamado passando initialCapacity como parâmetro, um array com esse tamanho é criado. Caso nenhum valor seja informado, a capacidade inicial do array é 10, sendo este o valor default.
Observando os seus principais métodos de manipulação de elementos: get(), set() e add() (em suas duas versões), é fácil perceber porque esses métodos possuem complexidade de tempo constante, ou O(1). Todos eles passam como parâmetro o índice do elemento desejado, por isso o acesso é direto. Para entender melhor essa questão, vamos ver um exemplo de método dessa classe. Primeiramente, iremos destrinchar o método ensureCapacity(), que é utilizado pelo add(), que será visto em seguida.
ensureCapacity() é um dos métodos de ArrayList que serve para redimensionar o array de elementos. O método recebe como parâmetro um inteiro que representa a capacidade mínima que o array deve ter. Um erro comum é confundir capacidade do ArrayList com o seu tamanho, representado pelo atributo size. O tamanho do ArrayList refere-se a quantos elementos ele possui no momento. Veja a implementação de ensureCapacity() na Listagem 1. Note que utilizamos comentários como “\\ Linha n”, o que significa que essa linha específica de código será detalhada posteriormente. Usaremos essa notação em outras listagens no artigo.
Listagem 1. Método ensureCapacity() de ArrayList.
public void ensureCapacity(int minCapacity) {
modCount++;
int oldCapacity = elementData.length;
if (minCapacity > oldCapacity) { \\ Linha 1
Object oldData[] = elementData;
int newCapacity = (oldCapacity * 3)/2 + 1; \\ Linha 2
if (newCapacity < minCapacity) \\ Linha 3
newCapacity = minCapacity;
elementData = Arrays.copyOf(elementData, newCapacity); \\ Linha 4
}
}Linha 1: É primeiramente verificado se o tamanho do array é maior do que minCapacity. Se for, nada acontece, afinal, o array tem bastante espaço para confortar mais elementos. Caso contrário, haverá um redimensionamento do array.
Linha 2: A questão agora é: de quanto será o redimensionamento? Mais um? Mais dois? Isso seria pouco eficiente caso você estivesse adicionando milhares de elementos, não acha? Seria necessário redimensionar o array milhares de vezes (uma vez a cada chamada). Igualmente, redimensionar em 5.000 seria um desperdício de espaço se o array guardasse poucos elementos. Portanto, nessa linha podemos ver que o redimensionamento é exponencial: o array cresce 1.5x a cada chamada. Quer o cliente adicione muitos ou poucos elementos, o ArrayList se adapta proporcionalmente. No pequeno cálculo feito nesta linha, pode notar que é somado 1 ao resultado da divisão. Caso esteja curioso, esse “+1” é para os casos de o array ser vazio ou de tamanho 1. Assim, o valor da variável newCapacity sempre será maior que o valor de oldCapacity. Se, por exemplo, oldCapacity fosse 1 e não houvesse o “+1” na equação, newCapacity nunca passaria de 1 (pois a parte inteira de 1*1.5=1), ou seja, o array na verdade não estaria se expandindo!
Linha 3: O array cresce 150%, exceto se o parâmetro minCapacity for ainda maior que essa nova capacidade calculada. Nesse caso, o array toma o valor de minCapacity.
Linha 4: É criado um novo array com capacidade maior e seus elementos são todos copiados do array “antigo”. O método usado para copiar os elementos é Arrays.copyOf(), que por sua vez, usa System.arraycopy() em sua implementação. Veremos mais sobre esse último adiante.
Observe agora a implementação do método add(int index, E element), que insere um elemento na posição indicada por index (veja a Listagem 2). Note também que, apesar de esse método ser executado em tempo constante O(1), caso o array necessite ser expandido, o custo torna-se linear.
Listagem 2. Método add() de ArrayList.
public void add(int index, E element) {
if (index > size || index < 0)
throw new IndexOutOfBoundsException("Index: "+index+", Size: "+size);
ensureCapacity(size+1); // Linha 1
System.arraycopy(elementData, index, elementData, index + 1,size - index); //Linha 2
elementData[index] = element;
size++;
} ... 
