Cohérence de hashCode () sur une chaîne Java

134

La valeur hashCode d'une chaîne Java est calculée comme suit (String.hashCode () ):

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

Existe-t-il des circonstances (par exemple, la version JVM, le fournisseur, etc.) dans lesquelles l'expression suivante sera évaluée à false?

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

Mise à jour n ° 1: Si vous prétendez que la réponse est "oui, il y a de telles circonstances" - alors veuillez donner un exemple concret de quand "Ceci est une chaîne Java" .hashCode ()! = 586653468. Essayez d'être aussi spécifique / concret que possible.

Mise à jour # 2: Nous savons tous que se fier aux détails d'implémentation de hashCode () est mauvais en général. Cependant, je parle spécifiquement de String.hashCode () - veuillez donc garder la réponse concentrée sur String.hashCode (). Object.hashCode () est totalement hors de propos dans le contexte de cette question.

knorv
la source
2
Avez-vous réellement besoin de cette fonctionnalité? Pourquoi avez-vous besoin de la valeur précise?
Brian Agnew
26
@Brian: J'essaye de comprendre le contrat de String.hashCode ().
knorv
3
@Knorv Il n'est pas nécessaire de comprendre exactement comment cela fonctionne - il est plus important de comprendre le contrat et sa signification ultérieure.
mP.
45
@mP: Merci pour votre contribution, mais je suppose que c'est à moi de décider.
knorv
pourquoi ont-ils donné au premier personnage la plus grande puissance? lorsque vous voulez l'optimiser pour la vitesse afin de conserver des calculs supplémentaires, vous stockez la puissance du précédent, mais le précédent serait du dernier caractère au premier. cela signifie qu'il y aurait également des erreurs de cache. n'est-il pas plus efficace d'avoir un algorithme de: s [0] + s [1] * 31 + s [2] * 31 ^ 2 + ... + s [n-1] * 31 ^ [n-1 ]?
développeur android

Réponses:

101

Je peux voir cette documentation aussi loin que Java 1.2.

S'il est vrai qu'en général, vous ne devriez pas compter sur une implémentation de code de hachage qui reste la même, c'est maintenant un comportement documenté pour java.lang.String, donc le changer compterait comme la rupture des contrats existants.

Dans la mesure du possible, vous ne devriez pas vous fier à ce que les codes de hachage restent les mêmes d'une version à l'autre, etc. - mais dans mon esprit, java.lang.Stringc'est un cas spécial simplement parce que l'algorithme a été spécifié ... tant que vous êtes prêt à abandonner la compatibilité avec les versions antérieures à la l'algorithme a été spécifié, bien sûr.

Jon Skeet
la source
7
Le comportement documenté de String a été spécifié depuis Java 1.2 Dans la v1.1 de l'API, le calcul du code de hachage n'est pas spécifié pour la classe String.
Martin OConnor
Dans ce cas, nous ferions mieux d'écrire nos propres codes de hachage ight matey?
Felype
@Felype: Je ne sais vraiment pas ce que vous essayez de dire ici, j'en ai peur.
Jon Skeet
@JonSkeet Je veux dire, dans ce cas, nous pouvons peut-être écrire notre propre code pour générer notre propre hachage, pour accorder la portabilité. C'est ça?
Felype
@Felype: On ne sait pas du tout de quel type de portabilité vous parlez, ni même ce que vous entendez par «dans ce cas» - dans quel scénario spécifique? Je suppose que vous devriez poser une nouvelle question.
Jon Skeet
18

J'ai trouvé quelque chose à propos de JDK 1.0 et 1.1 et> = 1.2:

Dans JDK 1.0.x et 1.1.x, la fonction hashCode pour les chaînes longues fonctionnait en échantillonnant chaque nième caractère. Cela garantissait assez bien que vous auriez beaucoup de hachage de chaînes à la même valeur, ralentissant ainsi la recherche de Hashtable. Dans JDK 1.2, la fonction a été améliorée pour multiplier le résultat jusqu'à présent par 31 puis ajouter le caractère suivant dans la séquence. C'est un peu plus lent, mais c'est beaucoup mieux pour éviter les collisions. Source: http://mindprod.com/jgloss/hashcode.html

Quelque chose de différent, car vous semblez avoir besoin d'un numéro: que diriez-vous d'utiliser CRC32 ou MD5 au lieu du hashcode et vous êtes prêt à partir - pas de discussions et pas de soucis du tout ...

René
la source
8

Vous ne devez pas vous fier à un code de hachage égal à une valeur spécifique. Juste qu'il renverra des résultats cohérents dans la même exécution. La documentation de l'API dit ce qui suit:

Le contrat général de hashCode est:

  • Chaque fois qu'elle est appelée sur le même objet plus d'une fois lors d'une exécution d'une application Java, la méthode hashCode doit systématiquement renvoyer le même entier, à condition qu'aucune information utilisée dans les comparaisons égales sur l'objet ne soit modifiée. Cet entier n'a pas besoin de rester cohérent d'une exécution d'une application à une autre exécution de la même application.

EDIT Puisque le javadoc pour String.hashCode () spécifie comment le code de hachage d'un String est calculé, toute violation de ceci violerait la spécification de l'API publique.

Martin OConnor
la source
1
Votre réponse est valide, mais ne répond pas à la question spécifique posée.
knorv
6
C'est le contrat de code de hachage général - mais le contrat spécifique pour String donne des détails sur l'algorithme et remplace effectivement ce contrat général IMO.
Jon Skeet
4

