Uma visão sobre o Framework Collections do Java
Uma atividade bastante comum ao programarmos é agrupar uma série de objetos para trabalharmos com eles como se fossem um única unidade. Uma coleção é utilizada para armazenar, recuperar, percorrer e outras manipulações de dados. Normalmente uma coleção armazena dados que formam um grupo natural normalmente do mesmo tipo como Clientes, Veículos, Contas ou outros objetos mais abstratos. Se você já trabalhou um pouco Java já utilizou uma de suas classes a ArrayList com certeza.
O Framework Collections é composto de uma série de interfaces e classes concretas organizadas em uma determinada arquitetura e estão disponibilizadas no pacote java.util. As interfaces representam estruturas de dados clássicas como Listas(List), Filas(Queue) e Mapas(Map) por exemplo e as classes concretas as implementações destas estruturas como a classe ArrayList que é uma implementação de uma Lista utilizando array e a classe LinkedList que é uma implementação de uma Lista utilizando uma lista ligada.
Começamos vendo as interfaces
Collection<E>
Esta é a interface raiz do framework, embora não seja fornecida implementações diretas a esta interface ela serve de denominador comum para as implementações de coleções(exceto Map), fornecendo o máximo de generalização possível já que as coleções podem conter vários tipos de restrições, como por exemplo não aceitarem objetos repetidos, ou manterem os objetos em uma determinada ordem.
Segue algumas das operações fornecidas pela interface Colletion e consequentemente presentes nas classes concretas:
- add( E e ): Adiciona o objeto passado por parâmetro a coleção.
- addAll( Collection<? extends E> c): Adiciona todos os elementos da coleção passada por parâmetro a na coleção que chamou o método.
- remove(Object o ): Remove o objeto passado por parâmetro da coleção.
- removeAll(Collection<?> c): Remove todos os elemento da coleção passada por parâmetro da coleção que chamou o método.
- contains(Object o): Retorna true se o objeto passado por parâmetro estiver dentro da coleção, senão retorna false.
- isEmpty(): Retorna true se a coleção não tiver nenhum objeto dentro dela.
- size(): Retorna o número de objetos da coleção.
- clear(): Remove todos os objetos de dentro da coleção.
- toArray(): Retorna um array contendo todos os objetos da coleção.
- toArray(T[] a): Retorna um array contendo todos os objetos da coleção. Se os objetos da coleção couberem no array passado por parâmetro este será retornado, senão um novo array será criado e retornado.
- iterator(): Retorna um objeto Iterator utilizado para percorrer os objetos da coleção. Este método é especificado na interface Iterable a qual Collection estende.
List<E> – Listas
Em um conjunto do tipo List, os objetos são organizados um após o outro em sequência, temos o 1º objeto, o 2º, 3º, etc. Como em um array há uma ordem bem defina no armazenamento(sendo uma coleção ordenada), mas com a vantagem de não ter um tamanho fixo. Como em um array esta coleção dá muita importância ao índice ou seja a posição que ele ocupa na coleção, fornecendo vários métodos relacionados a ele.
- get(int index): Retorna o objeto armazenado na posição informada pelo parâmetro passado.
- indexOf(E e): Retorna um int para a posição da primeira vez que o objeto passado por parâmetro aparece na coleção. Ele retornará -1 se o objeto não for encontrado.
- add(E e): Insere o objeto passado por parâmetro no final da lista.
- add(int index , E e): Insere um o objeto passado e na posição index da lista.
- remove(int index): Remove o objeto que está na posição index.
Set<E> – Conjuntos
A interface Set não permite objetos duplicados dentro dela. Uma classe que implemente Set irá utilizar o método equals para determinar se um objeto que estamos tentando inserir já está presente na coleção ou não, sendo assim importante implementar corretamente o método equals na classe que vamos inserir na coleção. Veremos mais sobre o método equals mais adiante.
A interface Set não adiciona mais métodos aos já definidos na interface Collection.
Map<k,v> – Mapa
A interface Map não estende Collection. Ela prove um armazenamento no formato chave/valor, ou seja, uma chave exclusiva(o identificador) é “mapeada” ou melhor é associada a um valor especifico dentro da coleção sendo tanto a chave e o valor objetos. Se desejar utilizar valores primitivos como chave ou valor ele deve ser colocado dentro de uma classe Wrap. Um Map utiliza o método equals para determinar se uma chave é igual a outra.
- put(K key, V value): Adiciona um objeto value dentro da coleção associado a chave
keya ele. - get(Object key): Retorna o objeto da coleção que esta associado ao objeto
keypassado por parâmetro. Se não houver nenhum objeto na coleção associado akeyserá retornadonull. - containsKey(Object key): Retorna true se a chave
keypassada por parâmetro existe na coleção, senão retornafalse. - containsValue(Object value): Retorna true se o objeto
valuepassado por parâmetro existe na coleção, senão retorna false. - remove(Object key): Remove da coleção o objeto que está associado a chave
keypassada por parâmetro. - keySet(): Retorna um objeto do tipo
Setcontendo todas as chaves do Mapa. - values(): Retorna um objeto
Collectioncom todos os valores dos Mapa.
Queue<E> – Fila
A Queue prove uma lista de “coisas a fazer”, ou lista de elementos a serem processados de alguma forma. Normalmente uma Queue é considerada FIFO(first in, first out – primeiro item a entrar é o primeiro a sair) como uma fila de banco, quem chega primeiro é atendido primeiro.
Além das operações básica de Collection, Queue fornece métodos para acrescentar e subtrair objetos da fila, estes métodos existem em duas formas, um que lança uma exceção se a operação falhar e outro que retorna um valor especial(null ou false).
- add(E e): Adiciona o objeto passado por parâmetro a fila, lembrando que ele será posicionado no final da fila. Se não houver mais espaço irá lançar uma exceção
IllegalStateException - offer(E e): Adiciona o objeto passado por parâmetro ao final da fila. Retorna true se for inserido sem erro(havia espaço na fila) e false se não havia.
- remove(): Remove o primeiro objeto da fila retornando ele. Lança a exceção
NoSuchElementExceptionse a fila estiver vazia. - poll(): Remove o primeiro objeto da fila retornando ele. Retorna
nullse a fila estiver vazia. - element(): Retorna o primeiro objeto da fila sem removê-lo. Lança a exceção
NoSuchElementExceptionse a fila estiver vazia. - peek(): Retorna o primeiro objeto da fila sem removê-lo. Retorna null se a fila estiver vazia.
Classes Concretas
Antes de vermos as classes de implementação propriamente dita vamos ver dois métodos que são muito importantes para várias delas funcionarem apropriadamente, os métodos equals e hashCode.
equals
O método equals é herdado de Object e é utilizado para saber se dois objetos são significativamente equivalentes, ou seja se os valores de duas instâncias de uma classe possuem os mesmos valores o que não seria possível fazer com o operador "==" que compara apenas as referências dos objetos e não os valores armazenados nelas.
Em alguns casos queremos que cada instância seja considerada um objeto diferente, mas em outros casos podemos não querer isso, podemos consideramos que se dois objetos possuem os mesmos valores para certos atributos então são objetos iguais, como se dois objetos clientes tem o mesmo número de CPF significa que dentro de nosso sistema são os mesmo objeto apenas estão em lugares diferentes na memória.
O método equals é muito importante para o Framework Collection já que ele é utilizado nas classes que implementam Set para avaliar se o objeto já está na coleção, e nas classes Map para comparar as chaves. Por estes motivos devemos sobrescrever corretamente este método que possui um contrato pré-estabelecido.
- É reflexivo: Para qualquer valor de referência x,
x.equals(x)deve retornar true - É simétrico: Para qualquer valor de referência x e y,
x.equals(y)deve retornar true se, e somente se,y.equals(x) - É transitivo: Para qualquer valor de referência x, y, e z,
x.equals(y)deve retornar true e y.equals(z) deve retornar true, então,x.equals(z)também deve retornar true - É consistente: Para múltiplas chamadas de
x.equals(y)deve retornar sempre true ou false se não forem alterados os objetos x e y
Abaixo sobrescrevemos equals de uma maneira aceitável.
public class Cliente {
private String cpf;
private String nome;
...
@Override
public boolean equals(Object obj) {
if (this == obj){
// se são a mesma referência são iguais
return true;
}
if (obj == null){
// se é nulo não é um objeto então não pode ser igual
return false;
}
if ( ! (obj instanceof Cliente) ){
// se não é uma instancia de Cliente não pode ser igual
return false;
}
Cliente other = (Cliente) obj;
if ( cpf.equals(other.cpf) && nome.equals(other.getNome() ) ){
// se o cpf eo nome dos dois objetos forem iguais então os objetos são iguais
return true;
}else{
return false;
}
}
...
}
hashCode
Além de equals também herdamos hashCode de Object e ele é utilizado por algumas classes do Framework Collection para melhorar o desempenho em grandes conjuntos de dados(seja esperto e descubra quais classes). Ele deve retornar um número que podemos considerar como um código de localização do objeto que será utilizado para facilitar a localização deste objeto dentro da coleção.
Por exemplo se temos que armazenar fichas de alunos de uma grande escola, colocá-las todas dentro do mesmo arquivo poderia resolver, mas quando tivermos que buscar a ficha de um aluno vamos ter que buscar em milhares de fichas qual é a que queremos, contudo se pegarmos as fichas e dividirmos em diversos arquivos colocando as fichas nos arquivos de acordo com alguma informação da ficha, como por exemplo ano de nascimento. Agora quando quisermos pegar a ficha do joãozinho que nasceu em 1984 basta ir no arquivo “1984” e procurar a ficha do joãozinho em uma quantidade muito menor de fichas do que se estivessem todas juntas. Você pode perguntar, mas não seria melhor arquivar por letra, até poderia mas lembre-se que os arquivos k,y,z estariam quase vazios e outros como o a, m, r estariam bem cheios, não fornecendo uma boa distribuição.
Vejamos o contrato de hashCode:
- Se dois objetos forem iguais segundo
equalsdevem retornar o mesmohashCode - Múltiplas chamadas os método
hashCodede um objeto devem retornar sempre o mesmo inteiro, contando que nenhuma informação utilizada emequalsseja alterada - Dois objetos diferentes podem retornar o mesmo
hashCode
Veja um exemplo
public class Cliente {
private String cpf;
private String nome;
...
@Override
public int hashCode() {
int hashCpf = (cpf == null) ? 0 : cpf.hashCode() ;
int hashNome = (nome == null) ? 0 : nome.hashCode();
int result = hashCpf + hashNome ;
return result;
}
...
}
Listas – ArrayList e LinkedList
Basicamente a diferença entre as classes ArrayList e LinkedList é a forma que as duas são armazenam seus itens.
ArrayList
Um ArrayList armazena seus itens com um array que é iniciado com um determinado tamanho, ao ser inserido um elemento ele verifica se é necessário aumentar o array, se sim ele cria um novo array e copia todos os objetos do antigo para o novo(e maior) e descarta o antigo.
Vamos ver o uso de um ArrayList
// criando um arraylist que só irá aceitar String
ArrayList<String> c = new ArrayList<String>();
c.add("Rodrigo"); //adicionando ao final da lista, posição 0
c.add("Maria"); //adicionando ao final da lista, posição 1
c.add("Thiago"); //adicionando ao final da lista, posição 2
c.add("João"); //adicionando ao final da lista, posição 3
//pegando o a quantidade de objetos - saída: Tamanho: 4
System.out.println("Tamanho: " + c.size() );
//pegando um objeto especifico - saída: A string na posição 2: Thiago
System.out.println("A string na posição 2: " + c.get(2) );
//pegando a posição de um determinado objeto - saída: A posição da String 'Maria': 1
System.out.println("A posição da String 'Maria': " + c.indexOf("Maria") );
//removendo a String na posição 1, ou seja "Maria"
c.remove( 1 );
System.out.println("============================");
//percorrendo através de um iterator(objeto responsável por percorrer uma coleção)
Iterator<String> i = c.iterator();// pegando o iterator da coleção
while( i.hasNext() ){//enquanto tiver um próximo objeto na coleção
//retorna o próximo elemento da coleção e incrementa o contador interno do itarator
String nome = i.next();
System.out.println( nome );
}
System.out.println("============================");
// adicionando na posição 1 a String "Mario", sendo que a o objeto que está na
// posição 1 passa para a posição 2, o objeto na posição 2 para 3 e assim por diante
c.add(1, "Mario");
//percorrendo a lista através de um "for aprimorado"
//para cada objeto presente na lista "c" o objeto será coloca em "nome" e executará o bloco
for(String nome : c){
System.out.println( nome );
}
System.out.println("============================");
//criando um array com o mesmo tamanho dos objetos da coleção
String[] nomes = new String[ c.size() ];
//colocando os objetos da coleção dentro do array passado por parâmetro
c.toArray( nomes );
//percorrendo o array
for(int j = 0 ; j < nomes.length ; j++){
System.out.println(nomes[j]);
}
LinkedList
A LinkedList utiliza uma abordagem diferente para armazenar os seus objetos. Ela utiliza uma lista duplamente ligada onde cada um dos elementos adicionado é colocado dentro de outro objeto(Nó), que além de conter o valor armazenado tem uma referência ao próximo Nó e ao anterior. Com isso cada Nó pode ser colocado em qualquer lugar da memória e não somente um após ao outro como na implementação de ArrayList o que causa perda de desempenho ao ter que aumentar o array ou mover muitos objetos para inserir um valor no meio da lista por exemplo.
Em uma LinkedList para inserir no inicio da lista ou no meio não é necessário mover todos os objetos da memória uma posição para frente, basta alterar as referências ao próximo Nó e ao anterior, tornando as operações de inserção e remoção mais eficientes principalmente no inicio e no final.
A classe LinkedList fornece alguns métodos além dos da interface List em especial para inserir no inicio da lista e no final.
- addFirst(E e): Insere o objeto e no inicio da lista.
- addLast(E e): Insere o objeto e no final da lista.
- getFirst(): Retorna o primeiro objeto da lista.
- getLast(): Retorna o último objeto da lista.
- removeFirst(): Remove e retorna o primeiro objeta da lista.
- removeLast(): Remove e retorna o último objeto da lista.
A classe LinkedList também implementa a interface Queue sendo assim possível trabalhar com ela como se fosse uma fila.
LinkedList<String> queue = new LinkedList<String>();
queue.offer("Rodrigo");
queue.offer("Luiz");
queue.offer("Maria");
queue.offer("Fernando");
System.out.println(queue);
//saida: [Rodrigo, Luiz, Maria, Fernando]
System.out.println(queue.poll());//Rodrigo
System.out.println(queue.poll());//Luiz
System.out.println(queue.poll());//Maria
System.out.println(queue.poll());//Fernando
HashSet – LinkedHashSet
HashSet e LinkedHashSet são classes que implementam Set ou seja fornecem uma estrutura para armazenar objetos sem repetição.
A classe HashSet utiliza internamente uma outra coleção(a classe HashMap) para armazenar e fornecer a garantia de seus objeto não se repetirem.
HashSet<String> set = new HashSet<String>();
boolean[] inseriu = new boolean[4];
inseriu[0] = set.add("Rodrigo"); //adicionando "Rodrigo"
inseriu[1] = set.add("Carlos"); //adicionando "Carlos"
inseriu[2] = set.add("Maria"); //adicionando "Maria""
inseriu[3] = set.add("Rodrigo"); // Não será adicionado "Rodrigo" pois já existe na coleção
//a saida deste laço será true, true, true, false mostrando que o último add não foi funcionou
for(int i = 0 ; i < inseriu.length ; i++){
System.out.println( inseriu[i] );
}
//percorrendo o conjunto com o "for aprimorado"
for(String nome : set){
System.out.println(nome);
}
//saída foi Maria, Carlos, Rodrigo
Como você notou a saída ao percorrer a HashSet não foi a mesma que foi inserida, sendo que a inserção do último “Rodrigo” falhou. O que acontece é que a coleção HashSet não garante a ordem de inserção, podendo embaralhar os objetos quando for percorrida.
Já a classe LinkedHashSet é muito semelhante a HashSet sendo a única diferença que ela utiliza uma lista duplamente encadeada para garantir que ao ser percorrida a ordem de inserção dos elementos será respeitada. Para fazer um teste apenas mude a linha 1 do exemplo acima para LinkedHashSet set = new LinkedHashSet(); e observe a saída.
HashTable , HashMap e LinkedHashMap
As classes HashTable, HashMap e LinkedHashMap são classes que implementam a interface Map fornecendo assim armazenamento de objeto no formato chave/valor com diferenças sutis entre as implementações. E devemos lembrar que os objetos para serem utilizados com estas classes devem respeitar os contratos de equals e hashCode.
- HashTable: É uma implementação onde seus métodos são
synchronizedou seja são protegidos para manipulação concorrentes(múltiplas threads). É uma classe antiga e não é recomendada para ser utilizada, a não ser onde operações thread-safe sejam necessárias. - HashMap: É uma implementação ao contrário de
HashTablenão é thread-safe e não preserva a ordem do objetos inseridos. É a classe mais utilizada quando queremos umMap - LinkedHashMap: É uma implementação de
Mapque preservar a ordem em que os elementos foram inseridos na coleção, para isso ela utiliza uma lista duplamente encadeada.
// criando uma coleção HashMap, onde as chaves são objetos do tipo
// String e os valores são do tipo Integer
HashMap<String, Integer> numeros = new HashMap<String, Integer>();
// inserindo um valor na coleção, a chae será o objeto "um" e
// o valor associado será 1 que sofrerá "auto-boxing" em uma classe Integer
numeros.put("um", 1);
numeros.put("dois", 2);
numeros.put("três", 3);
// retornamos o valor que está associado a chave "três" e mostramos
System.out.println( numeros.get("três") );
// pegamos todas as chaves dos objetos da coleção e retornamos como
// uma coleção do tipo Set
Set<String> keys = numeros.keySet();
//iteramos pela coleção de chaves para mostrar cada elemento da coleção
// hashMap, já que ela não implementa a interface Iterable que marca e
// fornece métodos para podermos percorrer uma coleção com um for aprimorado
for(String key : keys){
System.out.println(key +" - "+ numeros.get( key ) );
}
SortedSet/TreeSet e SortedMap/TreeMap
As interfaces SortedSet e SortedMap são interface que representam coleções que são ordenadas, do menor para o maior, na SortedSet os objetos em si e na SortedMap os objetos chave. Mas como poderemos determinar a ordem de classes como Cliente e Carro que contém vários atributos, como determinar por qual deles será feita a ordenação. O modo mais simples é fazer essas nossas classes implementarem a interface Comparable que obrigará ao objeto ter o método compareTo(T o) para a coleção conseguir comparar um objeto com outro. Se esta interface não for implementada, as classes TreeSete TreeMap irão lançar a exceção java.lang.ClassCastException, pois internamente elas fazem cast para Comparable. Também é possível passar um objeto que estenda Comparator para a coleção para possibilitar a comparação.
int compareTo(T o): Este método de retorna um inteiro negativo se o objeto que chamou o método é menor que o objeto passado por parâmetro. Deve retornar zero se os dois objetos forem iguais, e deve retornar um inteiro positivo se for maior.
Classes como String, Integer, Double, etc, já implementam a interface Comparable.
public class Cliente implements Comparable<Cliente>{
private int nInscricao;
private String cpf;
private String nome;
public int compareTo(Cliente o) {
if( this.nInscricao == o.getnInscricao() ){
//se o objeto passado tem a mesma inscrição retorna 0 pois os dois objetos são iguais
return 0;
}else{
if( this.nInscricao < o.getnInscricao() ){
//se o obj. passado é menor retorna do que o obj. que chamou o método retorna um int negativo
return -1;
}else{
//se o obj. passado é menor retorna do que o obj. que chamou o método retorna um int negativo
return 1;
}
}
}
...
}
As classes TreeSet e TreeMap implementam um algoritmo de árvore de busca binária balanceada, que como o nome diz organiza os dados dentro delas como uma árvore visando deixar as informações ordenadas dentro da estrutura para otimizar a busca de valores. Os valores ficam armazenados de uma forma parecida com a abaixo.
//=============== TreeSet ===============
TreeSet<Cliente> treeSet = new TreeSet<Cliente>();
treeSet.add( new Cliente(3 , "Rodrigo") );
treeSet.add( new Cliente(1 , "Maria") );
treeSet.add( new Cliente(2 , "Fernando") );
treeSet.add( new Cliente(4 , "Fernando") );
for(Cliente cliente : treeSet){
System.out.println(cliente.getnInscricao() + " - "+cliente.getNome() );
}
//saida
//1 - Maria
//2 - Fernando
//3 - Rodrigo
//4 - Fernando
//=============== TreeMap ===============
TreeMap<String , Cliente > treeMap = new TreeMap<String , Cliente>();
treeMap.put("Um" , new Cliente(3 , "Rodrigo") );
treeMap.put("Dois" , new Cliente(1 , "Maria") );
treeMap.put("Três", new Cliente(2 , "Fernando") );
System.out.println( treeMap );
//saida(chave/valor): {Dois=1 - Maria, Três=2 - Fernando, Um=3 - Rodrigo}
Bom era isso, lembrando que é uma visão superficial não muito detalhada, mais para “ouvir falar” sendo interessante estudar Estruturas de Dados para entender realmente como o Framework Collections funciona.
Para maiores detalhes das classes apresentadas de uma olhada na documentação da API do Java todas as classes do Framework Collections estão no pacote java.util