Por que usar um número primo no hashCode?

173

Eu só estava me perguntando por que os números primos são usados ​​no hashCode()método de uma classe ? Por exemplo, ao usar o Eclipse para gerar meu hashCode()método, sempre há o número principal 31usado:

public int hashCode() {
     final int prime = 31;
     //...
}

Referências:

Aqui está uma boa cartilha sobre o Hashcode e um artigo sobre como funciona o hash que eu encontrei (C #, mas os conceitos são transferíveis): Diretrizes e regras de Eric Lippert para GetHashCode ()

Ian Dallas
fonte
Essa é mais ou menos uma duplicata da pergunta stackoverflow.com/questions/1145217/… .
Hans-Peter Störr
1
Por favor, verifique minha resposta em stackoverflow.com/questions/1145217/… Está relacionado às propriedades dos polinômios sobre um campo (não um anel!), Portanto, números primos.
TT_ 26/11/2013

Respostas:

103

Como você deseja que o número pelo qual você está multiplicando e o número de buckets nos quais você está inserindo tenha fatorações primárias ortogonais.

Suponha que haja 8 baldes para inserir. Se o número que você está usando para multiplicar for múltiplo de 8, o intervalo inserido será determinado apenas pela entrada menos significativa (a que não é multiplicada). Entradas semelhantes entrarão em conflito. Não é bom para uma função de hash.

31 é um número suficientemente grande para que seja improvável que o número de buckets seja divisível por ele (e, de fato, as implementações modernas do HashMap em java mantêm o número de buckets em uma potência de 2).

ILMTitan
fonte
9
Em seguida, uma função de hash que se multiplica por 31 terá um desempenho não ideal. No entanto, eu consideraria essa implementação de tabela de hash mal projetada, considerando o quão comum é 31 como um multiplicador.
precisa saber é o seguinte
11
Então 31 é escolhido com base no pressuposto de que os implementadores de tabela de hash sabem que 31 é comumente usado em códigos de hash?
Steve Kuo
3
31 é escolhido com base na ideia de que a maioria das implementações possui fatorações de números primos relativamente pequenos. 2s, 3s e 5s geralmente. Pode começar às 10 e crescer 3X quando ficar muito cheio. O tamanho raramente é inteiramente aleatório. E mesmo que fosse, 30/31 não são chances ruins de ter algoritmos de hash bem sincronizados. Também pode ser fácil calcular como outros já declararam.
ILMTitan
8
Em outras palavras ... precisamos saber algo sobre o conjunto de valores de entrada e as regularidades do conjunto, para escrever uma função projetada para removê-los dessas regularidades, para que os valores no conjunto não colidam na mesma baldes de hash. Multiplicar / dividir / modular por um número primo alcança o efeito, porque se você tem um LOOP com itens X e pula espaços Y no loop, nunca retornará ao mesmo local até que X se torne um fator de Y Como X é frequentemente um número par ou uma potência de 2, você precisa que Y seja primo, de modo que X + X + X ... não é um fator de Y, então 31 yay! : /
Triynko
3
@FrankQ. É a natureza da aritmética modular. (x*8 + y) % 8 = (x*8) % 8 + y % 8 = 0 + y % 8 = y % 8
ILMTitan
135

Os números primos são escolhidos para melhor distribuir os dados entre os depósitos de hash. Se a distribuição das entradas for aleatória e distribuída uniformemente, a escolha do código / módulo de hash não importa. Isso só tem impacto quando há um determinado padrão nas entradas.

Esse é geralmente o caso ao lidar com locais de memória. Por exemplo, todos os números inteiros de 32 bits são alinhados aos endereços divisíveis por 4. Confira a tabela abaixo para visualizar os efeitos do uso de um módulo primário versus não primário:

Input       Modulo 8    Modulo 7
0           0           0
4           4           4
8           0           1
12          4           5
16          0           2
20          4           6
24          0           3
28          4           0

Observe a distribuição quase perfeita ao usar um módulo primário versus um módulo não primário.

No entanto, embora o exemplo acima seja amplamente inventado, o princípio geral é que, ao lidar com um padrão de entradas , o uso de um módulo de número primo produzirá a melhor distribuição.

advait
fonte
17
Não estamos falando do multiplicador usado para gerar o código de hash, e não do módulo usado para classificar esses códigos de hash em buckets?
ILMTitan
3
Mesmo princípio. Em termos de E / S, o hash é alimentado na operação do módulo da tabela de hash. Acho que o ponto era que, se você multiplicar por números primos, obterá mais entradas distribuídas aleatoriamente até o ponto em que o módulo nem importará. Como a função hash atende à folga de distribuir melhor os insumos, tornando-os menos regulares, é menos provável que colidam, independentemente do módulo usado para colocá-los em um balde.
Triynko
9
Esse tipo de resposta é muito útil porque é como ensinar alguém a pescar, em vez de pegar uma para ela. Ajuda as pessoas a ver e entender o princípio subjacente ao uso de números primos para hashes ... que é distribuir insumos de forma irregular, para que caiam uniformemente nos baldes, uma vez modulados :).
Triynko
29

