O que é um primo sensata para o cálculo hashcode?

Question

Eclipse 3.5 tem um recurso muito bom para gerar funções Java hashCode (). Ele geraria por exemplo (ligeiramente encurtado:)

class HashTest {
    int i;
    int j;        
    public int hashCode() {
        final int prime = 31;
        int result = prime + i;
        result = prime * result + j;
        return result;
    }
}

(Se você tem mais atributos na classe, result = prime * result + attribute.hashCode(); é repetido para cada atributo adicional. Para ints .hashCode () pode ser omitido.)

Este parece muito bem, mas para a escolha 31 para o prime. Provavelmente é tomada a partir da implementação hashCode de Java Cordas , que foi usado por motivos de desempenho que estão muito longe depois da introdução de multiplicadores de hardware. Aqui você tem muitas colisões hashcode para pequenos valores de i e j: por exemplo (0,0) e (a 1,31) têm o mesmo valor. Eu acho que é uma coisa ruim (TM), uma vez que valores pequenos ocorrem frequentemente. Para String.hashCode você também vai encontrar muitas cordas curtas com o mesmo código hash, por exemplo "Ca" e "DB". Se você tomar uma grande privilegiada, este problema desaparece se você escolher o direito prime.

Assim, a minha pergunta: o que é uma boa privilegiada para escolher? Que critérios você aplica para encontrá-lo?

Esta é entendida como uma questão geral - então eu não quero dar uma gama de i e j. Mas suponho que na maioria das aplicações valores relativamente pequenos ocorrem mais frequentemente do que grandes valores. (Se você tem grandes valores a escolha do principal é provavelmente sem importância.) Ele pode não fazer muita diferença, mas a melhor opção é uma maneira fácil e óbvia para melhorar isso - então por que não fazê-lo? Commons lang HashCodeBuilder também sugere curiosamente pequenos valores.

( Clarificação : este é não uma cópia de por que o hashCode () do Java in Cadeia utilização 31 como um multiplicador? desde a minha questão não está preocupado com a história do 31 no JDK, mas sobre o que seria um melhor valor em novo código usando o mesmo modelo básico. Nenhuma das respostas não tentam responder a isso.)

Answer 1

Eu recomendo usar 92821 . Aqui está o porquê.

Para dar uma resposta significativa para isso você tem que saber algo sobre os possíveis valores de i e j. A única coisa que posso pensar é em geral, que em muitos casos pequenos valores será mais comum do que grandes valores. (As probabilidades de 15 aparecem como um valor em seu programa são muito melhores do que, digamos, 438281923.) Assim, parece uma boa idéia para fazer o menor colisão hashcode tão grande quanto possível, escolhendo um nobre apropriado. Para 31 este bastante ruim - já para i=-1 e j=31 você tem o mesmo valor hash como para i=0 e j=0

.

Uma vez que isso é interessante, eu escrevi um pequeno programa que procurou toda a gama int para o melhor privilegiada nesse sentido. Ou seja, para cada I nobre procurou o valor mínimo de Math.abs(i) + Math.abs(j) sobre todos os valores de i,j que têm o mesmo código hash como 0,0, e, em seguida, tomou o privilegiada, onde esse valor mínimo é tão grande quanto possível.

Drumroll : o melhor privilegiada neste sentido é 486187739 (com a menor colisão sendo i=-25486, j=67194). Quase tão bom e muito mais fácil de lembrar é 92821 com a menor colisão sendo i=-46272 and j=46016.

Se você der "pequeno" outro significado e quer ser o mínimo de Math.sqrt(i*i+j*j) para a colisão tão grande quanto possível, os resultados são um pouco diferentes: o melhor seria 1322837333 com i=-6815 and j=70091, mas o meu favorito 92821 (menor -46272,46016 colisão ) é novamente quase tão bom como o melhor valor.

Eu reconheço que é bastante discutível se estes cálculo faz muito sentido na prática. Mas eu acho que, tendo 92821 como Primeiro faz muito mais sentido do que 31, a menos que tenha boas razões para não.

Answer 2

Na verdade, se você tomar um primo tão grande que chega perto de INT_MAX, você tem o mesmo problema por causa da aritmética modulo. Se você espera de hash principalmente cadeias de comprimento 2, talvez um primo próximo da raiz quadrada de INT_MAX seria melhor, se as cordas você haxixe são mais longos que não importa tanto e colisões são assim mesmo inevitável ...

Answer 3

As colisões não pode ser um grande problema ... O principal objetivo do hash é evitar o uso iguais para 1: 1 comparações. Se você tem uma implementação onde é igual a é "geralmente" extremamente barato para objetos que colidiram hashs, então este não é um problema (em tudo).

No final, o que é a melhor maneira de hashing depende do que você está comparando. No caso de um par de int (como no seu exemplo), usando operadores básicos bit a bit poderia ser suficiente (como a utilização de & ou ^).

Answer 4

Você precisa definir a sua gama de i e j. Você pode usar um número primo para ambos.

public int hashCode() {
   http://primes.utm.edu/curios/ ;)
   return 97654321 * i ^ 12356789 * j;
}

Answer 5

Eu escolheria 7243. Grande o suficiente para evitar colisões com números pequenos. Não transborde para pequenos números rapidamente.

Answer 6

Eu só quero salientar que hashcode não tem nada a ver com a prime. Na implementação JDK

for (int i = 0; i < value.length; i++) {
                h = 31 * h + val[i];
            }

Eu encontrei se você substituir 31 com 27 , o resultado são muito semelhantes.