Coleções: Como não usar Arrays

Introdução

Depois que se aprender a sintaxe básica de uma linguagem a primeira coisa a aprender a seguir é o conceito de array. A palavra array não tem uma boa tradução para o português já que significa “conjunto de coisas posicionado em linha”. É comum vermos palavras como vector, matrix ou fila como traduções de array, mas nenhuma delas expressa o real significado e pior que isso, são palavras associadas a outros conceitos. Essa associação dupla pode causar graves problemas do entendimento da linguagem java para o iniciante. Por isso não traduzirei essa palavra.

Um array, em java, é um objeto que agrega outros objetos que compartilham um supertipo comum e aos quais nos podemos referir por um índice (ou seja, um numero inteiro). Arrays em java são imutáveis o que significa que para criar um array menor ou maior baseando-nos num que já existe é necessário criar um novo array e fazer uma cópia, elemento a elemento do antigo para o novo.

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



// sem array

public 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

public String getDayOfWeek(int weekDayOrdinal){

return WEEK_DAY_NAMES[weekDayOrdinal-1];

}

Código 1:

Esta é uma situação simples que pode não parecer muito vantajosa ainda para mais quando seria necessário inicializar o array ( embora, essa inicialização seria 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 java oferece um recurso muito mais poderoso que permite ao programador não usar arrays se não quiser : 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 recente (Java 5) 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 é definido 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:

O resultado de invocar equals() para os mesmos dois objetos, sempre retorna o mesmo resultado independentemente de quando essa invocação é feita.
null nunca é igual a nenhum objecto
Um objeto é igual a si próprio. Ou seja, a.equals(a) tem que ser verdade.
A ordem da invocação para dois objetos não importa. Se a.equals(b) é verdade então também tem que ser verdade que b.equals(a)
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. A saber:

equals() é Consistente
e é consistente com null
equals() é Reflexivo
equals() é Simétrico
equals() é Transitivo

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 {

String nome;IDFiscal indentificadorFiscal;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);

}

Código 2:

O uso de instanceof implementa a consistência com null, já que null nunca é instância de um objeto. Ao mesmo tempo, testamos se 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 o objeto 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 reversiveis 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() Object também define o método hashCode() que não é mais que uma função de hash aplicada ao próprio objeto. É facíl 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()

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 vier com fato 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 frequencia 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 {

String nome;IDFiscal indentificadorFiscal;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);

}

public int hashCode(){

return indentificadorFiscal.hashCode();

}

Código 3:

Usamos os mesmos atributos que usámos para identificar se a pessoa era igual e usámos 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 conseqüê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 no dá; ou seja, referencia o objeto da coleção com um indice 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 este mecanismo de referencia e usar qualquer objeto para referenciar qualquer objeto ou invés de apenas indices 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 pilha e todas implementa a interface Queue. Podemos ainda estar interessados em trabalhar não apenas com o primeiro , mas também e/ou com ultimo. Neste caso a coleção são chamadas fila 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” : “Pilha 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 codigos 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 codigo 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 espeficio. 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

 }

Código 4:

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

 }

Código 5

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 subtituido, e a maior parte das vezes deve ser substituido 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 promenorizada é necessária, especialmentequando tratamos com muitos elementos ou com concurrência. Lembre-se também que para que tudo isto funcione os objetos que usa devem sobreescrever equals() e hashCode() corretamente.

Referências

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