Comme indiqué ci-dessus, en général, vous ne devez pas vous fier au code de hachage d'une classe qui reste le même. Notez que même les exécutions ultérieures du même application sur la même machine virtuelle peuvent produire des valeurs de hachage différentes. AFAIK la fonction de hachage de Sun JVM calcule le même hachage à chaque exécution, mais ce n'est pas garanti.

Notez que ce n'est pas théorique. La fonction de hachage pour java.lang.String a été modifiée dans JDK1.2 (l'ancien hachage avait des problèmes avec les chaînes hiérarchiques comme les URL ou les noms de fichiers, car il avait tendance à produire le même hachage pour les chaînes qui ne différaient qu'à la fin).

java.lang.String est un cas particulier, car l'algorithme de son hashCode () est (maintenant) documenté, vous pouvez donc probablement vous y fier. Je considère toujours que c'est une mauvaise pratique. Si vous avez besoin d'un algorithme de hachage avec des propriétés spéciales et documentées, écrivez-en un :-).

sleske
la source
4
Mais l'algorithme était-il spécifié dans la documentation avant JDK 1.2? Sinon, c'est une situation différente. L'algorithme est maintenant défini dans la documentation, donc le changer serait un changement radical dans un contrat public.
Jon Skeet
(Je m'en souviens comme 1.1.) L'algorithme original (plus pauvre) a été documenté. Incorrectement. L'algorithme documenté a en fait lancé une ArrayIndexOutOfBoundsException.
Tom Hawtin - tackline
@Jon Skeet: Ah, je ne savais pas que l'algorithme de String.hashCode () est documenté. Bien sûr, cela change les choses. Mis à jour mon commentaire.
sleske
3

Un autre (!) Problème à craindre est le changement possible d'implémentation entre les versions antérieures / tardives de Java. Je ne pense pas que les détails d'implémentation soient gravés dans la pierre, et donc potentiellement une mise à niveau vers une future version Java pourrait causer des problèmes.

En bout de ligne, je ne compterais pas sur la mise en œuvre de hashCode().

Vous pouvez peut-être mettre en évidence le problème que vous essayez réellement de résoudre en utilisant ce mécanisme, ce qui mettra en évidence une approche plus appropriée.

Brian Agnew
la source
1
Merci pour votre réponse. Pouvez-vous donner des exemples concrets de quand "Ceci est une chaîne Java" .hashCode ()! = 586653468?
knorv
1
Non désolé. Mon point est que tout ce que vous testez peut fonctionner comme vous le souhaitez. Mais ce n'est toujours pas une garantie. Donc, si vous travaillez sur un projet (disons) à court terme où vous avez le contrôle de la VM, etc., alors ce qui précède peut fonctionner pour vous. Mais vous ne pouvez pas vous y fier dans le monde entier.
Brian Agnew
2
"une mise à niveau vers une future version Java pourrait poser des problèmes". Une mise à niveau vers une future version de Java pourrait supprimer complètement la méthode hashCode. Ou faites-le toujours renvoyer 0 pour les chaînes. Ce sont des changements incompatibles pour toi. La question est de savoir si Sun ^ HOracle ^ HThe JCP le considérerait comme un changement radical et qu'il vaut donc la peine d'éviter. Puisque l'algorithme est dans le contrat, on espère qu'ils le feraient.
Steve Jessop
@SteveJessop bien, puisque les switchinstructions sur les chaînes se compilent en code reposant sur un code de hachage fixe particulier, les modifications apportées à Stringl'algorithme de code de hachage de 's briseraient définitivement le code existant…
Holger
3

Juste pour répondre à votre question et pour ne poursuivre aucune discussion. L'implémentation Apache Harmony JDK semble utiliser un algorithme différent, au moins il semble totalement différent:

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;
}

Harmonie Apache

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;
}

N'hésitez pas à le vérifier vous-même ...

René
la source
23
Je pense qu'ils sont simplement cool et qu'ils optimisent. :) "(multiplier << 5) - multiplier" est juste 31 * multiplicateur, après tout ...
dérouler le
Ok, était trop paresseux pour vérifier cela. Merci!
ReneS
1
Mais pour que ce soit clair de mon côté ... Ne vous fiez jamais au hashcode car le hashcode est quelque chose d'interne.
ReneS
1
que signifient les variables "offset", "count" et "hashCode"? Je suppose que "hashcode" est utilisé comme valeur en cache, pour éviter les calculs futurs, et que "count" est le nombre de caractères, mais quel est le "offset"? supposons que je souhaite utiliser ce code pour qu'il soit cohérent, étant donné une chaîne, que dois-je faire?
développeur android
1
@androiddeveloper Voilà une question intéressante - même si j'aurais dû la deviner, en fonction de votre nom d'utilisateur. D'après la documentation Android, il semble que le contrat soit le même: s[0]*31^(n-1) + s[1]*31^(n-2) + ... + s[n-1]sauf si je me trompe, c'est parce qu'Android utilise l'implémentation par Sun de l'objet String sans changement.
Kartik Chugh
2

Si vous vous inquiétez des modifications et éventuellement des machines virtuelles incompatibles, copiez simplement l'implémentation de hashcode existante dans votre propre classe d'utilitaire et utilisez-la pour générer vos hashcodes.

Sam Barnum
la source
J'allais dire ceci. Alors que les autres réponses répondent à la question, écrire une fonction hashCode distincte est probablement la solution appropriée au problème de knorv.
Nick
1

Le hashcode sera calculé en fonction des valeurs ASCII des caractères de la chaîne.

C'est l'implémentation dans la classe String est la suivante

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

Les collisions dans le hashcode sont inévitables. Par exemple, les chaînes "Ea" et "FB" donnent le même hashcode que 2236

Lourdes
la source