Implementar HashCode

Programação Java
#1

Pessoal,

Vou ter uma tabela de tamanho definido (975) e vou armazenar objetos que contêm um ID (int) e um nome (String) como chaves.

Estou tentando implementar o hashCode dele de maneira que o hashCode máximo seja o tamanho da minha tabela.

Alguém tem alguma idéia?

Obrigado

#2

Cara, se você está fazendo isso, é porque provavelmente em algum lugar você está usando o hashCode para uma função que não é a dele.

Isso não é bom, pois algoritmos como o da hashTable e do hashSet são fortemente dependentes de um bom algoritmo hash. Para ver mais detalhes sobre esse assunto, leia o item 8 do capítulo 3 do livro Effective Java, do Joshua Bloch (o cara que simplesmente implementou o Collections framework).
http://java.sun.com/developer/Books/effectivejava/Chapter3.pdf

Agora vamos ao seu problema. Quem deve ter o hashCode máximo igual ao tamanho da tabela? Se for a tabela, basta calcular o hash com o algoritmo do livro e no final fazer:
hashObtido = hashObtido % TAMANHO_TABELA;

(onde aqui TAMANHO_TABELA=975).

Com o operador %, o hashObtido passa a ser então o resto da divisão do hashCalculado pelo tamanho da tabela. Isso dá um número entre 0 e 974, no nesse caso.

Se forem os objetos, a técnica é a mesma. Mas você terá o problema de criar uma dependência dos objetos com a tabela, uma vez que esse valor, 975 teria que estar contido em algum campo “public static final”.

Ficaria assim:
hashObtido = hashObtido % ClasseDaTabela.TAMANHO_TABELA;

#3

Vou tentar explicar melhor o que estou tentando fazer.

Eu tenho uma matriz 65 x 15 (daí o 975) que é uma representação visual dos meus objetos.

Pensei em utilizar o HashCode como “índice” dessa matriz para colocar os meus objetos. Por isso o HashCode deveria ser no máximo 975, assim daria uma certa aleatoriedade, já que o HashCode seria baseado num id (int) e num nome (string).

Vou dar uma olhada no link que você mandou pra tentar ter mais idéias.

Obrigado

#4

Acho que então a sugestão que eu dei não serve.

Veja bem, o algoritmo de hash permite que haja colisões (dois hashs iguais). No seu caso, você já não quer colisões. Mais um motivo para não usar o hash para isso. :wink:

O ideal mesmo é criar outro método e escrever um contrato mais específico para o seu problema. Não custa nada.

Parece que você não vai escapar de ter uma dependência com a tabela. O seu valor poderia ser:

valor = (indiceDaLinha * (númeroDeColunas-1)) + indiceDaColuna;

Isso cria um índice “linear” para sua tabela, que pode ser usado por seus objetos. Aliás, eles até poderiam delegar isso para tabela… Que tal na classe do objeto fazer:

public int getLinearIndex() {
    if (table == null)
       throw new IllegalStateException("Not bound to a table");
    return table.getLinearIndex(this);
}

E então deixar que a tabela conheça a posição do objeto e calcule o índice linear dele?

#5

O problema do índice linear eu já tinha resolvido…

Agora, como pode haver colisões se o id é único?

Eu poderia simplesmente usar o id, mas daí os dados ficariam jogados sequencialmente da mesma maneira.

#6

Huummm…

Só estou aconselhando a não usar o método hashCode para o que ele não foi feito para fazer… Se você colocar um requisito extra no hashCode (que seja, único, por exemplo), quem for manter esse programa terá que advinhar isso. Fora o fato de que, o código ficará menos claro, porque em certos trechos o hash será usado de maneira “estranha” para quem lê. Finalmente, você estará comprometendo o funcionamento das classes que já se baseiam no hash…

A menos é claro, que sua intenção seja efetivamente implementar na sua tabela uma hashTable. Nesse caso, não obrigue suas classes a terem um hash não padrão e considere que o contrato do hash aceita duplicatas.

Você pode simplesmente colocar no sua SimpleHashTable a condição de que: “Essa tabela não aceita hash duplicados” e lance uma exceção se isso acontecer. Nesse caso, aquela idéia de usar o operador % ainda vale. Pegue o hash do objeto, divida pelo tamanho máximo da tabela e adicione ele no índice do resultado.

#7

Ah sim, sua classe de objetos pode ter um método getRandomIndex().

Você pode faze-lo assim:

public void getRandomIndex()
{
    Random r = new Random();
    int random = r.nextInt(ClasseDaTabela.TAMANHO_MAXIMO);
    while (randomSet.contains(random))
      random = r.nextInt(ClasseDaTabela.TAMANHO_MAXIMO);
    randomSet.add(random);

    return random;
}

O random set seria um HashSet estático, contendo todos os índices gerados. Entretanto, dessa forma, você também teria que retirar o índice do objeto do set quando o objeto fosse destruído.

#8

Estou resolvendo outros problemas por enquanto, mas vou dar uma olhada nas suas sugestões.

A do Random é a que mais me atrai, já havia pensado nela. O problema dela é que cada objeto terá um índice diferente em cada execução, mas pra uma versão beta serve.

Obrigado por tudo!

Abraços

#9