Consistência de hashCode () em uma sequência Java

134

O valor hashCode de uma String Java é calculado como ( String.hashCode () ):

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

Existem circunstâncias (por exemplo, versão da JVM, fornecedor etc.) sob as quais a expressão a seguir será avaliada como falsa?

boolean expression = "This is a Java string".hashCode() == 586653468

Atualização 1: se você afirmar que a resposta é "sim, existem circunstâncias" - forneça um exemplo concreto de quando "Esta é uma string Java" .hashCode ()! = 586653468. Tente ser o mais específico / concreto que possível.

Atualização 2: Todos sabemos que confiar nos detalhes da implementação de hashCode () é ruim em geral. No entanto, estou falando especificamente sobre String.hashCode () - portanto, mantenha a resposta focada em String.hashCode (). Object.hashCode () é totalmente irrelevante no contexto desta pergunta.

knorv
fonte
2
Você realmente precisa dessa funcionalidade? Por que você precisa do valor exato?
27411 Brian Agnew
26
@ Brian: Estou tentando entender o contrato de String.hashCode ().
knorv
3
@Knorv Não é necessário entender exatamente como ele funciona - é mais importante entender o contrato e seu significado posterior.
mP.
45
@ MP: Obrigado pela sua contribuição, mas acho que cabe a mim decidir.
knorv
por que eles deram ao primeiro personagem o maior poder? quando você quiser otimizá-lo em velocidade para preservar cálculos extras, você armazenaria a potência do anterior, mas o anterior seria do último caractere para o primeiro. isso significa que também haveria erros de cache. não é mais eficiente ter um algoritmo de: s [0] + s [1] * 31 + s [2] * 31 ^ 2 + ... + s [n-1] * 31 ^ [n-1 ]?
desenvolvedor android

Respostas:

101

Eu posso ver essa documentação já em Java 1.2.

Embora seja verdade que, em geral, você não deve confiar em uma implementação de código de hash permanecendo a mesma, agora é um comportamento documentado java.lang.String, portanto, alterá-lo contará como quebra de contratos existentes.

Sempre que possível, você não deve confiar em códigos de hash permanecendo o mesmo em todas as versões etc - mas na minha mente java.lang.Stringé um caso especial, simplesmente porque o algoritmo tenha sido especificado ... desde que você está disposto a abandonar a compatibilidade com versões anteriores à algoritmo foi especificado, é claro.

Jon Skeet
fonte
7
O comportamento documentado de String foi especificado desde Java 1.2 Na v1.1 da API, o cálculo do código de hash não é especificado para a classe String.
Martin OConnor
Nesse caso, é melhor escrevermos nossos próprios códigos de hash?
Felype
@Felype: Eu realmente não sei o que você está tentando dizer aqui, eu tenho medo.
Jon Skeet
@ JonSkeet Quero dizer, nesse caso, talvez possamos escrever nosso próprio código para gerar nosso próprio hash, para conceder portabilidade. É isso?
Felype
@Felype: Não está claro de que tipo de portabilidade você está falando, nem o que você quer dizer com "neste caso" - em que cenário específico? Eu suspeito que você deveria fazer uma nova pergunta.
precisa
18

Encontrei algo sobre o JDK 1.0 e 1.1 e> = 1.2:

No JDK 1.0.xe 1.1.x, a função hashCode para Strings longas trabalhava com amostragem de cada enésimo caractere. Isso garante que você tenha muitas strings hash no mesmo valor, diminuindo a velocidade da pesquisa do Hashtable. No JDK 1.2, a função foi aprimorada para multiplicar o resultado até agora por 31 e adicionar o próximo caractere em sequência. Isso é um pouco mais lento, mas é muito melhor para evitar colisões. Fonte: http://mindprod.com/jgloss/hashcode.html

Algo diferente, porque você parece precisar de um número: que tal usar o CRC32 ou MD5 em vez do código de hash e você está pronto - sem discussões e sem preocupações ...

ReneS
fonte
8

Você não deve confiar em um código de hash igual a um valor específico. Só que ele retornará resultados consistentes dentro da mesma execução. Os documentos da API dizem o seguinte:

O contrato geral do hashCode é:

  • Sempre que é invocado no mesmo objeto mais de uma vez durante a execução de um aplicativo Java, o método hashCode deve retornar consistentemente o mesmo número inteiro, desde que nenhuma informação usada em comparações iguais no objeto seja modificada. Esse número inteiro não precisa permanecer consistente de uma execução de um aplicativo para outra execução do mesmo aplicativo.

EDIT Como o javadoc para String.hashCode () especifica como o código de hash de uma String é calculado, qualquer violação disso violaria a especificação pública da API.

Martin OConnor
fonte
1
Sua resposta é válida, mas não aborda a pergunta específica feita.
knorv
6
Esse é o contrato geral de código de hash - mas o contrato específico para String fornece detalhes do algoritmo e substitui efetivamente esse contrato geral da IMO.
31516 Jon Skeet
4

Como dito acima, em geral você não deve confiar no código hash de uma classe que permanece o mesmo. Observe que mesmo execuções subsequentes do mesmo aplicativo na mesma VM podem produzir valores de hash diferentes. AFAIK, a função de hash da Sun JVM calcula o mesmo hash em cada execução, mas isso não é garantido.

Observe que isso não é teórico. A função hash para java.lang.String foi alterada no JDK1.2 (o hash antigo teve problemas com cadeias hierárquicas como URLs ou nomes de arquivos, pois tendia a produzir o mesmo hash para cadeias de caracteres que diferiam apenas no final).

