Trabalhando com Coleções em Java

Arrays

Arrays são tipos primitivos que agregam vários objetos e os indexam usando um número inteiro.

Arrays são muito uteis para substituir condições de seleção, como vemos no exemplo a seguir:

// sem arraypublic String getDayOfWeek(int weekDayOrdinal){
	switch(weekDayOrdinal){
		case 1: return “Domingo”;
		case 2: return “Segunda-Feira”;
		case 3: return “Terça-Feira”;
		case 4: return “Quarta-Feira”;
		case 5: return “Quinta-Feira”;
		case 6: return “Sexta-Feira”;
		case 7: return “Sábado”;
	}
}

// com array
	private static String[] WEEK_DAY_NAMES = new String[]{
		“Domingo”,
		“Segunda-Feira”,
		“Terça-Feira”,
		“Quarta-Feira”,
		“Quinta-Feira”,
		“Sexta-Feira”,
		“Sábado”
	};

	public String getDayOfWeek(int weekDayOrdinal){
		return WEEK_DAY_NAMES[weekDayOrdinal-1];
	}

Esta é uma situação simples que pode não parecer muito vantajosa ainda para mais quando é necessário inicializar o array ( embora, essa inicialização seja feita apenas uma vez em toda a vida do programa).

O iniciante em Java , sobretudo quem já usou outras linguagens antes, sente-se muitas vezes frustrado ao tentar usar array como usava em outras linguagens e muitas vezes acaba concluindo que Java é uma linguagem mal desenhada. A razão para que o Array seja um objeto pouco maleável é de eficiência. Mas existe um recurso muito mais poderoso que permite ao programador não usar arrays: o Java Collections Framework (JCF).

Java Collections Framework

O Java Collections Framework é um conjunto de interfaces e classes que permitem uma vasta gama de opções na hora de trabalhar com agregações de objetos. A introdução de tipos genéricos e de coleções desenhadas para ambientes concorrentes não devem deixar dúvidas a ninguem, que em Java, usar arrays não é o padrão a seguir.

Os algoritmos existentes relativos a coleções são amplamente divulgados e estudados. A eficiência é a prioridade ao trabalhar com grandes coleções de objetos. Por esse motivo, o JCF é bastante flexível e vasto. Esses algoritmos são tão importantes que obrigam todos os objetos a seguir contratos bem definidos. O primeiro e mais importante deles é o contrato de definição de igualdade.

Definindo igualdade com equals e hashCode

equals()

Em Java o operador de igualdade == não determina se os objetos são iguais, apenas se as variáveis de referencia a eles são iguais. Duas variáveis de referencia a objetos podem referenciar objetos iguais ou não. Para resolver o problema todos os objetos em Java definem o método equals(). Este método é declarado em Object – a classe mãe de todas as classes – e como tal o método é onipresente na linguagem. Por padrão, este método apenas verifica se as referências dos objetos são iguais. Ou seja, por padrão, um objeto só é igual a outro se a variável de referencia é a mesma. Isso garante que objeto quando igual tem as mesma características, mas muitas vezes necessitamos que a igualdade seja determinada pelas características em si e não pela referência do objeto. Para conseguirmos isso basta sobre-escrever o método equals() no nosso objeto. Para fazermos isso temos que seguir algumas regras:

  • Consistencia - O resultado de invocar equals() para os mesmos dois objetos, sempre retorna o mesmo resultado independentemente de quando essa invocação é feita.

  • Consistencia com null - null nunca é igual a nenhum objecto

  • Reflexividade - Um objeto é igual a si próprio. Ou seja, a.equals(a) tem que ser verdade.

  • Simetria - A ordem da invocação para dois objetos não importa. Se a.equals(b) == b.equals(a).

  • Transitividade - Se a.equals(b) e b.equals(c) são verdade então também tem que ser verdade que a.equals(c)

Esta regras traduzem as propriedades do método equals(). Se o método não tem estas propriedades ele não está bem implementado.

Vamos usar estas regras para implementar a classe Pessoa. Uma pessoa tem um nome. Mas existem pessoas com o mesmo nome (pessoas homônimas), logo o nome não é um identificador único para a pessoa. Normalmente a pessoa está inscrita em algum registro nacional de identidade e/ou em algum registro nacional de tributação. Nenhum destes identificadores por si só é único. Embora que raro, é possível que duas pessoas tenham o mesmo identificador e/ou que o identificador se modifique. Veja que baseamos a escolha na análise de uma pessoa real, e usamos isso como modelo para a nossa implementação. Sabemos que escolher um dos identificadores “sociais” não é à prova de bala, mas aqui temos que jogar com as probabilidades. É muito menos comum duas pessoas partilhares o mesmo numero “social” do que o mesmo nome. Escolheremos então o identificador fiscal como base do nosso teste de igualdade. Usaremos também um artifício para simplificar o código. O método que queremos sobrescrever é equals(Object), por isso ele é marcado com @Override. Aqui descobriremos que o objeto passado pode ser uma pessoa. Se sim, usaremos o método equals(Pessoa) para determinar a igualdade.

