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<e> é 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<string> 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.</string></e>

Collection<e></e>

Raiz das coleções. Define os métodos mais gerais (ex.: size()), independentes da estrutura e da forma de acesso da coleção.

Iterator<e></e>

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<e></e>

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<k,v></k,v>

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