Login Registre-se

Home > Artigos > Java em Geral >

Collections Framework

Publicado por ronaldtm em 17/08/2009 - 74.232 visualizações



comentários: 5

O Collections Framework
Veja também: http://www.javafree.org/artigo/6953/Cap-7-Objetos-e-conjuntos


    "Desde a versão 1.2 do JDK (depois que o renomearam para Java 2 SDK), a plataforma J2SE inclui um framework de coleções (a Collections Framework). Uma coleção é um objeto que representa um grupo de objetos. Um framework de coleções é uma arquitetura unificada para representação e manipulação de coleções, permitindo que elas sejam manipuladas independentemente dos detalhes de sua implementação.

    As principais vantagens do collections framework são:

    - Redução do esforço de programação, fornecendo estruturas de dados e algoritmos úteis, para que não seja necessário reescrevê-los.

    - Aumento da performance, fornecendo implementações de alta performance. Como as várias implementações de cada interface são substituíveis, os programas podem ser facilmente refinados trocando-se as implementações.

    - Interoperabilidade entre APIs não relacionadas, estabelecendo uma linguagem comum para passagem de coleções.

    - Redução do esforço de aprendizado de APIs, eliminando a necessidade de se aprender várias APIs de coleções diferentes.

    - Redução do esforço de projetar e implementar APIs, eliminando a necessidade de se criar APIs de coleções próprias.

    - Promover o reúso de software, fornecendo uma interface padrão para coleções e algoritmos para manipulá-los.


    O Collections Framework consiste em:

    - Interfaces de coleções - representam diferentes tipos de coleção, como conjuntos, listas e arrays associativos. Estas interfaces formam a base do framework.

    - Implementação de uso geral - implementações básicas das interfaces de coleções.

    - Implementações legadas - as classes de coleções de versões anteriores, Vector e Hashtable, foram remodeladas para implementar as interfaces de coleções (mantendo a compatibilidade).

    - Implementações de wrappers - adicionam funcionalidades, como sincronização, a outras implementações.

    - Implementações convenientes - "mini-implementações" de alta performance das interfaces de coleções.

    - Implementações abstratas - implementações parciais das interfaces de coleções, para facilitar a criação de implementações personalizadas.

    - Algoritmos - métodos estáticos que performam funções úteis sobre coleções, como a ordenação de uma lista.

    - Utilitários de Arrays - funções utilitárias para arrays de primitivas e objetos. Estritamente falando, não pertence ao Collections Framework, porém, esta funcionalidadefoi adicionada à plataforma Java ao mesmo tempo, e utiliza parte da mesma infraestrutura." (tradução livre de um trecho da documentação do JDK)



Coleções

Collection

Interface base para todos os tipos de coleção. Ela define as operações mais básicas para coleções de objetos, como adição (add) e remoção (remove) abstratos (sem informações quanto à ordenação dos elementos), esvaziamento (clear), tamanho (size), conversão para array (toArray), objeto de iteração (iterator), e verificações de existência (contains e isEmpty).




List