public class Pessoa {

	private String nome;
	private IDFiscal indentificadorFiscal;
	private IDRegistro registro;

	@Override
	public boolean equals(Object other){
		return other instanceof Pessoa && equals((Pessoa)other);
	}

	public boolean equals (Pessoa other){
		return this.indentificadorFiscal.equals(other.indentificadorFiscal)
			&& this.registro.equals(other.registro);
	}
}

O uso de instanceof implementa a consistência com null, já que null nunca é instância de um objeto. Ao mesmo tempo, testamos se o objeto é uma pessoa. Entenda que, se não é uma pessoa, automaticamente não é igual a uma pessoa. Depois, testamos a igualdade da pessoa com outra pessoa. Elas são iguais se os seus identificadores sociais são iguais. Note que usamos o método equals() desses outros objetos para testar a igualdade. Isto é normal e exime a classe Pessoa de saber como comparar objetos de outros tipos (Separação de Responsabilidade).

hashCode()

Hash é um código desenvolvido em criptografia. Função de Hash é um mecanismo que baseado numa entrada produz um código de hash (hashCode). Funções de Hash não são reversíveis e sempre produzem o mesmo resultado para a mesma entrada. Contudo não são obrigadas a produzirem códigos diferentes para entradas diferentes ( ou seja, não são injetivas). Por outro lado, funções de hash produzem códigos do mesmo tamanho para entradas de tamanhos aleatoriamente diferentes. Estas propriedades são extremamente uteis já que pela simples comparação do código de hash poderemos saber se dois objetos são diferentes. Atenção para o fato que elas não revelam se os objetos são iguais, mas na maioria dos casos ser diferente é mais importante que ser igual.

Sabendo disto, à semelhança de equals() a classe Object também define o método hashCode() que não é mais que uma função de hash aplicada ao próprio objeto. É fácil de compreender que se alteramos o mecanismo padrão de verificação de igualdade, temos também que alterar o mecanismo padrão de produção do código de hash. Isso nos leva à regra de consistência que diz que:

>> Sempre que sobrescrever equals() sobrescreva também hashCode() de forma compatível.

De forma compatível significa que:

>> Se a.equals(b) é verdade então também é verdade que a.hashCode() == b.hashcode()

Objetos iguais têm o mesmo hashCode. Mas objetos com o mesmo hashCode não são necessariamente iguais.

Existem muitas formas de redefinir o calculo do código de hash. Da mais simples e com pior performance que é fazer todos os objetos terem o mesmo código até à mais complexa de deixar todos os objetos terem um código diferente. Embora seja teoricamente possível ter uma função de hash tão eficiente que produz um código diferente para cada objeto diferente, na prática nos encontramos limitados já que o código tem que caber num int (32 bits). Então temos que viver com fato de que nossas funções de hash vão produzir código iguais em algum ponto. A isso se chama Colisão de Hash. O objetivo é diminuir as colisões, ou seja diminuir a frequência com que dois objetos diferentes produzem o mesmo código de hash. Quanto menos colisões, mais eficiente é a nossa função de hash. A função de hash mais simples é a operação de ou-exclusivo (XOR) que em Java se representa pelo operador ^.

Vejamos como ficaria a implementação da função de hash para o nosso objeto Pessoa.

public class Pessoa {

	private String nome;
	private IDFiscal indentificadorFiscal;
	private IDRegistro registro;

	@Override
	public boolean equals(Object other){
		return other instanceof Pessoa && equals((Pessoa)other);
	}

	public boolean equals (Pessoa other){
		return this.indentificadorFiscal.equals(other.indentificadorFiscal)
			&& this.registro.equals(other.registro);
	}

	@Override
	public int hashCode(){
		return indentificadorFiscal.hashCode() ^ this.registro.hashCode();
	}
}

Usamos os mesmos atributos que usamos para identificar se a pessoa era igual e usamos suas funções de hash para criar o hash de Pessoa. Desta forma, se os identificadores são os mesmos também os seus hashCodes serão o mesmo, e por consequência os hashCode de Pessoa será o mesmo.

É de extrema importância entender a necessidade de sobrescrever estes métodos. São eles que definem se dois objetos são iguais. E a igualdade é uma característica importantíssima para qualquer tipo de objeto já que dá ao objeto a sua identidade. Com base na identidade do objeto o JCF pode ser mais eficaz e dar-lhe as ferramentas que você necessita sem nenhum esforço da sua parte.

