Por que o hashCode () da String não é 0?

Eu observei no código-fonte Java 6 para String que hashCode armazena apenas valores diferentes de 0. A diferença no desempenho é exibida pelo seguinte trecho:

public class Main{ static void test(String s) { long start = System.currentTimeMillis(); for (int i = 0; i < 10000000; i++) { s.hashCode(); } System.out.format("Took %d ms.%n", System.currentTimeMillis() - start); } public static void main(String[] args) { String z = "Allocator redistricts; strict allocator redistricts strictly."; test(z); test(z.toUpperCase()); } } 

Executar isto em ideone.com fornece a seguinte saída:

 Took 1470 ms. Took 58 ms. 

Então minhas perguntas são:

  • Por que o hashCode () da String não é 0?
  • Qual é a probabilidade de uma string Java ser hashes para 0?
  • Qual é a melhor maneira de evitar a penalidade de desempenho de recalcular o valor de hash toda vez que as cadeias que hash para 0?
  • Essa é a melhor maneira de armazenar valores em cache? (ou seja, armazenar todos, exceto um?)

Para sua diversão, cada linha aqui é uma string que contém 0:

 pollinating sandboxes amusement & hemophilias schoolworks = perversive electrolysissweeteners.net constitutionalunstableness.net grinnerslaphappier.org BLEACHINGFEMININELY.NET WWW.BUMRACEGOERS.ORG WWW.RACCOONPRUDENTIALS.NET Microcomputers: the unredeemed lollipop... Incentively, my dear, I don't tessellate a derangement. A person who never yodelled an apology, never preened vocalizing transsexuals. 

Você está se preocupando com nada. Aqui está uma maneira de pensar sobre esse problema.

Suponha que você tenha um aplicativo que não faça nada além de ficar esperando hashing de Strings durante todo o ano. Vamos supor que sejam necessárias mil cadeias de caracteres, todas em memory, chamadas hashCode () repetidamente de modo round-robin, um milhão de vezes, depois, outras mil novas cadeias de caracteres e novamente.

E suponha que a probabilidade de o código hash de uma string ser zero fosse, na verdade, muito maior que 1/2 ^ 32. Tenho certeza que é um pouco maior que 1/2 ^ 32, mas vamos dizer que é muito pior do que isso, como 1/2 ^ 16 (a raiz quadrada! Agora é muito pior!).

Nessa situação, você tem mais a ganhar com os engenheiros da Oracle, melhorando como os códigos hash dessas sequências são armazenados em cache do que qualquer outra pessoa viva. Então você escreve para eles e pede para eles consertarem. E eles trabalham sua mágica de forma que sempre que s.hashCode () for zero, ele retorna instantaneamente (até a primeira vez! Uma melhoria de 100%!). E digamos que eles fazem isso sem degradar o desempenho em nenhum outro caso.

Viva! Agora seu aplicativo é … vamos ver … 0.0015% mais rápido!

O que costumava levar um dia inteiro agora leva apenas 23 horas, 57 minutos e 48 segundos!

E lembre-se, montamos o cenário para dar todo o benefício possível da dúvida, muitas vezes a um grau ridículo.

Isso parece valer a pena para você?

EDIT: desde postar isso há algumas horas atrás, eu deixei um dos meus processadores correr solta à procura de frases de duas palavras com zero códigos de hash. Até agora, surgiu: zorillo bequirtle, schtoff cronogrammic, clusister contuso, organzine creashaks, boulderhead drumwood, exercitável eletroanalítico, e favosely nonconstruable. Isto está fora de cerca de 2 ^ 35 possibilidades, então com uma distribuição perfeita, nós esperamos ver apenas 8. Claramente, quando terminarmos, teremos algumas vezes isso, mas não muito mais do que isso. O que é mais significativo é que eu agora tenho alguns nomes de bandas / álbuns interessantes! Não é justo roubar!

Ele usa 0 para indicar “ainda não trabalhei com o hashcode”. A alternativa seria usar um sinalizador booleano separado, que ocuparia mais memory. (Ou para não armazenar em cache o código hash, claro.)

Não espero muitos hash de strings para 0; sem dúvida, faria sentido para a rotina de hash evitar deliberadamente 0 (por exemplo, traduzir um hash de 0 para 1 e armazenar em cache isso). Isso aumentaria as colisões, mas evitaria a repetição. É tarde demais para fazer isso agora, já que o algoritmo String hashCode é explicitamente documentado.