Pelo que vale a pena, o Effective Java 2nd Edition renuncia manualmente à questão da matemática e apenas diz que o motivo da escolha 31 é:

  • Porque é um primo ímpar e é "tradicional" usar primos
  • Também é um a menos que a potência de dois, o que permite a otimização bit a bit

Aqui está a citação completa, do Item 9: sempre substitui hashCodequando você substituiequals :

O valor 31 foi escolhido porque é um primo ímpar. Se fosse par e a multiplicação transbordasse, as informações seriam perdidas, pois multiplicação por 2 é equivalente a deslocamento. A vantagem de usar um primo é menos clara, mas é tradicional.

Uma boa propriedade 31 é que a multiplicação pode ser substituída por um turno ( §15.19 ) e subtração para obter melhor desempenho:

 31 * i == (i << 5) - i

As VMs modernas fazem esse tipo de otimização automaticamente.


Embora a receita neste item produza funções hash razoavelmente boas, ela não produz funções hash de ponta, nem as bibliotecas da plataforma Java fornecem essas funções hash a partir do release 1.6. Escrever essas funções de hash é um tópico de pesquisa, melhor deixar para matemáticos e cientistas da computação teórica.

Talvez uma versão posterior da plataforma forneça funções hash de ponta para suas classes e métodos utilitários para permitir que programadores comuns construam essas funções hash. Enquanto isso, as técnicas descritas neste item devem ser adequadas para a maioria das aplicações.

De maneira bastante simplista, pode-se dizer que o uso de um multiplicador com vários divisores resultará em mais colisões de hash . Como para o hash eficaz, queremos minimizar o número de colisões, tentamos usar um multiplicador que tenha menos divisores. Um número primo, por definição, possui exatamente dois divisores positivos distintos.

Perguntas relacionadas