Coleções e Mapas

Ao colocar os objetos dentro de uma conjunto esperamos poder fazer alguma coisa com esses objetos. A primeira coisa que podemos pensar em fazer com uma coleção é obter a mesma funcionalidade que o array nos dá, ou seja,referenciar o objeto da coleção com um índice numérico. O JCF chama a objetos de coleção que implementam essa característica de listas e todos implementam a interface List.

Podemos sofisticar o mecanismo de referencia e usar qualquer objeto para referenciar qualquer objeto ou invés de apenas índices numéricos. Objetos que implementam este mecanismo são chamados de _mapas_ e implementam a interface `Map`.

Poderemos estar apenas interessados em formar um conjunto em que os elementos não se repetem e em que não os precisamos referenciar de nenhuma forma. Este é o tipo de coleção mais simples que chamados de conjunto e implementa a interface Set.

Por outro lado podemos estar interessados em trabalhar especialmente com o primeiro elemento da coleção. A este tipo de coleção chamamos fila e todas implementa a interface Queue.

Podemos ainda estar interessados em trabalhar não apenas com o primeiro , mas também e/ou com último. Neste caso a coleção são chamadas pilha e todas implementam Deque.

As interfaces `List`, `Queue` e `Set` são subclasses da interface `Collection`.	 A interface `Deque` é uma subinterface de `Queque` ( o nome é a abreviação da expresão inglesa “Double ended Queue” : “Fila de duas pontas”).

Ordenação, busca e iteração

Busca e iteração são as operações básica que podemos fazer com qualquer coleção. Iteração é uma operação tão importante que o JCF incorpora o padrão de projeto Iterator. Iterator é um objeto responsável por iterar os objetos contidos na coleção numa certa ordem. Essa ordem depende da ordem intrínseca à coleção; ou seja, ele percorre os elementos da coleção na mesma ordem em que eles se encontram dentro dela. A iteração é tão importante que a partir da versão 5 do Java foi incluída da interface Iterable para marcar qualquer objeto capaz de produzir um iterador. E com isso uma nova sintaxe para o velho for : o for-each. Arrays comuns também foram capacitados com esta interface o que torna a iteração num array tão simples quanto a de numa coleção.

Buscar o elemento num coleção parece uma operação simples, mas não é. Quando a coleção tem muitos elementos é vital que seja incorporada uma forma de retorna os elementos o mais rapidamente possível ( em menos operação possível). Isso leva as implementações das coleções a adotarem metodologia especiais para ordenar internamente seus elementos. As lista estão incapacitadas deste tipo de funcionalidade avançada uma vez que a ordem de uma lista é sempre a da inserção dos elementos. Isso significa que encontrar um elemento na lista corresponde basicamente a iterar a lista e comparar cada elemento. Os conjuntos são mais rápidos neste mecanismo porque usam os códigos de hash para comparar os elementos ou usam um algoritmo baseado na ordem natural dos elementos. A mesma filosofia é seguida pelos mapas. As filas e pilhas tem uma funcionalidade especial para a busca do primeiro e/ou ultimo elemento, sendo mais rápidas a encontrar estes elementos. Normalmente não nos interessa a ordem interna deste tipo de coleção, apenas quem é o primeiro e o ultimo e como tal a otimização é feita para encontrar estes elementos mais depressa.

A ordenação dos elementos dentro da coleção pode ser ditada basicamente de três forma: ordem de inserção, ordem natural ou aleatória. A ordem se inserção segue a ordem pela qual os elementos foram adicionados na coleção. O ultimo elemento a ser adicionado está no fim da lista e será o ultimo a ser retornado pelo iterador. As listas, filas e pilhas são baseadas neste conceito de ordenação. A ordem aleatória é a uma forma da coleção se excusar de manter uma ordem , não fazendo nenhuma garantia sobre uma ordem predeterminada. Isso permite à coleção implementar algoritmos mais eficientes na hora de procurar pelos elementos contidos nelas. Normalmente este tipo de implementação é baseado no código de hash e é usada principalmente por conjuntos e mapas. A ordem natural também é principalmente usada por conjuntos e mapas em particular aos que implementa as interfaces SortedSet e SortedMap respectivamente, cujas implementações se baseiam na ordem especifica dos objetos que são seus elementos. Por exemplo os números, as datas e as palavras tem uma ordem natural. Os números vão de -infinito a +infinito ,as datas tem ordem cronológica e as palavras são ordenadas conforme o alfabeto. Outros objetos podem implementa uma ordem natural para dizer ao Java o mesmo que números e strings dizem: Hei! nós somos ordenados! A ordem natural é implementada por um objeto implementado a interface Comparable se o objeto só tem uma ordem possível. Como é o caso de números, strings e datas. Se o objeto tem mais do que uma ordem possível existem implementações de Comparator. Este tipo de objeto tem a responsabilidade de saber a ordem do tipo de objeto conforme algum critério especifico. Por exemplo, Pessoa é um objeto que pode ser ordenado pelo nome ou pela idade, ou por ambos. Para caso especifico em que a coleção tem uma ordem natural pode ser necessário procurar elementos pela relação de grandeza. Ou seja, não procurar o elemento que é igual a certo elemento, mas o elemento que é maior ou menor. Neste caso dizemos que coleção é navegável e ela deve implementar NavigatableSet ou NavigatableMap dependendo do seu super tipo.