Quanto a se esta é uma boa idéia em geral: é um mecanismo de cache certamente eficiente, e pode ser melhor ainda com uma mudança para evitar rehashing valores que acabam com um hash de 0. Pessoalmente, eu estaria interessado em ver os dados que levaram a Sun a acreditar que isso valeria a pena, em primeiro lugar – está ocupando 4 bytes extras para cada string já criada, no entanto, muitas vezes ou raramente é fragmentada, eo único benefício é para cadeias de caracteres que são mais de uma vez .

EDIT: Como KevinB aponta em um comentário em outro lugar, a sugestão de “evitar 0” acima pode ter um custo líquido porque ajuda um caso muito raro , mas requer uma comparação extra para cada cálculo de hash.

Eu acho que há algo importante que as outras respostas até agora estão faltando: o valor zero existe para que o mecanismo de cache de hashCode funcione de forma robusta em um ambiente multi-threaded.

Se você tivesse duas variables, como o próprio cachedHashCode e um booleano isHashCodeCalculated para indicar se o cachedHashCode havia sido calculado, você precisaria da synchronization de threads para que as coisas funcionassem em um ambiente multithread. E synchronization seria ruim para o desempenho, especialmente porque Strings são muito comumente reutilizados em vários segmentos.

Meu entendimento do modelo de memory Java é um pouco superficial, mas aqui está mais ou menos o que está acontecendo:

  1. Quando vários segmentos acessam uma variável (como o hashCode em cache), não há garantia de que cada thread verá o valor mais recente. Se uma variável começa em zero, então A atualiza (define para um valor diferente de zero), então o segmento B o lê logo em seguida, o encadeamento B ainda pode ver o valor zero.

  2. Há outro problema em acessar valores compartilhados de vários threads (sem synchronization) – você pode acabar tentando usar um object que foi parcialmente inicializado (construir um object não é um processo atômico). Leituras e gravações multi-thread de primitivos de 64 bits como longs e doubles não são necessariamente atômicas, então se dois threads tentarem ler e alterar o valor de um long ou double, um thread pode acabar vendo algo estranho e parcialmente setado . Ou algo assim de qualquer maneira. Existem problemas semelhantes se você tentar usar duas variables ​​juntas, como cachedHashCode e isHashCodeCalculated – um thread pode facilmente aparecer e ver a versão mais recente de uma dessas variables, mas uma versão mais antiga de outra.

  3. A maneira usual de contornar esses problemas de multi-threading é usar a synchronization. Por exemplo, você poderia colocar todo o access ao hashCode em cache dentro de um bloco sincronizado, ou você poderia usar a palavra-chave volátil (embora tenha cuidado com isso porque a semântica é um pouco confusa).

  4. No entanto, a synchronization desacelera as coisas. Má idéia para algo como uma string hashCode. As strings são frequentemente usadas como chaves no HashMaps, então você precisa do método hashCode para ter um bom desempenho, inclusive em ambientes multi-threaded.

  5. Primitivos Java que são de 32 bits ou menos, como int, são especiais. Ao contrário, digamos, de um valor longo (de 64 bits), você pode ter certeza de que nunca lerá um valor parcialmente inicializado de um int (32 bits). Quando você lê um int sem synchronization, não pode ter certeza de que obterá o valor definido mais recente, mas pode ter certeza de que o valor obtido é um valor que foi explicitamente definido em algum ponto por seu thread ou outro segmento.

O mecanismo de armazenamento em cache do hashCode em java.lang.String é configurado para confiar no ponto 5 acima. Você pode entender melhor olhando para a fonte de java.lang.String.hashCode (). Basicamente, com vários encadeamentos chamando hashCode de uma só vez, hashCode pode acabar sendo calculado várias vezes (se o valor calculado for zero ou se vários encadeamentos chamarem hashCode de uma vez e ambos virem um valor zero em cache), mas você pode ter certeza que hashCode () sempre retornará o mesmo valor. Então, é robusto e tem desempenho também (porque não há synchronization para atuar como um gargalo em ambientes multiencadeados).

Como eu disse, o meu entendimento do modelo de memory Java é um pouco superficial, mas tenho certeza de que tenho a essência do código acima. Em última análise, é uma linguagem muito inteligente para armazenar em cache o hashCode sem a sobrecarga da synchronization.

0 não é armazenado em cache, pois a implementação interpreta um valor em cache de 0 como “valor em cache ainda não inicializado”. A alternativa teria sido usar um java.lang.Integer , pelo qual null implicava que o valor ainda não estava em cache. No entanto, isso significaria uma sobrecarga de armazenamento adicional.

