Dissecando a Java Collections - Revista Java Magazine 96

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!