Por que usar um número primo no hashCode?

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 ()

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).

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.

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

• HashCode Java a partir de um campo - a receita, mais um exemplo do uso dos construtores do Apache Commons Lang
• é incorreto definir um código de hash de um objeto como a soma, multiplicação, qualquer que seja, de todas as variáveis ​​de classe hashcodes?
• Guia do iniciante absoluto para mudança de bits?

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.

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

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.

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.

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.

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