Artigo Java Magazine 18 - Coleções de ponta a ponta

Clique aqui para ler este artigo em PDF

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 é uma coleção com um único argumento genérico E, que neste caso, parametriza o tipo do elemento armazenado na coleção. Se uma variável for declarada como Collection nomes, será uma coleção que armazena somente strings. Uma operação como nomes.add(Boolean.FALSE) irá gerar um erro de compilação, enquanto uma operação como String x = nomes.get(0) não exigirá typecast. Veja o artigo “Tipos no J2SE 5.0” (Edição 16) para mais detalhes sobre tipos genéricos.

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 ."