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

StackOverflow https://stackoverflow.com/questions/785091

  •  16-09-2019
  •  | 
  •  

Question

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

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

Y a-t-il des circonstances (dire la version JVM, fournisseur, etc.) en vertu de laquelle l'expression suivante évaluera false? 

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

Mise à jour # 1: Si vous prétendez que la réponse est « oui, il y a de telles circonstances » - alors s'il vous plaît donner un exemple concret quand « Ceci est une chaîne Java » .hashCode ()! = 586653468. Essayez d'être aussi précis / concret que possible.

Mise à jour n ° 2: Nous savons tous que compter sur les détails de mise en œuvre de hashCode () est mauvais en général. Cependant, je parle spécifiquement de String.hashCode () - donc s'il vous plaît garder la réponse concentrée à String.hashCode (). Object.hashCode () est totalement hors de propos dans le contexte de cette question.

Était-ce utile?

La solution

Je vois que la documentation aussi loin que Java 1.2.

Il est vrai que en général vous ne devriez pas compter sur une mise en œuvre du code de hachage restant le même, il est un comportement maintenant documenté pour java.lang.String, donc changer compterait comme la rupture des contrats existants.

Dans la mesure du possible, vous ne devriez pas compter sur les codes de hachage reste la même dans les versions, etc - mais dans mon esprit java.lang.String est un cas particulier simplement parce que l'algorithme a PRECISEE ... tant que vous êtes prêt à abandonner la compatibilité avec les versions avant que l'algorithme a été spécifié, bien sûr.

Autres conseils

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

  

Dans 1.0.x et 1.1.x JDK la hashCode   fonction pour les longues chaînes travaillées par   échantillonnage chaque caractère nième. Cette   assez bien garantis que vous auriez   de nombreuses chaînes de hachage à la même   valeur, ce qui ralentit Hashtable   Chercher. Dans la fonction JDK 1.2 a   été amélioré pour multiplier le résultat   jusqu'à présent par 31 puis ajoutez la prochaine   caractère en séquence. C'est un   peu plus lent, mais il est beaucoup mieux   en évitant les collisions.   Source: http://mindprod.com/jgloss/hashcode.html

Quelque chose de différent, parce que vous semblez avoir besoin d'un numéro: Pourquoi ne pas utiliser CRC32 ou MD5 de hashcode et vous êtes bon pour aller - pas de discussions et pas de soucis du tout ...

Vous ne devez pas compter sur un code de hachage étant égale à une valeur spécifique. Juste obtenir des résultats cohérents au sein de la même exécution. Les API docs disent ce qui suit:

  

Le contrat général de hashCode est:

     
      
  • Chaque fois qu'il est invoqué sur le même objet plus d'une fois lors d'une exécution d'une application Java, la méthode hashCode doit retourner systématiquement le même entier, n'a fourni aucune information utilisé dans des comparaisons sur l'égal objet est modifié. Cet entier ne doit pas rester cohérente d'une exécution d'une application à une autre exécution de la même application.
    •   

EDIT Depuis la javadoc pour String.hashCode () spécifie comment un code de hachage de chaîne est calculée, toute violation de ce serait contraire à la spécification API publique.

Comme dit plus haut, en général, vous ne devriez pas compter sur le code de hachage d'une classe reste la même. Notez que même les exécutions ultérieures du même application sur les mêmes VM peut produire des valeurs de hachage différentes. AFAIK la fonction de hachage de JVM Sun calcule le même hachage sur chaque course, mais ce n'est pas garanti.

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

java.lang.String est est (maintenant) documenté, vous pouvez probablement compter sur un cas particulier, comme l'algorithme de son hashCode () qui. Je considère toujours une mauvaise pratique. Si vous avez besoin d'un algorithme de hachage avec des propriétés spéciales, documentées, il suffit d'écrire un: -.)

Une autre (!) Question à vous préoccuper de l'évolution possible de la mise en œuvre entre les premières versions / fin de Java. Je ne crois pas que les détails de mise en œuvre sont définies dans la pierre, et ainsi potentiellement une mise à niveau à un futur version Java pourrait causer des problèmes.

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

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

Si vous êtes inquiet au sujet des changements et peut-être des machines virtuelles de façon incompatible, il suffit de copier l'implémentation hashcode existante dans votre classe utilitaire, et l'utiliser pour générer vos hashcodes.

Juste pour répondre à votre question et de ne pas poursuivre les discussions. La mise en œuvre Apache Harmony JDK semble utiliser un algorithme différent, au moins, il semble tout à fait 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;
}

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

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

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

Ceci est la mise en œuvre 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;
}

Collisions en hashcode sont inévitables. Par exemple, les chaînes « Ea » et « FB » donnent le même hashcode que 2236

Licencié sous: CC-BY-SA avec attribution
Non affilié à StackOverflow
scroll top