Iteração e RandomAccess

A iteração sobre uma coleção é feita por meio do iterador. Essa iteração pode ser explicita ou implícita graças à nova sintaxe for introduzida no Java 5.

// explicita
for (Iterator it = lista.iterator();it.hasNext();){
	Object obj = it.next();
	// faz algo com obj
}

// implicita
for (Object obj : list ){
	// faz algo com obj
}

Embora o objetivo do JCF é substituir o uso de arrays por objetos muito mais inteligentes e uteis não podemos negar que iterar um array é muito mais rápido do que iterar uma coleção. A JCF resolve isto com a interface RandomAccess. Todas as listas em que a iteração usando o método get(i) seja mais rápida que o uso do iterador implementam a interface marcadora RandomAccess. Um exemplo de uma lista que implementa esta interface é ArrayList que como o nome sugere é apenas uma cápsula à volta de um array.

// usando get(i)
for (int i=0; i < list.size();i++){
	Object obj = list.get(i);
	// faz algo com obj
}

// com iterador
for (Object obj : list ){
	// faz algo com obj
}

Concorrência

A operação mais comum sobre uma coleção é a iteração. Mas o que acontece quando estamos iterando e alguém altera a coleção adicionando ou removendo um elemento. Com certeza isso é inesperado e leva a exceções ( em particular a ConcurrentModificationException) Por outro lado, o que acontece quando se tenta adicionar ou remover dois elemento simultaneamente ? Algumas implementações das coleções levam isto em consideração e possuem características especiais para lidar com estes problemas. Algumas , em particular as que implementa ,BlockingQueue são especificamente desenhadas para trabalhar nestas condições e mais do que isso, o próprio sincronismo faz parte do sua funcionalidade.

Hierarquia de Coleções

Como vimos as capacidades especificas de cada implementação de uma coleção depende de fatores como a ordem, a eficiência de busca e capacidade de funcionarem em ambientes concorrentes. A combinações destes fatores dá origem a um conjunto vasto de implementações possíveis , cada uma baseada num algoritmo diferente que tira o máximo de partido da determinação da identidade dos objetos incluídos na coleção.

Ilustração 1: Hierarquia de tipos de coleções em Java

Escolhendo a sua Coleção

Escolher qual implementação usar nem sempre é uma tarefa simples. É necessário conhecer muito bem o uso que será feito da coleção. Ela será usada mais para inserir ou para iterar ? Tem que haver mapeamento ou não ? É realmente necessário associar um índice a cada elemento ? Tem que ser sincronizada ? Os elementos que serão contidos nela têm uma ordem natural ? Responder a estas perguntas é essencial para saber que interface de coleção e que implementação escolher. O diagrama a seguir pode ajudá-lo a escolher a interface mais apropriada para as assinaturas e a implementação mais apropriada compatível com ela.

Ilustração 2: Diagrama de escolha de coleções em Java

É possível que durante o desenvolvimento da sua aplicação as suas necessidade mudem. Por isso é sempre conveniente nunca declarar as classes de implementação em assinaturas de métodos e sempre usar a interface mais genérica possível dentro do algoritmo que se deseja implementar.

Resumo

O uso de arrays pode ser substituído, e a maior parte das vezes deve ser substituído pelo uso de alguma dos tipos de coleção disponíveis no Java Collections Framework.A sua vida será muito simplificada se o fizer e sempre terá um ganho de performance relativamente a arrays. Claro que, esta tarefa não é simples e cada caso é um caso. Para o dia-a-dia ArrayList e HashSet e HashMap cobrem 90% das necessidades, mas ha casos em que uma analise pormenorizada é necessária, especialmente quando tratamos com muitos elementos ou com concorrência. Lembre-se também que para que tudo isto funcione os objetos que usa devem sobrescrever equals e hashCode corretamente.

Bibliografia

[1] The Collections Framework, Sun Microsystems, Inc. (http://java.sun.com/javase/6/docs/technotes/guides/collections/index.html)

[2] The Collections Framework API Reference, Sun Microsystems, Inc. (http://java.sun.com/javase/6/docs/technotes/guides/collections/reference.html)

Scroll to Top