7

Em Java, o código hash para um objeto String é computado como

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

usando aritmética de inteiros, onde s[i] é o i-ésimo caracter da string, n é o comprimento da string, e ^ indica exponenciação.

Por que 31 é usado como multiplicador?

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

Fonte

4
  • Há uns anos, eu já vi críticas quanto a escolha desse número, que alegam ter sido uma escolha ruim. Vou tentar procurar o link. Commented 2/01/2019 às 16:59
  • @VictorStafusa Incluí o link da pergunta no SOen. De fato uma outra pergunta linkada lá diz que o Java usou por razões de performance hoje desnecessárias e sugere números maiores para futuras implementações de hashCode().
    – Piovezan
    Commented 2/01/2019 às 17:07
  • dzone.com/articles/… Commented 2/01/2019 às 17:23
  • Há críticas ao artigo nos respectivos comentários. Tem que digerir bem o conteúdo deles para concluir alguma coisa. Criticam a afirmação de que usar strings como chaves em HashMaps deixa a aplicação sujeita a ataques de DoS.
    – Piovezan
    Commented 2/01/2019 às 18:08

2 Respostas 2

5

Geralmente o código hash é usado com chave para tabelas de espalhamento, os chamados dicionários. É comum que o valor máximo de códigos possíveis seja guardado em 32 bits, então faz sentido usar o múltiplo máximo de 32 e o primo inferior imediato é 31. Não que precise usar todos os códigos, mas desse número pode-se derivar o índice mais apropriado de acordo com a quantidade de buckets possíveis naquele espalhamento específico assim dando uma boa distribuição.

Conforme comentários, hoje considera-se que há números melhores (maiores), mas até onde eu sei o motivo da escolha inicial era esse. Um número menor poderia gerar colisão de códigos muito mais facilmente. Um maior realmente é melhor, mas a diferença de ganho não é tão grande assim, já um menor fica bem pior.

Em algumas plataformas uma operação de shift de certos números é barata, em outras não é, em alguns casos há otimização para alguns números, como é o caso do 31 que pode ser usado (é um shift e uma subtração simples).

Dá para dizer que não é um número bem pensado, não foi feita uma avaliação profunda, algo que tem uma justificativa sensacional :)

Uma comparação foi feita no SOen. Parece que certos números dão no mesmo, mas note que outras observações precisam ser feitas, não pode se tomar a análise em isolado. Ali não mostra outros problemas de cada número.

Coloquei no GitHub para referência futura.

3
  • 1
    Não acho que tenha relação com o número de bits, acredito que isso é apenas uma coincidência. Vou ver se acho algum link que explique isso. Commented 2/01/2019 às 17:01
  • Eu lembro do quesito da primalidade, mas não lembro da relação com a bitagem do inteiro Commented 2/01/2019 às 17:13
  • @VictorStafusa vê aí, eu respondi a motivação que eu sei, até entendo que não seja um bom número, mas pelo que sei foi ingenuamente pensado por causa disto, mas realmente não tenho uma fonte confiável sobre isso.
    – Maniero
    Commented 3/01/2019 às 10:16
1

Joshua Bloch, Um dos desenvolvedores da plataforma Java, deu uma boa explicação no seu livro "Effective Java" (2nd edition):

O valor 31 foi escolhido porque é um primo ímpar. Se fosse par e a multiplicação resultasse em overflow, informação seria perdida, já que multiplicação por 2 é equivalente a shifting. A vantagem de usar um primo é menos clara, mas é tradicional. Uma boa propriedade de 31 é que a multiplicação pode ser substituída por um shift e uma subtração para obter melhor performance:

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

VM's modernas fazem esse tipo de otimização automaticamente.

O livro é de 2008 e de lá para cá podem ter surgido novas ideias de como fazer hashes melhores, mas pelo menos essa é uma resposta de um dos autores da plataforma.

Você deve fazer log-in para responder a esta pergunta.

Esta não é a resposta que você está procurando? Pesquise outras perguntas com a tag .