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

Você precisa estar logado para dar um feedback. Clique aqui para efetuar o login
Para efetuar o download você precisa estar logado. Clique aqui para efetuar o login
Confirmar voto
0
 (2)  (0)

Artigo publicado na Java Magazine Edição 18.

Esse artigo faz parte da revista Java Magazine edição 18. Clique aqui para ler todos os artigos desta edição

jm18_capa.jpg


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 .

Set

Agrupa objetos sem permitir duplicatas – similar aos conjuntos da matemática. SortedSet garante iteração ordenada. O J2SE 1.4 adiciona LinkedHashSet, com ordem estável de iteração. Implementados, respectivamente, por HashSet, TreeSet e LinkedHashSet, que utilizam internamente uma HashMap, TreeMap ou LinkedHashMap, na qual a chave é igual ao valor (chave?chave).

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

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

A exibição deste artigo foi interrompida :(
Este post está disponível para assinantes MVP

 
Você precisa estar logado para dar um feedback. Clique aqui para efetuar o login
Receba nossas novidades
Ficou com alguma dúvida?