Por que hashCode () do Java in Cadeia usar 31 como um multiplicador?

https://stackoverflow.com/questions/299304

08-07-2019
|

Pergunta

Per a documentação Java, o hash de código para um objeto String é calculado como:

s[0]*31^(n-1) + s[1]*31^(n-2) + ... + s[n-1]
usando int aritmética, onde s[i] é o i th caráter da corda, n é o comprimento a corda, e ^ indica exponenciação.

Por que é 31 usado como um multiplicador?

Eu entendo que o multiplicador deve ser um relativamente grande número primo. Então por que não 29 ou 37, ou mesmo 97?

Solução

De acordo com a Effective Java de Joshua Bloch (um livro que pode não ser bastante recomendada, e que eu comprei graças à contínua menciona em stackoverflow):

O valor de 31 foi escolhido porque é um primo ímpar. Se fosse mesmo ea multiplicação transbordou, a informação seria perdida, como a multiplicação por 2 é equivalente a mudar. A vantagem de usar um número primo é menos claro, mas é tradicional. Uma boa propriedade de 31 é que a multiplicação pode ser substituída por uma mudança e uma subtração para um melhor desempenho: 31 * i == (i << 5) - i. Modern VMs fazer esse tipo de otimização automaticamente.

(do Capítulo 3, ponto 9: Sempre override hashcode quando você substituir iguais, página 48)

Outras dicas

Como Goodrich e Tamassia salientar, Se você tomar mais de 50.000 palavras em inglês (formado como a união das listas de palavras fornecidas em duas variantes do Unix), usando as constantes de 31, 33, 37, 39, e 41 vai produzir menos do que 7 colisões em cada caso. Sabendo disso, ele deve vir como nenhuma surpresa que muitas implementações de Java escolher uma destas constantes.

Por coincidência, eu estava no meio de ler a seção "códigos de hash polinomial" quando vi esta questão.

EDIT: aqui está link para o ~ livro 10mb PDF Estou me referindo a acima. Consulte a seção 10.2 Hash Tables (página 413) de Estruturas de dados e Algoritmos em Java

Em (principalmente) processadores antigos, multiplicando por 31 pode ser relativamente barato. Em um braço, por exemplo, é apenas uma instrução:

RSB       r1, r0, r0, ASL #5    ; r1 := - r0 + (r0<<5)

A maioria dos outros processadores exigiria uma mudança separada e instrução subtrair. No entanto, se o seu multiplicador é lento isso ainda é uma vitória. Os processadores modernos tendem a ter multiplicadores rápidos por isso não faz muita diferença, desde que 32 vai no lado correto.

Não é um grande algoritmo de hash, mas é bom o suficiente e melhor do que o código 1.0 (e muito muito melhor do que a especificação 1.0!).

Ao multiplicar, bits são deslocados para a esquerda. Isto usa mais do espaço disponível de códigos de hash, reduzindo colisões.

por não utilizar uma potência de dois, o de ordem inferior, os bits mais à direita são preenchidos, bem como, para ser misturado com a próxima peça de dados que vão para o hash.

O n * 31 expressão é equivalente a (n << 5) - n.

Você pode ler o raciocínio original de Bloch em "Comentários" em http: // bugs.java.com/bugdatabase/view_bug.do?bug_id=4045622. Ele investigou o desempenho de diferentes funções hash em relação ao "tamanho da cadeia média", resultando em uma tabela hash. P(31) foi uma das funções comuns durante esse tempo que ele encontrou no livro de K & R (mas mesmo Kernighan e Ritchie não conseguia se lembrar de onde veio). No final, ele basicamente teve que escolher um e então ele tomou P(31) desde que parecia para executar bem o suficiente. Mesmo que P(33) não era realmente pior e multiplicação por 33 é igualmente rápido para calcular (apenas uma mudança por 5 e uma adição), ele optou por 31 desde 33 não é um número primo:

Dos restantes quatro, eu provavelmente seleccionar P (31), como é o mais barato para calcular em um RISC Máquina (31 porque é a diferença de duas potências de dois). P (33) é Da mesma forma barata para calcular, mas seu desempenho é marginalmente pior, e 33 é composto, o que me deixa um pouco nervoso.

Assim, o raciocínio não era tão racional quanto muitas das respostas aqui parece implicar. Mas somos tudo de bom na vinda acima com razões racionais após as decisões do intestino (e mesmo Bloch pode ser propenso a isso).

Na verdade, 37 iria funcionar muito bem! z: = 37 * x pode ser calculado como y := x + 8 * x; z := x + 4 * y. Ambas as etapas correspondem às instruções x86 um LEA, então isso é extremamente rápido.

Na verdade, a multiplicação com o primeiro-even-maior 73 poderia ser feito com a mesma velocidade, definindo y := x + 8 * x; z := x + 8 * y.

