Ensinando o que é o hashCode

Sem dúvida um dos pontos mais difíceis para quem está fazendo um curso inicial de java é entender hashCode, em especial para quem nunca viu estruturas de dados além de filas e pilhas, isso porque o desenvolvedor já está bem confuso em ter seu primeiro contato com a API das coleções, sintaxe do generics e uso extensivo de interfaces.

Aqui vou mostrar como costumo fazer essa explicação, e depois sugerir uma grande melhoria.

Costumo usar o exemplo de pesquisar por uma String dentro de uma lista de Strings. A busca seqüencial vai fazer até lista.size() comparações, o que pode ser muito grande. Então como diminuir esse número de comparações? Espalhando nossas Strings de acordo com algum critério, e colocando-as dentro de uma tabela de espalhamento (hashtable, hash=espalhar).

Mas como espalhá-las? Podemos classificar essas Strings de acordo com a sua primeira letra em uma array de listas (List<String>[]): strings[65] teria uma lista de Strings que começam com a letra A, e assim por diante. O problema é que, por exemplo, podemos ter todas nossas strings começando com A gerando a quantidade máxima de colisões em uma mesma lista! Daqui podemos elaborar a idéia para que as Strings sejam indexadas por um critério mais interessante. Por exemplo, multiplicar o valor inteiro de cada char: paulo valeria p*a*u*l*o, que é 112*97*117*108*111 = -1942066240 (explodiu Integer.MAX_VALUE). Esse número pode ser muito grande ou não nos servir por algum motivo, então nosso HashMap vai limitar o tamanho da array, e fazer algo como -1942066240 % array.length para saber em que bucket colocar esse ítem.

E continuo nessa linha de pensamento para explicar o contrato do método hashCode, realocação do tamanho da tabela de espalhamento e que isso tudo é utilizado na implementação de arrays associativas em algumas linguagens.

Os principais problemas desse exemplo:

  • Alguns desenvolvedores conhecem um pouco de árvores binárias, e querem usá-las. O problema é que tabelas de espalhamento são muito mais rápidas na pesquisa, além de que usar árvores binárias necessita de um critério de comparação entre os objetos, o que não é necessário em espalhamentos;
  • Gerar um int a partir de uma String atrapalha bastante. Repare a quantidade de passos que precisei passar: transformação de cada char em seu valor numérico da tabela unicode, multiplicar tudo, fazer mod, etc. Seria melhor se o objeto em questão já tivesse alguma relação numérica, e que não precisássemos fazer contas em cima de seus valores;
  • Pessoalmente sinto que poderia ser melhor.

Um amigo analista que trabalha no asset management de um grande banco brasileiro conversava comigo quando surgiu a necessidade dele encontrar dois arquivos de conteúdo idêntico que estavam no mesmo diretório. O problema é que esse diretório tem mais de 10 mil arquivos! Ele mesmo sugeriu fazer uma comparação primeiramente ordenando os arquivos por tamanho, e só vale comparar byte a byte os arquivos que possuírem o mesmo tamanho, os outros obviamente são diferentes entre si. Disse então para ele que esse era um excelente exemplo de tabelas de espalhamento, e que ele não precisaria nem mesmo ordenar os arquivos por tamanho, bastando separá-los!

Repare que esse meu amigo não é programador, mas todo engenheiro e administrador que trabalha em banco acaba sujando suas mãos com centenas (as vezes milhares) de linhas de VB dentro de funções excel. Isso mostra como a idéia de indexação e hash são muito simples e intuitivas, às vezes o que atrapalha é o professor :).

Vamos ver como ficaria ensinar com esse exemplo: o contrato do método hashCode diz que:

se a.equals(b) então a.hashCode() == b.hashCode()

Pensando no problema da comparação dos arquivos, podemos falar:

fileA é equivalente a fileB então tamanho de fileA == tamanho de fileB

Colocando em java:
se fileA.equals(fileB) então fileA.length() == fileB.length()

Reescrevendo hashCode para espalhar de acordo com esse nosso critério, teríamos finalmente:

se fileA.equals(fileB) então fileA.hashCode() == fileB.hashCode()

Muito mais simples e direto que o exemplo da String! Aqui o debate poderia prosseguir em encontrar um hashCode que espalhasse melhor os arquivos, e o assunto cairia em checksums… mais perfeito impossível!