Interface que extende Collection, e que define coleções ordenadas (sequências), onde se tem o controle total sobre a posição de cada elemento, identificado por um índice numérico. Na maioria dos casos, pode ser encarado como um "array de tamanho variável" pois, como os arrays primitivos, é acessível por índices, mas além disso possui métodos de inserção e remoção.



    ArrayList

    Implementação de List que utiliza internamente um array de objetos. Em uma inserção onde o tamanho do array interno não é suficiente, um novo array é alocado (de tamanho igual a 1.5 vezes o array original), e todo o conteúdo é copiado para o novo array. Em uma inserção no meio da lista (índice < tamanho), o conteúdo posterior ao índice é deslocado em uma posição. Esta implementação é a recomendada quando o tamanho da lista é previsível (evitando realocações) e as operações de inserção e remoção são feitas, em sua maioria, no fim da lista (evitando deslocamentos), ou quando a lista é mais lida do que modificada (otimizado para leitura aleatória).


    LinkedList

    Implementação de List que utiliza internamente uma lista encadeada. A localização de um elemento na n-ésima posição é feita percorrendo-se a lista da ponta mais próxima até o índice desejado. A inserção é feita pela adição de novos nós, entre os nós adjacentes, sendo que antes é necessária a localização desta posição. Esta implementação é recomendada quando as modificações são feitas em sua maioria tanto no início quanto no final da lista, e o percorrimento é feito de forma sequencial (via Iterator) ou nas extremidades, e não aleatória (por índices). Um exemplo de uso é como um fila (FIFO - First-In-First-Out), onde os elementos são retirados da lista na mesma sequência em que são adicionados.


    Vector

    Implementação de List com o mesmo comportamento da ArrayList, porém, totalmente sincronizada. Por ter seus métodos sincronizados, tem performance inferior ao de uma ArrayList, mas pode ser utilizado em um ambiente multitarefa (acessado por várias threads) sem perigo de perda da consistência de sua estrutura interna.
    Em sistemas reais, essa sincronização acaba adicionando um overhead desnecessário, pois mesmo quando há acesso multitarefa à lista (o que não acontece na maioria das vezes), quase sempre é preciso fazer uma nova sincronização nos métodos de negócio, para \'atomizarem\' operações seguidas sobre o Vector. Por exemplo, uma chamada ao método contains(), seguida de uma chamada do método add() caso o elemento não exista, podem causar condições de corrida, se há acessos de várioas threads ao mesmo tempo. Assim, acaba sendo necessária uma sincronização adicional, englobando estas duas operações e tornando desnecessária a sincronização inerente da classe.
    Portanto, a não ser que hajam acessos simultâneos de várias threads à lista, e a sincronização simples, provida pela classe Vector, seja o bastante, prefira outras implementações como ArrayList e LinkedList, que oferecem performance superior.


    Stack

    Implementação de List que oferece métodos de acesso para uso da lista como uma pilha (LIFO - Last-In-First-Out), como push(), pop() e peek(). Estende Vector, portanto herda as vantagens e desvantagens da sincronização deste. Pode ser usado para se aproveitar as implementações das operações específicas de pilha.


Set

Interface que define uma coleção, ou conjunto, que não contém duplicatas de objetos. Isto é, são ignoradas as adições caso o objeto ou um objeto equivalente já exista na coleção. Por objetos equivalentes, entenda-se objetos que tenham o mesmo código hash (retornado pelo método hashCode()) e que retornem verdadeiro na comparação feita pelo método equals().
Não é garantida a ordenação dos objetos, isto é, a ordem de iteração dos objetos não necessariamente tem qualquer relação com a ordem de inserção dos objetos. Por isso, não é possível indexar os elementos por índices numéricos, como em uma List.



    HashSet

    Implementação de Set que utiliza uma tabela hash (a implementação da Sun utiliza a classe HashMap internamente) para guardar seus elementos. Não garante a ordem de iteração, nem que a ordem permanecerá constante com o tempo (uma modificação da coleção pode alterar a ordenação geral dos elementos). Por utilizar o algoritmo de tabela hash, o acesso é rápido, tanto para leitura quanto para modificação.



    LinkedHashSet

    Implementação de Set que estende HashSet, mas adiciona previsibilidade à ordem de iteração sobre os elementos, isto é, uma iteração sobre seus elementos (utilizando o Iterator) mantém a ordem de inserção (a inserção de elementos duplicados não altera a ordem anterior). Internamente, é mantida uma lista duplamente encadeada que mantém esta ordem. Por ter que manter uma lista paralelamente à tabela hash, a modificação deste tipo de coleção acarreta em uma leve queda na performance em relação à HashSet, mas ainda é mais rápida que uma TreeSet, que utiliza comparações para determinar a ordem dos elementos.




SortedSet