Usando 73 ou 37 (em vez de 31) pode ser melhor, porque conduz a código denso : As duas instruções LEA ter apenas 6 bytes contra os 7 bytes para mover-shift para subtrair a multiplicação por 31. uma possível ressalva é que as instruções LEA 3-argumento usado aqui tornou-se mais lenta na arquitetura Sandy bridge da Intel, com um aumento da latência de 3 ciclos.

Além disso, 73 é o número favorito de Sheldon Cooper.

Neil Coffey explica porque 31 é usado em engomadoria o viés .

Basicamente utilizando 31 dá-lhe uma distribuição de probabilidade mais até mesmo definir-bit para a função hash.

A partir JDK-4045622 , onde Joshua Bloch descreve as razões por isso que a implementação particular (novo) String.hashCode() foi escolhido

A tabela abaixo resume o desempenho dos vários de hash funções descritas acima, por três conjuntos de dados:

1) Todas as palavras e frases com entradas no Merriam-Webster 2º Int'l Unabridged Dictionary (311,141 cordas, comprimento avg 10 caracteres).

2) todas as cordas em / bin / , / / ??bin usr / , / usr / lib / , / usr / ucb / e / usr / openwin / bin / * (66,304 cordas, comprimento média de 21 caracteres).

3) Uma lista de URLs reunidos por um web-crawler que funcionou por vários horas da noite anterior (28,372 cordas, comprimento avg 49 caracteres).

A métrica de desempenho mostrado na tabela é o "tamanho médio da cadeia" sobre todos os elementos da tabela de Hash (isto é, o valor esperado do número de chave compara a olhar para cima um elemento).
                          Webster's   Code Strings    URLs
                          ---------   ------------    ----
Current Java Fn.          1.2509      1.2738          13.2560
P(37)    [Java]           1.2508      1.2481          1.2454
P(65599) [Aho et al]      1.2490      1.2510          1.2450
P(31)    [K+R]            1.2500      1.2488          1.2425
P(33)    [Torek]          1.2500      1.2500          1.2453
Vo's Fn                   1.2487      1.2471          1.2462
WAIS Fn                   1.2497      1.2519          1.2452
Weinberger's Fn(MatPak)   6.5169      7.2142          30.6864
Weinberger's Fn(24)       1.3222      1.2791          1.9732
Weinberger's Fn(28)       1.2530      1.2506          1.2439
Olhando para esta tabela, é claro que todas as funções, exceto para a função Java atual e as duas versões quebradas de Weinberger de função oferta excelente, desempenho quase indistinguíveis. Eu fortemente conjecturar que esse desempenho é essencialmente o "Ideal teórico", que é o que você obteria se você usou um verdadeiro aleatório gerador de números no lugar de uma função hash.

Eu descartar a função WAIS como sua especificação contém páginas de números aleatórios, e seu desempenho não é melhor do que qualquer um dos funções muito mais simples. Qualquer uma das seis funções restantes parecer excelentes opções, mas temos que escolher um. Suponho que descarta variante de Vo e função por causa de seu agregado da Weinberger complexidade, embora menor. Dos restantes quatro, eu provavelmente seleccionar P (31), como é o mais económico para calcular numa máquina RISC (porque 31 é a diferença de duas potências de dois). P (33) é semelhante ao barato de calcular, mas o desempenho é marginalmente pior, e 33 é composto, o que me deixa um pouco nervoso.

Josh

Eu não tenho certeza, mas eu acho que eles testaram algumas amostras de números primos e descobriu que 31 deu a melhor distribuição sobre alguma amostra de possíveis Strings.

Bloch não chega a entrar nessa, mas a razão Eu sempre ouvi / acreditado é que este é álgebra básica. Hashes resumem-se a operações de multiplicação e módulo, o que significa que você nunca quer usar números com fatores comuns se você pode ajudá-lo. Em outras palavras, números relativamente primos proporcionar uma distribuição uniforme de respostas.

Os números que compõem usando um hash são tipicamente:

módulo do tipo de dados que você colocá-lo em (2 ^ 32 ou 2 ^ 64)
módulo de contagem de bucket em sua hashtable (varia. Em java costumava ser privilegiada, está agora em 2 ^ n)
multiplicar ou mudança por um número mágico em sua função de mistura
O valor de entrada

Você realmente só começa a controlar um par desses valores, portanto, um pouco de cuidado extra é devido.

Na versão mais recente do JDK, 31 ainda é usado. https://docs.oracle.com/en/java/javase/11/docs/api/java.base/java/lang/String.html#hashCode ()

O objetivo da seqüência de hash é

único (Let ver ^ operador no documento de cálculo hashcode, é ajudar único)
custo mais barato para o cálculo

31 é o valor máximo pode colocar em 8 bits (1 byte =) registar. é o maior número primo pode colocar em um registo de bytes, é número ímpar.

Multiply 31 é << 5 em seguida, subtrair-se, portanto, precisam de recursos baratos.

Licenciado em: CC-BY-SA com atribuição

Não afiliado a StackOverflow