Por que o hashCode () do Java em String usa 31 como um multiplicador?

De acordo com a documentação Java, o código de hash para um Stringobjeto é calculado como:

s[0]*31^(n-1) + s[1]*31^(n-2) + ... + s[n-1]

usando intaritmética, onde s[i]é o i- ésimo caractere da sequência, né o comprimento da sequência e ^indica exponenciação.

Por que o 31 é usado como multiplicador?

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

De acordo com o Effective Java de Joshua Bloch (um livro que não pode ser recomendado o suficiente, e que eu comprei graças a menções contínuas sobre o stackoverflow):

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 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. As VMs modernas fazem esse tipo de otimização automaticamente.

(do capítulo 3, item 9: sempre substitua o código de hash ao substituir igual, página 48)

Como Goodrich e Tamassia apontam, se você usar mais de 50.000 palavras em inglês (formadas como a união das listas de palavras fornecidas em duas variantes do Unix), o uso das constantes 31, 33, 37, 39 e 41 produzirá menos de 7 colisões em cada caso. Sabendo disso, não é de surpreender que muitas implementações de Java escolham uma dessas constantes.

Por coincidência, eu estava lendo a seção "códigos de hash polinomiais" quando vi essa pergunta.

EDIT: aqui está o link para o livro ~ 10mb PDF a que me refiro acima. Consulte a seção 10.2 Tabelas de hash (página 413) de estruturas de dados e algoritmos em Java

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

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

A maioria dos outros processadores exigiria uma instrução separada de troca e subtração. No entanto, se o seu multiplicador for lento, isso ainda é uma vitória. Os processadores modernos tendem a ter multiplicadores rápidos, de modo que não faz muita diferença, desde que 32 sejam do lado correto.

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

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

Por não usar uma potência de dois, os bits de ordem inferior e mais à direita também são preenchidos, para serem misturados com os próximos dados inseridos no hash.

A expressão n * 31é 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 de hash em relação ao "tamanho médio da cadeia" resultante em uma tabela de hash. P(31)foi uma das funções comuns durante esse período que ele encontrou no livro de K&R (mas nem Kernighan nem Ritchie conseguiam se lembrar de onde vinha). No final, ele basicamente teve que escolher um e, por isso, aceitou, P(31)pois parecia ter um bom desempenho. Mesmo que P(33)não tenha sido realmente pior e a multiplicação por 33 seja igualmente rápida de calcular (apenas um turno por 5 e uma adição), ele optou por 31, já que 33 não é primo:

Dos quatro restantes, eu provavelmente selecionaria P (31), pois é o mais barato para calcular em uma máquina RISC (porque 31 é a diferença de duas potências de duas). P (33) é igualmente barato de calcular, mas seu desempenho é marginalmente pior e 33 é composto, o que me deixa um pouco nervoso.

Portanto, o raciocínio não era tão racional quanto muitas das respostas aqui parecem sugerir. Mas todos somos bons em apresentar razões racionais após decisões internas (e até Bloch pode estar propenso a isso).

Na verdade, 37 funcionaria muito bem! z: = 37 * x pode ser calculado como y := x + 8 * x; z := x + 4 * y. As duas etapas correspondem a uma instrução LEA x86, portanto, isso é extremamente rápido.

De fato, a multiplicação com o primo 73 ainda maior pode ser feita na mesma velocidade, configurando y := x + 8 * x; z := x + 8 * y.

Usar 73 ou 37 (em vez de 31) pode ser melhor, porque leva a um código mais denso : As duas instruções LEA levam apenas 6 bytes vs. 7 bytes para mover + shift + subtrair para a multiplicação por 31. Uma ressalva possível é que as instruções LEA de três argumentos usadas aqui se tornaram mais lentas na arquitetura Sandy bridge da Intel, com uma latência aumentada de 3 ciclos.

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

Neil Coffey explica por que o 31 é usado na solução do problema .

Basicamente, o uso de 31 fornece uma distribuição de probabilidade de bits mais uniforme para a função hash.

No JDK-4045622 , onde Joshua Bloch descreve os motivos pelos quais essa (nova) String.hashCode()implementação específica foi escolhida

A tabela abaixo resume o desempenho das várias funções de hash descritas acima, para três conjuntos de dados:

1) Todas as palavras e frases com entradas no 2º Dicionário Livre Internacional da Merriam-Webster (311.141 cordas, comprimento médio de 10 caracteres).

2) Todas as strings em / bin / , / usr / bin / , / usr / lib / , / usr / ucb / e / usr / openwin / bin / * (66.304 strings, com comprimento médio de 21 caracteres).

3) Uma lista de URLs reunidos por um rastreador da Web que funcionou por várias horas na noite passada (28.372 strings, com comprimento médio de 49 caracteres).

A métrica de desempenho mostrada na tabela é o "tamanho médio da cadeia" em todos os elementos da tabela de hash (ou seja, o valor esperado do número de chaves se compara à procura de 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, fica claro que todas as funções, exceto a atual função Java e as duas versões quebradas da função de Weinberger, oferecem desempenho excelente, quase indistinguível. Suponho firmemente que esse desempenho é essencialmente o "ideal teórico", que é o que você obteria se usasse um gerador de números aleatórios verdadeiro no lugar de uma função hash.

Eu descartaria a função WAIS, pois sua especificação contém páginas de números aleatórios e seu desempenho não é melhor do que qualquer uma das funções muito mais simples. Qualquer uma das seis funções restantes parece ser uma excelente opção, mas precisamos escolher uma. Suponho que descartar a variante de Vo e a função de Weinberger por causa de sua complexidade adicional, embora menor. Dos quatro restantes, eu provavelmente selecionaria P (31), pois é o mais barato para calcular em uma máquina RISC (porque 31 é a diferença de duas potências de duas). P (33) é igualmente barato de calcular, mas seu desempenho é marginalmente pior e 33 é composto, o que me deixa um pouco nervoso.

Josh

Bloch não entra nisso, mas a lógica que sempre ouvi / acreditei é que essa é a álgebra básica. Os hashes se resumem às operações de multiplicação e módulo, o que significa que você nunca deseja usar números com fatores comuns, se puder ajudá-lo. Em outras palavras, números relativamente primos fornecem uma distribuição uniforme de respostas.

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

• módulo do tipo de dados em que você o coloca (2 ^ 32 ou 2 ^ 64)
• módulo da contagem de bucket em sua hashtable (varia. Em java costumava ser primo, agora 2 ^ n)
• multiplique ou mude por um número mágico na sua função de mixagem
• O valor de entrada

Você realmente só consegue controlar alguns desses valores; portanto, é necessário um cuidado extra.

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

O objetivo da cadeia de hash é

• exclusivo (deixe o operador ^no documento de cálculo de código de hash, ele ajuda exclusivo)
• custo barato para calcular

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

Multiplicar 31 é << 5 e subtrai-se, portanto, precisa de recursos baratos.

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

Isso ocorre porque 31 possui uma boa propriedade - sua multiplicação pode ser substituída por um deslocamento bit a bit mais rápido que a multiplicação padrão:

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