Interface que estende Set, adicionando a semântica de ordenação natural dos elementos. A posição dos elementos no percorrimento da coleção é determinado pelo retorno do método compareTo(o), caso os elementos implementem a interface Comparable, ou do método compare(o1, o2) de um objeto auxiliar que implemente a interface Comparator.



    TreeSet

    Implementação de SortedSet que utiliza internamente uma TreeMap, que por sua vez utiliza o algoritmo Red-Black para a ordenação da árvore de elementos. Isto garante a ordenação ascendente da coleção, de acordo com a ordem natural dos elementos, definida pela implementação da interface Comparable ou Comparator. Use esta classe quando precisar de um conjunto (de elementos únicos) que deve estar sempre ordenado, mesmo sofrendo modificações. Para casos onde a escrita é feita de uma só vez, antes da leitura dos elementos, talvez seja mais vantajoso fazer a ordenação em uma List, seguida de uma cópia para uma LinkedHashSet (dependendo do tamanho da coleção e do número de repetições de elementos).



Map

Interface que define um array associativo, isto é, ao invés de números, objetos são usados como chaves para se recuperar os elementos. As chaves não podem se repetir (seguindo o mesmo princípio da interface Set), mas os valores podem ser repetidos para chaves diferentes. Um Map também não possui necessariamente uma ordem definida para o percorrimento.



    HashMap

    Implementação de Map que utiliza uma tabela hash para armazenar seus elementos. O tempo de acesso aos elementos (leitura e modificação) é constante (muito bom) se a função de hash for bem distribuída, isto é, a chance de dois objetos diferentes retornarem o mesmo valor pelo método hashCode() é pequena.


    LinkedHashMap

    Implementação de Map que estende HashMap, mas adiciona previsibilidade à ordem de iteração sobre os elementos, isto é, uma iteração sobre seus elementos (utilizando o Iterator) mantém a ordem de inserção (a inserção de elementos duplicados não altera a ordem anterior). Internamente, é mantida uma lista duplamente encadeada que mantém esta ordem. Por ter que manter uma lista paralelamente à tabela hash, a modificação deste tipo de coleção acarreta em uma leve queda na performance em relação à HashMap, mas ainda é mais rápida que uma TreeMap, que utiliza comparações para determinar a ordem dos elementos.


    Hashtable

    Assim como o Vector, a Hashtable é um legado das primeiras versões do JDK, igualmente sincronizado em cada uma de suas operações. Pelos mesmos motivos da classe Vector, dê preferência a outras implementações, como a HashMap, LinkedHashMap e TreeMap, pelo ganho na performance.


    Properties

    Classe que estende Hashtable, especializada para trabalhar com Strings. Não é propriamente uma coleção (já que se restringe basicamente a Strings), mas serve como exemplo de uma implementação especializada da interface Map.


    IdentityHashMap

    Implementação de Map que intencionalmente viola o contrato da interface, utilizando a identidade (operador ==) para definir equivalência das chaves. Esta implementação deve ser usada apenas em casos raros onde a semântica de identidade referencial deve ser usada para equivalência.


    WeakHashMap

    Implementação de Map que utiliza referências fracas (WeakReference) como chaves, permitindo a desalocação pelo Garbage Collector dos objetos nela contidos. Esta classe pode ser usada como base para a implementação de caches temporários, com dados automaticamente desalocados em caso de pouca utilização.


SortedMap

Interface que estende Map, adicionando a semântica de ordenação natural dos elementos, análogo à SortedSet. Também adiciona operações de partição da coleção, com os métodos headMap(k) - que retorna um SortedMap com os elementos de chaves anteriores a k -, subMap(k1,k2) - que retorna um SortedMap com os elementos de chaves compreendidas entre k1 e k2 - e tailMap(k) - que retorna um SortedMap com os elementos de chaves posteriores a k.



    TreeMap
    Implementação de SortedMap que utiliza o algoritmo Red-Black para a ordenação da árvore de elementos. Isto garante a ordenação ascendente da coleção, de acordo com a ordem natural dos elementos, definida pela implementação da interface Comparable ou Comparator. Use esta classe quando precisar de um conjunto (de elementos únicos) que deve estar sempre ordenado, mesmo sofrendo modificações. Análogo ao TreeSet, para casos onde a escrita é feita de uma só vez, antes da leitura dos elementos, talvez seja mais vantajoso fazer a ordenação em uma List, seguida de uma cópia para uma LinkedHashSet (dependendo do tamanho da coleção e do número de repetições de chaves).