Vale lembrar que eu estou falando aqui de uma classe File imaginária, pois a java.io.File não leva em consideração o conteúdo do arquivo para o equals nem para o hashCode, ela usa apenas o abstract pathname em consideração.

10 Comentários

  1. Renato 04/09/2006 at 09:59 #

    Na minha opinião o hashCode não deveria existir, simplesmente uma nova keyword que a gente colocasse nos campos de identificação seria mais coeso e menos repetitivo:

    class Person {
    public id String name;
    public id int age;
    public String anotherField;
    }

  2. Tiago Silveira 04/09/2006 at 11:04 #

    Existem (poucos) casos em que vc quer que dois objetos que não são equivalentes tenham o mesmo valor de hash code. Um caso que me vem à cabeça é aquele em que a comparação de equivalencia (equals()) requer algum processamento pesado, que na prática raramente será necessário porque mais de 90% dos objetos terão diferenças em outros atributos e os que são iguais geralmente são a mesma instância (e o seu equals() tested (this == other).

  3. Tiago Silveira 04/09/2006 at 11:05 #

    Puxa, esqueci de elogiar: ótimo post!

  4. Luiz Aguiar 05/09/2006 at 10:35 #

    Dependendo pra quem for falar sobre hash code, eu uso exemplos dos pacotes de trafégo de rede, cada um tem seu cabeçalho, então pra encontrar dois pacotes idênticos dentro de 1GB de dados, vc pega ai o cabeçalho (hash code) dos pacotes como “filtro” da busca.
    Pelo menos os “raquers” entendem na primeira hehe.

  5. Fernando Boaglio 06/09/2006 at 17:17 #

    Só uma observação sobre o Eclipse 3.2, que dá pra gerar facilmente o método hashCode:

    No meio do seu código Java tecle: ALT+SHIFT+S,
    depois escolha a opção: “generate hashcode() and equals()…”

    Notem o algoritmo gerado pelo Eclipse, normalmente ele é bem interessante.

  6. Alex 18/03/2011 at 17:54 #

    Fiz o curso JF-11 e não consegui entender o que foi redigido na apostila, na sessão “16.13 – Para saber mais: Equals e HashCode”. Primeiro ele diz “só vamos procurar entre os elementos que estão no mesmo grupo daquele hashcode. Dentro deste grupo, vamos testando o objeto procurado com o candidato usando equals()”. O que está se dizendo aqui, implicitamente, é que temos vários elementos com o mesmo hashcode, já que ele só vai testar o equals() nos elementos do mesmo grupo (hashcode). Em outras palavras, eu terei vários elementos com o mesmo hashcode, mas apenas um deles terá o mesmo equal do objeto procurado. Pergunta: é assim mesmo que funciona? A boa prática não diz que se equals diferente, então hascode deve ser diferente?

  7. Paulo Silveira 18/03/2011 at 18:56 #

    Ola Alex

    Excelente questão.

    O ideal seria esse mesmo, que para cada objeto, o hashCode fosse único. Mas infelizmente isso as vezes não é possível.

    Mesmo se você tiver uma chave boa como essa, isso não é o suficiente para garantir que cada “bucket” da tabela de espalahamento só tenha um objeto, pois essa tabela tem apenas um numero limitado de buckets (definidos pelo loadfactor passado no seu construtor e numero de elementos ja inseridos).

    Isso é, se temos 10 objetos, mesmo com 100 buckets existe a chance de que o resultado de objeto.hashCode() % 100 coloque no mesmo bucket dois objetos que nao sejam equals (na implementação do java é um pouco mais elaborado que isso)

    Um exemplo obvio sao duas strings como as citadas aqui nesse post. Uma que desse 337 de hashcode e outra 227 de hashcode. Sao diferentes e possuem hashcodes diferentes, mas poderiam ser colocadas no mesmo bucket dependendo da quantidade deles (se fossem 100 nesse caso). Ai essas duas strings seriam comparadas com equals, mesmo obviamente nao sendo equals, mas a tabela de hash nao tem como saber isso de antemao.

    Por melhor e mais unico que seja o seu valor de hashcode, pode ainda haver colisoes na tabela.

    abraços

  8. victoria 05/07/2012 at 23:25 #

    Você sabe se vai dar conflito com buckets se eu tentar fazer uma geração de codigo de barras de informação de usuarios que nunca podem ser iguais? **gerando hashCode separadamente** ou seria mais seguro eu tentar usar uma API a parte no java?

Deixe uma resposta