java.lang.String é um caso especial, pois o algoritmo de seu hashCode () está (agora) documentado, portanto você provavelmente pode confiar nisso. Eu ainda consideraria uma prática ruim. Se você precisar de um algoritmo de hash com propriedades especiais documentadas, basta escrever um :-).

sleske
fonte
4
Mas o algoritmo foi especificado nos documentos antes do JDK 1.2? Caso contrário, é uma situação diferente. O algoritmo está agora estabelecido nos documentos, portanto, alterá-lo seria uma mudança de quebra em um contrato público.
31910 Jon Skeet
(Lembro-me como 1.1.) O algoritmo original (mais pobre) foi documentado. Incorretamente. O algoritmo documentado realmente lançou uma ArrayIndexOutOfBoundsException.
Tom Hawtin - tackline
@ Jon Skeet: Ah, não sabia que o algoritmo de String.hashCode () está documentado. Claro que isso muda as coisas. Atualizado meu comentário.
Sleske #
3

Outra questão (!) Com que se preocupar é a possível alteração de implementação entre as versões iniciais / tardias do Java. Não acredito que os detalhes da implementação estejam definidos, e potencialmente uma atualização para uma versão futura do Java pode causar problemas.

Resumindo, eu não confiaria na implementação de hashCode().

Talvez você possa destacar qual problema está realmente tentando resolver usando esse mecanismo, e isso destacará uma abordagem mais adequada.

Brian Agnew
fonte
1
Obrigado pela sua resposta. Você pode dar exemplos concretos de quando "Esta é uma string Java" .hashCode ()! = 586653468?
knorv
1
Desculpe. O que quero dizer é que tudo o que você testar pode funcionar da maneira que você deseja. Mas isso ainda não é garantia. Portanto, se você estiver trabalhando em um (digamos) projeto de curto prazo em que tenha controle da VM, etc., o acima poderá funcionar para você. Mas você não pode confiar nisso no mundo inteiro.
9139 Brian Agnew
2
"uma atualização para uma versão futura do Java pode causar problemas". Uma atualização para uma versão futura do Java pode remover completamente o método hashCode. Ou faça-o sempre retornar 0 para seqüências de caracteres. Isso é alterações incompatíveis para você. A questão é se a Sun ^ HOracle ^ HJCP consideraria uma mudança de quebra e, portanto, vale a pena evitar. Como o algoritmo está no contrato, espera-se que sim.
Steve Jessop
@SteveJessop bem, uma vez que switchas declarações sobre cordas compilar para código depender de um determinado código de hash fixo, muda para String's algoritmo de código hash iria quebrar o código existente ...
Holger
3

Apenas para responder sua pergunta e não continuar com nenhuma discussão. A implementação do Apache Harmony JDK parece usar um algoritmo diferente, pelo menos parece totalmente diferente:

Sun JDK

public int hashCode() {
    int h = hash;
    if (h == 0) {
        int off = offset;
        char val[] = value;
        int len = count;

        for (int i = 0; i < len; i++) {
            h = 31*h + val[off++];
        }
        hash = h;
    }
    return h;
}

Apache Harmony

public int hashCode() {
    if (hashCode == 0) {
        int hash = 0, multiplier = 1;
        for (int i = offset + count - 1; i >= offset; i--) {
            hash += value[i] * multiplier;
            int shifted = multiplier << 5;
            multiplier = shifted - multiplier;
        }
        hashCode = hash;
    }
    return hashCode;
}

Sinta-se livre para verificar você mesmo ...

ReneS
fonte
23
Eu acho que eles estão sendo legais e otimizando isso. :) "(multiplicador << 5) - multiplicador" é apenas 31 * multiplicador, afinal ...
descontraia
Ok, estava com preguiça de verificar isso. Obrigado!
Renes
1
Mas para deixar claro do meu lado ... Nunca confie no código de hash, porque o código de hash é algo interno.
Renes
1
quais são as variáveis ​​de "offset", "count" e "hashCode" significam? suponho que "hashcode" seja usado como um valor em cache, para evitar cálculos futuros, e que "count" seja o número de caracteres, mas qual é o "deslocamento"? suponha que eu queira usar esse código para que seja consistente, dada uma string, o que devo fazer com ele?
desenvolvedor Android
1
@androiddeveloper Agora, essa é uma pergunta interessante - embora eu devesse ter adivinhado, com base no seu nome de usuário. A partir dos documentos do Android , parece que o contrato é o mesmo: a s[0]*31^(n-1) + s[1]*31^(n-2) + ... + s[n-1]menos que eu esteja enganado, isso ocorre porque o Android usa a implementação da Sun do objeto String sem alterações.
Kartik Chugh
2

Se você estiver preocupado com alterações e possivelmente com VMs incompatíveis, copie a implementação de código de hash existente em sua própria classe de utilitário e use-a para gerar seus códigos de hash.

Sam Barnum
fonte
Eu ia dizer isso. Enquanto as outras respostas respondem à pergunta, escrever uma função hashCode separada é provavelmente a solução apropriada para o problema do knorv.
6111 Nick
1

O hashcode será calculado com base nos valores ASCII dos caracteres na String.

Esta é a implementação na classe String é a seguinte

public int hashCode() {
    int h = hash;
    if (h == 0 && value.length > 0) {
        hash = h = isLatin1() ? StringLatin1.hashCode(value)
                              : StringUTF16.hashCode(value);
    }
    return h;
}

Colisões no código hash são inevitáveis. Por exemplo, as cadeias "Ea" e "FB" fornecem o mesmo código hash que 2236

Lourdes
fonte