Interfaces auxiliares

O framework Collections define ainda uma série de interfaces auxiliares, que definem operações de objetos retornados por métodos das interfaces de coleções.

Iterator

Interface que define as operações básicas para o percorrimento dos elementos da coleção. Utiliza o pattern de mesmo nome (Iterator, GoF), desacoplando o código que utiliza as coleções de suas estruturas internas. É possível remover elementos da coleção original utilizando o método remove(), que remove o elemento atual da iteração, mas esta operação é de implementação opcional, e uma UnsupportedOperationException será lançada caso esta não esteja disponível.


ListIterator

Interface que estende Iterator, adicionando funções específicas para coleções do tipo List. É obtida através do método listIterator() de uma List, e possui operações de percorrimento em ambos os sentidos (permitido pela indexação dos elementos feita pela List).


Comparable

Interface que define a operação de comparação do próprio objeto com outro, usado para definir a ordem natural dos elementos de uma coleção. Pode ser usado caso os objetos que serão adicionados na coleção já implementem a interface (Integer, Double, String, etc.), ou serão implementados pelo programador, que tem a chance de embutir esta interface em seu código.


Comparator

Interface que define a operação de comparação entre dois objetos por um objeto externo. É utilizado quando os objetos a serem adicionados não podem ser modificados para aceitarem a interface Comparable (são de uma biblioteca de terceiros, por exemplo), ou é necessária a troca da estratégia de ordenação em tempo de execução (ordenação das linhas de uma tabela, por exemplo). Esta interface provê maior flexibilidade, sem custo adicional significativo. Prefira seu uso, ao invés da interface Comparable, a não ser que esta seja necessária (isto é, você usa uma classe que espera objetos que a implementem) ou se a própria semântica dos objetos exija esa ordem natural (o que é bem subjetivo e específico do domínio/sistema).


Enumeration

\'Ancestral\' da interface Iterator, que provê as mesmas funções, a não ser a retirada de elementos da coleção. Os nomes de seus métodos são bem mais longos - hasMoreElements() e nextElement() contra hasNext() e next() - o que dificulta a digitação e a leitura do código. É utilizada basicamente apenas nas classes Vector e Hashtable, podendo ser praticamente ignorada e substituída pela interface Iterator.


RandomAccess

Interface marcadora (marker interface), que apenas assinala que determinadas implementações de List são otimizadas para acesso aleatório (por índice numérico, ao invés de iterators). Ista informação pode ser usada por algumas classes, para que estas possam alterar suas estratégias internas para ganho de performance.


Classes Utilitárias

Classes utilitárias, como assumidas aqui, são classes que possuem apenas métodos estáticos, provendo algoritmos comuns.

Collections

Oferece métodos que efetuam operações sobre coleções. Algumas operações disponíveis são: busca binária em listas; substituição dos elementos de uma lista por um determinado objeto; busca pelo menor ou maior elemento (de acordo com a ordem natural definida pelas interfaces Comparable ou Comparator); inversão de uma lista; embaralhamento; deslocamento dos elementos; obtenção de coleções sincronizadas ou imutáveis, baseadas em coleções já existentes (através do pattern Decorator).


Arrays

Classe utilitária que oferece operações sobre arrays, incluindo: ordenação, procura binária, comparação entre arrays, preenchimento, cálculo do hashCode baseados nos elementos de um array, transformação em String e o invólucro de um array por uma implementação de tamanho fixo de List.




Programando por Interfaces

O Collections framework do Java nos fornece toda uma infraestrutura para estruturas de dados. E, por usar interfaces básicas bem definidas (Collection, List, Set, SortedSet, Map, SortedMap), cria também abstrações que aumentam a flexibilidade e a facilidade de modificação.