Em relação à probabilidade de um código hash de String ser computado como 0, eu diria que a probabilidade é bem baixa e pode acontecer nos seguintes casos:

  • O String está vazio (embora recomputar esse código de hash toda vez é efetivamente O (1)).
  • Um estouro ocorre pelo qual o código hash calculado final é 0 ( eg Integer.MAX_VALUE + h(c1) + h(c2) + ... h(cn) == 0 ).
  • O String contém apenas caracteres Unicode 0. É muito pouco provável que seja um caractere de controle sem significado, exceto no “mundo da fita de papel” (!):

Da Wikipedia :

O código 0 (nome de código ASCII NUL) é um caso especial. Na fita de papel, é o caso quando não há furos. É conveniente tratar isso como um caractere de preenchimento, sem qualquer significado .

Esta é uma boa pergunta relacionada a uma vulnerabilidade de segurança .

“Ao fazer hash de uma string, Java também armazena em cache o valor hash no atributo hash, mas somente se o resultado for diferente de zero. Assim, o valor zero alvo é particularmente interessante para um atacante, pois impede o cache e força o re-hashing.”

  • Por que o hashCode () da String não é 0?

O valor zero é reservado como significando “o código hash não é armazenado em cache”.

  • Qual é a probabilidade de uma string Java ser hashes para 0?

De acordo com o Javadoc, a fórmula para o hashcode de uma String é:

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

using int arithmetic, onde s[i] é o i caractere da string e n é o tamanho da string. (O hash da String vazia é definido como zero como um caso especial.)

Minha intuição é que a function hashcode como acima fornece uma distribuição uniforme de valores de hash String no intervalo de valores int . Uma propagação uniforme que significaria que a probabilidade de uma sequência de caracteres gerada aleatoriamente para zero era 1 em 2 ^ 32.

  • Qual é a melhor maneira de evitar a penalidade de desempenho de recalcular o valor de hash toda vez que as cadeias que hash para 0?

A melhor estratégia é ignorar o problema. Se você está repetindo repetidamente o mesmo valor de String, há algo de estranho no seu algoritmo.

  • Essa é a melhor maneira de armazenar valores em cache? (ou seja, armazenar todos, exceto um?)

Este é um espaço versus tempo trade-off. AFAIK, as alternativas são:

  • Adicione um sinalizador em cached a cada object String, fazendo com que cada String Java leve uma palavra extra.

  • Use o bit superior do membro hash como sinalizador em cache. Dessa forma, você pode armazenar em cache todos os valores de hash, mas você só tem metade dos valores possíveis de hash de String.

  • Não armazene hashcodes em Strings.

Eu acho que os projetistas de Java fizeram a escolha certa para o Strings, e tenho certeza que eles fizeram perfis extensivos que confirmam a solidez de suas decisões. No entanto, isso não significa que essa sempre seria a melhor maneira de lidar com o armazenamento em cache.

(Observe que há dois valores de string “comuns” que são zero a zero; a String vazia e a String consistem em apenas um caractere NUL. No entanto, o custo de calcular os hashcodes para esses valores é pequeno comparado com o custo de calcular hashcode para um valor típico de String.)

Bem pessoal, ele mantém 0 porque se ele for de comprimento zero, ele terminará como zero de qualquer maneira.

E não demorou muito para descobrir que o len é zero e assim deve ser o hashcode.

Então, para o seu código de revisão! Aqui está em tudo o que é a glória do Java 8:

  public int hashCode() { int h = hash; if (h == 0 && value.length > 0) { char val[] = value; for (int i = 0; i < value.length; i++) { h = 31 * h + val[i]; } hash = h; } return h; } 

Como você pode ver, isso sempre retornará um zero rápido se a string estiver vazia:

  if (h == 0 && value.length > 0) ... 

A sugestão “evitar 0” parece apropriada para recomendar como melhor prática, pois ajuda um problema genuíno (degradação de desempenho seriamente inesperada em casos construtíveis que podem ser fornecidos pelo invasor) pelo custo escasso de uma operação de ramificação antes de uma gravação. Há alguma ‘degradação de desempenho inesperada’ restante que pode ser exercida se as únicas coisas entrarem em um hash definido para o valor ajustado especial. Mas isso é, na pior das hipóteses, uma degradação de 2x em vez de ilimitada.

É claro que a implementação do String não pode ser alterada, mas não há necessidade de perpetuar o problema.