Coleções de ponta a ponta
As APIs Java para Estruturas de Dados
Conheça a fundo as Collections do Java 2 e Tiger, o Commons Collections e outras APIs
A
ciência da computação é um edifício suportado por dois alicerces:
algoritmos e estruturas de dados. Mas enquanto o desenvolvimento de
novos algoritmos é uma tarefa recorrente em qualquer projeto com o
mínimo de complexidade, as estruturas de dados se prestam melhor à
padronização e ao reuso, tendo sido identificado um número
relativamente pequeno de estruturas que satisfazem às necessidades da
grande maioria das aplicações.
Num
sentido mais amplo, qualquer entidade que contém dados é uma “estrutura
de dados”, e isso inclui qualquer objeto que possua pelo menos um
atributo, bem como grupos mais complexos de vários objetos, como um
objeto Retangulo contendo dois objetos Ponto. Mas vamos usar aqui a
definição mais estrita, onde “estrutura de dados” é uma entidade cuja
funcionalidade essencial (semântica) consiste na sua forma de organizar
os dados, e não nos dados propriamente ditos. Por exemplo, um Array é
uma estrutura que organiza dados de forma a permitir acesso aleatório
para leitura e escrita. O que existe em cada posição do array é menos
importante.
Por
essa definição, os termos “estrutura de dados” e “coleção” tornam-se
sinônimos, pois coleções são precisamente aquelas entidades dedicadas a
armazenar e organizar dados de alguma forma. Os livros-texto de
computação dedicados ao assunto costumam usar a expressão “Estruturas
de Dados”, mais tradicional. O termo “coleção” é mais recente, e parece
ter se originado da linguagem Smalltalk, a primeira a instituir uma
biblioteca ampla e bem organizada de tais objetos como parte essencial
do seu ambiente de programação.
Muitos
programadores que se habituaram a trabalhar com bibliotecas
padronizadas de coleções tendem a classificar a disciplina de
estruturas de dados como uma daquelas matérias espinhosas que se tornam
inúteis após a formatura. Afinal, quem precisa saber implementar uma
hashtable hoje em dia? Está tudo pronto, pelo menos em qualquer
ambiente de programação mais ou menos respeitável (até no C++, que hoje
tem a STL, standard template library). Por outro lado, o fato de termos
APIs prontas não elimina a utilidade de conhecer o assunto de forma
mais profunda. As coleções continuam sendo entidades complexas, e às
vezes não é óbvia a melhor maneira de utilizá-las, especialmente quando
há demandas de alto desempenho.
Nota:
Devido ao grande número de classes e interfaces mencionadas, para
facilitar a leitura identificaremos as interfaces usando o estilo
Interface e as classes com Classe. Por exemplo: List, ArrayList.
Coleções primitivas
Como
programador de C++ numa vida anterior, lembro-me bem da declaração de
Bjarne Stroustrup, que seu maior erro foi não ter incluído uma boa
biblioteca de coleções na primeira versão daquela linguagem. James
Gosling e equipe começaram melhor, mas não muito. A versão 1.0 do Java
já tinha um suporte elementar a coleções (Vector, Stack, Hashtable,
Properties, BitSet, Enumeration, e os arrays nativos – tipo[]). O
tamanho reduzido da API se justificaria considerando o tamanho total do
Java 1.0, mas pior era o design da API, pouco extensível. Essa
deficiência logo deu espaço para bibliotecas de terceiros oferecendo
coleções mais ricas e bem elaboradas, como a JGL (inspirada na STL do
C++).
Coleções
são tão essenciais para qualquer linguagem decente quanto strings ou o
loop for. Felizmente, o problema foi logo reparado com a biblioteca de
collections, introduzida no Java 2 (e também disponível numa versão
para JDK 1.1.x, mas esta versão não é mais atualizada desde o
lançamento do J2SE 1.2).
Coleções do Java 2
A
API original de collections é um dos pontos fortes do Java: em minha
opinião, uma das APIs mais bem projetadas da plataforma J2SE,
especialmente na sua estruturação em três camadas: interfaces (ex.:
List), classes abstratas (AbstractList) e classes de implementação
(ArrayList).
Estas
coleções já estão há muitos anos na praça, mas vale a pena revisá-las.
A partir do J2SE 5.0, todas foram “reformadas” para suporte a tipos
genéricos, por isso vamos exibir os parâmetros genéricos pelo menos
para os tipos principais. Por exemplo, Collection
Collection
Raiz das coleções. Define os métodos mais gerais (ex.: size()), independentes da estrutura e da forma de acesso da coleção.
Iterator
Raiz
dos iteradores, que encapsulam a navegação dos elementos de uma
coleção. Iterator suporta acesso unidirecional e remoção do elemento
corrente. Algumas coleções suportam especializações mais capazes, como
ListIterator que faz navegação bidirecional. Veja mais no quadro
“Iteradores em detalhe”.
List
Coleção
que organiza elementos seqüencialmente, permitindo acesso posicional,
por índices (de 0 a size-1) de forma similar aos arrays primitivos. Mas
nem toda lista garante acesso indexado com tempo constante (no qual
todos elementos podem ser lidos ou alterados com o mesmo esforço);
quando for o caso, a lista implementará a interface marcadora
RandomAccess. É o caso de ArrayList, que usa internamente um array
primitivo para armazenar os valores. Mas não é o caso de LinkedList,
que usa uma lista duplamente encadeada de nós; cada nó possui um
ponteiro para um objeto armazenado na lista e dois ponteiros para os
nós anterior e seguinte. Essa estrutura permite inserções ou remoções
eficientes em qualquer posição da lista, mas um acesso randômico como
get(10) requer percorrer todos os primeiros 9 nós (exceto se a lista
tiver menos de 20 elementos, pois daí a busca é feita a partir do
último nó).
Map
Coleção que usa objetos para indexar elementos, produzindo um conjunto de pares (chave?valor).
HashMap utiliza o código de hashing das chaves (retornado por
hashCode()) para otimizar a procura dos objetos – veja o quadro
“Hashtables em detalhe”. SortedMap especializa Map para mapas ordenados
pela chave; implementado por TreeMap (com árvores red-black).
WeakHashMap utiliza uma WeakReference para cada chave, facilitando a
criação de caches amigáveis ao garbage collector.
O
J2SE 1.4 acrescentou mais duas implementações. IdentityHashMap é mais
eficiente quando a igualdade de referência (==) é suficiente para
diferenciar as chaves. LinkedHashMap mantém uma lista encadeada de
ponteiros entre as chaves, suportando uma ordem de iteração estável
mesmo após alterações na coleção. Por exemplo, se o mapa tinha as
chaves (a, b, c) e um iterador produzido neste momento percorreu-os na
ordem (c, a, b), então após removermos ‘a’ e adicionarmos ‘x’, os
elementos ‘c’ e ‘b’ (que já existiam na iteração anterior) serão
iterados na mesma ordem de antes, de forma que poderemos ter: (c, b,
x), (c, x, b) ou (x, c, b). É uma garantia fraca, comparada à ordenação
completa de um SortedMap, mas é suficiente para alguns algoritmos e com
um custo menor que o da ordenação completa.
Observe
que os mapas são um caso excepcional: eles não herdam Collection. É que
operações como iteração, contains() e outras poderiam ser feitas por
chave, por valor ou ambos, e os projetistas das collections decidiram
não privilegiar nenhuma opção. Para compensar, são oferecidas as
“coleções-view”: keySet(), valueSet() e entrySet(). As coleções
retornadas por estes métodos não são cópias do mapa, e sim coleções
virtuais com os mesmos elementos; alterações feitas no mapa serão
refletidas em todas as views, e vice-versa .
Set
Agrupa objetos sem permitir duplicatas – similar aos conjuntos da matemática. SortedSet
Collections e Arrays
Arrays
e Collections são classes utilitárias, com métodos static para
operações como pesquisa, ordenação ou conversão. Alguns gostariam que
estes métodos fossem movidos para as coleções (permitindo chamar, por
exemplo, lista.sort() ao invés de Collections.sort(lista)), mas isso
foi feito assim para evitar uma poluição excessiva das interfaces, e
também para facilitar a implementação de novas coleções. Por exemplo,
se sort() fosse um método de List, toda implementação desta interface
seria obrigada a implementar esse método, ou herdar uma implementação
padrão de AbstractList. Mesmo a herança é um requisito inconveniente
numa linguagem que não suporta herança múltipla de classes. A API
também emprega o recurso de operações opcionais. Por exemplo,
List.add() é opcional, de forma que uma implementação válida desta
interface poderia lançar uma exceção indicando não haver suporte a tal
método (o que é útil em listas somente de leitura, como as retornadas
por Collections.unmodifiableList()).
Comparator
Interfaces
auxiliares, usadas em todas as coleções ou métodos de ordenação.
Comparator é mais flexível (cada ordenação dos mesmos objetos pode ser
feita por um critério diferente, bastando fornecer um novo comparador),
enquanto Comparable facilita a programação, mas é mais adequada a
classes que sempre são ordenadas pelos mesmos critérios.
Mais coleções
Além
dessas, há várias classes em outras APIs que implementam alguma
interface de collections, ou estendem alguma de suas classes. Por
exemplo, java.awt.RenderingHints (da API Java 2D) implementa Map. Mas
este e outros exemplos são coleções para finalidades especializadas, e
não de uso geral como as encontradas em java.util.
Coleções “Legadas”
As
coleções primitivas foram todas “recauchutadas” para suportar também as
novas interfaces; por exemplo, Vector implementa List. Isso deixa estas
classes mais confusas – por exemplo, pode-se usar tanto elementAt()
quanto get() para fazer a mesma coisa. Mas é uma boa estratégia de
migração de código legado: você pode começar substituindo as invocações
aos métodos antigos pelos novos, e só depois mudar os tipos de
variáveis, parâmetros, atributos e valores de retorno, o que costuma
ser mais difícil devido ao impacto “em cascata” sobre outras classes
que invoquem as suas.