Quando programamos usando estas classes, devemos sempre referenciá-las pelas interfaces. Alguém pode dizer: "Mas não dá pra instanciar interfaces!" Claro que não. Quando precisamos instanciar uma coleção, utilizamos a implementação concreta mais apropriada, mas os tipos de parâmetros e retornos dos métodos devem sempre ser uma destas interfaces básicas.

Por exemplo, no código seguinte:



Suponha que tenhamos notado que não há acesso concorrente a este objeto, e a sincronização inerente do Vector está impactando na performance do sistema. Para alterarmos o tipo de Vector para ArrayList, eliminando o overhead desnecessário da sincronização, temos que alterar todas as classes que utilizam este método, pois elas passam e esperam um Vector, não um ArrayList.

Ou pior: suponha que estas classes que utilizam nossa lista de compras (criadas por outras equipes, portanto, mais difíceis de serem alteradas) também têm suas próprias estruturas internas de dados, utilizando a classe LinkedList. O inferno está mais próximo do que você imagina! Para passar parâmetros ou receber valores é preciso fazer conversões entre coleções diferentes, copiando os elementos de uma para outra, aumentando ainda mais o problema de performance, além de dificultar a leitura e a manutenção do código.

Nestes casos, se no lugar de Vector tivéssemos usado a interface List, bastaria alterar o local de instanciação da classe, que todo o resto do código teria automaticamente a nova implementação, sem modificações. Uma coleção criada em um componente poderia facilmente ser utilizada por outro, pois tudo o que ele espera é uma implementação de List, e não uma classe concreta.

Portanto, utilize interfaces sempre que puder, principalmente em assinaturas de métodos públicos, e limite ao máximo referências a classes concretas, mesmo internamente na classe.

E que interface usar?

Temos agora pelo menos seis interfaces para escolher: Collection, List, Set, SortedSet, Map e SortedMap. Se acrescentarmos as auxiliares de acesso à coleção, temos ainda a Iterator e a ListIterator. Qual delas usar?

A Collection é a mais genérica, portanto é a mais indicada sempre, certo?

Errado! Por ser tão genérica, suas operações são muito restritas, dificultando sua manipulação. Por exemplo, ela não permite o acesso direto a um elemento, toda a leitura deve ser feita através de seu Iterator. Se a coleção será sempre lida como uma sequência de elementos, e o acesso aleatório (por índice) não faz sentido, isto não é problema. Mas se este tipo de acesso é necessário (ou mesmo conveniente), faz mais sentido usar uma interface List.

Este é um problema sem uma resposta definitiva, pois depende muito de cada caso. Mas posso listar algumas regras básicas, obtidas da minha própria experiência. Não que isso seja grande coisa, mas vale a tentativa. :P


    - A interface Collection normalmente é usada para conjuntos descartáveis, isto é, que vão ser lidos apenas uma vez, e não guardados internamente e manipulados (no máximo copiados para uma outra estrutura).

    - A interface Set serve mais como um marcador da semântica esperada, pois ela não acrescenta nenhuma operação à Collection.

    - As interfaces SortedSet e SortedMap servem para forçar um contrato, de que os elementos da coleção virão ordenados. Aparecem, principalmente, como parâmetros de métodos que esperam por esta ordenação. Porém, na maioria das vezes, as classes TreeSet e TreeMap serão usadas apenas localmente, como containers temporários de ordenação.



Exemplos de uso:


    Loop típico em uma Collection, usando o Iterator:



    Loop típico em um Map, usando o Iterator:



    Usando um iterator para retirar elementos de uma coleção:




    Utilizando um TreeSet para listar o conteúdo de um Map/Properties de maneira ordenada:



    Inicialização de uma Collection:



    Criando e ordenando uma Collection:



    Criando e ordenando uma Collection:



    Intersecção de conjuntos utilizando Set:





:!:


Tetsuo




comentários: 5