poligenelubricants
fonte
4
Eh, mas não são adequados muitos primos que são ou 2 ^ n + 1 (chamados números primos Fermat ), isto é, 3, 5, 17, 257, 65537ou 2 ^ n - 1 ( primes Mersenne ): 3, 7, 31, 127, 8191, 131071, 524287, 2147483647. No entanto 31(e não, digamos 127) , é optado.
Dmitry Bychenko # 23/15
4
"porque é um primo ímpar" ... existe apenas um primo par: P
Martin Schneider
Não gosto da redação "é menos clara, mas é tradicional" em "Java eficaz". Se ele não quiser entrar nos detalhes matemáticos, deve escrever algo como "tem razões matemáticas [semelhantes]". A maneira como ele escreve parece ter apenas antecedentes históricos :( #
Qw3ry
5

Ouvi dizer que 31 foi escolhido para que o compilador possa otimizar a multiplicação para deslocar para a esquerda 5 bits e subtrair o valor.

Steve Kuo
fonte
como o compilador pode otimizar dessa maneira? x * 31 == x * 32-1 não é verdadeiro para todos os x afinal. O que você quis dizer foi turno à esquerda 5 (é igual a multiplicar por 32) e subtrai o valor original (x no meu exemplo). Embora isso possa ser mais rápido do que uma multiplicação (provavelmente não é para os processadores modernos de CPU), há fatores mais importantes a serem considerados ao escolher uma multiplicação para um código de hasch (vem à mente a distribuição igual dos valores de entrada para os buckets)
Grizzly
Pesquise um pouco, essa é uma opinião bastante comum.
Steve Kuo
4
A opinião comum é irrelevante.
fractor
1
@ Grizzly, é mais rápido que a multiplicação. O IMul tem uma latência mínima de 3 ciclos em qualquer CPU moderna. (consulte os manuais do agner fog) mov reg1, reg2-shl reg1,5-sub reg1,reg2pode executar em 2 ciclos. (o mov é apenas uma renomeação e leva 0 ciclos).
21415 Johan Johan
3

Aqui está uma citação um pouco mais próxima da fonte.

Tudo se resume a:

  • 31 é primo, o que reduz colisões
  • 31 produz uma boa distribuição, com
  • uma troca razoável de velocidade
John
fonte
3

Primeiro, você calcula o valor do hash módulo 2 ^ 32 (o tamanho de um int), portanto, deseja algo relativamente primo para 2 ^ 32 (relativamente primo significa que não há divisores comuns). Qualquer número ímpar serviria para isso.

Então, para uma determinada tabela de hash, o índice geralmente é calculado a partir do módulo de valor de hash do tamanho da tabela de hash, portanto, você deseja algo que seja relativamente primordial para o tamanho da tabela de hash. Geralmente, os tamanhos das tabelas de hash são escolhidos como números primos por esse motivo. No caso de Java, a implementação da Sun garante que o tamanho seja sempre uma potência de dois, portanto, um número ímpar também seria suficiente aqui. Há também uma massagem adicional das chaves de hash para limitar ainda mais as colisões.

O efeito ruim se a tabela de hash e o multiplicador tiverem um fator comum npode ser que, em certas circunstâncias, apenas 1 / n entradas na tabela de hash sejam usadas.

starblue
fonte
2

A razão pela qual os números primos são usados ​​é minimizar colisões quando os dados exibem alguns padrões particulares.

Primeiras coisas primeiro: se os dados são aleatórios, não há necessidade de um número primo, você pode fazer uma operação mod contra qualquer número e terá o mesmo número de colisões para cada valor possível do módulo.

Mas quando os dados não são aleatórios, coisas estranhas acontecem. Por exemplo, considere dados numéricos sempre múltiplos de 10.

Se usarmos o mod 4, encontramos:

10 mod 4 = 2

20 mod 4 = 0

30 mod 4 = 2

40 mod 4 = 0

50 mod 4 = 2

Portanto, dos 3 valores possíveis do módulo (0,1,2,3), apenas 0 e 2 terão colisões, o que é ruim.

Se usarmos um número primo como 7:

10 mod 7 = 3

20 mod 7 = 6

30 mod 7 = 2

40 mod 7 = 4

50 mod 7 = 1

etc

Também observamos que 5 não é uma boa escolha, mas 5 é primo, o motivo é que todas as nossas chaves são múltiplas de 5. Isso significa que temos que escolher um número primo que não divida nossas chaves, escolher um número primo grande é geralmente o suficiente.

Portanto, errar por ser repetitivo é a razão pela qual os números primos são usados ​​para neutralizar o efeito dos padrões nas chaves na distribuição de colisões de uma função hash.

Amar Magar
fonte
1

31 também é específico para o Java HashMap, que usa um int como tipo de dados hash. Assim, a capacidade máxima de 2 ^ 32. Não faz sentido usar primos Fermat ou Mersenne maiores.

DED
fonte
0

Geralmente, ajuda a obter uma distribuição mais uniforme dos seus dados entre os blocos de hash, especialmente para chaves de baixa entropia.


fonte