Test de la chaîne de l'égalité à l'aide de hashCode()

Est-il une raison pourquoi Java string ne peut pas être testé pour l'égalité à l'aide de sa méthode hashCode? Donc, en gros, au lieu de....

"hello".equals("hello")

Vous pouvez utiliser...

"hello".hashCode() == "hello".hashCode()

Ce serait utile car une fois qu'une chaîne est calculé, il est hashcode puis de les comparer une chaîne serait aussi efficace que la comparaison des int comme la chaîne met en cache le hashcode et il est fort probable que la chaîne est la chaîne de la piscine, de toute façon, si vous avez conçu de cette façon.

  • Votre réponse se trouve dans la documentation sur le equals() et hashcode() méthodes.
  • Et concernant l'efficacité énergétique: les regarder de plus près à la les chaînes que vous comparez. Je serai prêt à parier qu' > 50% diffèrent par leur premier caractère, et > 66% diffèrent dans leurs deux premiers caractères. Si vous avez réellement un très efficace en comparaison avec hashCode(), qui doit marcher à l'ensemble de la chaîne. De Plus, si vous utilisez des chaînes dans le constant pool, equals() vérifie d'abord de l'identité, qui donnera un coup de pied ceux tout de suite.
  • Il est vrai que le pire scénario est que les chaînes correspondent réellement, ce qui pourrait aussi être le scénario le plus courant. Vous avez également répondu à ma chaîne de performances de la question, tous les gains réalisés par une mise en commun des hashcode est fait déjà de l'exécution d'une instance de contrôle. Cheers!
  • Ce que je trouve étrange, c'est que l'actuelle Chaîne de mise en œuvre des caches de la hashCode, mais ne l'utilise pas dans equals(), même si ce serait un moyen rapide d'éliminer l'inégalité des chaînes dans de nombreux cas, un grand gain dans le (certes rares) cas où vous comparez des chaînes avec de longues identiques préfixes.
InformationsquelleAutor | 2009-09-23
  1. 37

    parce que: hashCodes de deux objets doivent être égales si les objets sont égaux, cependant, si les deux objets sont inégaux, le hashCode peut encore être égaux.

    (modifié d'après le commentaire)

    • +1, hashcodes ne pas garantir l'unicité - ils seulement essayer et de fournir moins de collisions
    • +1, mais une petite modification. hashCodes de deux objets DOIVENT être égales si les objets sont égaux, c'est spécifié dans le contrat de hashCode.
    • Court et la réponse correcte. Aussi faire quelque chose comme ça juste pour être aussi efficace que possible sonne un peu comme l'optimisation prématurée pour moi.
    • Serait-ce un problème si vous étiez l'essai contre la saisie de l'utilisateur par exemple. Si vous testiez les cordes dans un environnement contrôlé et peut garantir l'absence de collisions (tests unitaires), alors il vaudrait la peine s'il a marqué des améliorations de performances, mais comme kdgregory souligné ci-dessus, il ne le serait pas. Cheers!
    • En théorie, je suppose. Mais vous devez vérifier que vos chaînes ne donne pas de collisions de hachage. Et puis si plus tard, quelqu'un modifie le programme et ajoute une nouvelle corde, ils auraient à connaître pour vérifier si cela crée un hash collision, et, dans l'affirmative, ils seraient alors changer toutes les comparaisons. Vous feriez beaucoup mieux de créer un Enum ou céder votre propre identifiant unique pour chaque chaîne de caractères, plutôt que de compter sur les hashcodes de ne pas avoir de collisions fondamentalement hors de la chance.
    InformationsquelleAutor dstibbe
  2. 37

    Permettez-moi de vous donner un contre-exemple. Essayez ceci,

    public static void main(String[] args) {
    String str1 = "0-42L";
    String str2 = "0-43-";

    System.out.println("String equality: " + str1.equals(str2));
    System.out.println("HashCode eqauality: " + (str1.hashCode() == str2.hashCode()));
}

    Le résultat sur mon Java,

    String equality: false
HashCode eqauality: true
    • Est-ce une coïncidence que ces deux chaînes avec le code de hachage de collision sont si semblables? (c'est à dire, les trois premiers caractères sont les mêmes.) Ou sont les deux chaînes similaires également plus susceptibles d'avoir un code de hachage de collision?
    InformationsquelleAutor ZZ Coder
  3. 15

    comme beaucoup ont dit hashCode ne garantit pas l'unicité.
    en fait, il ne peut pas le faire pour une raison très simple.

    hashCode retourne un int, ce qui signifie qu'il y a 2^32 valeurs possibles (autour de 4,000,000,000), mais il y a sûrement plus de 2^32 possible des chaînes, ce qui signifie qu'au moins deux phrases ont le même hashcode valeur.

    ce qui est appelé Casier principe.

    • bonne réponse, pourrait avoir fait avec le savoir classer principe dans une récente interview
    • De façon plus que deux, si vous pensez à ce sujet. Si la longueur maximale d'une chaîne est de type Entier.MAX_VALUE, c'est à dire environ 2 milliards de dollars, et il y a 2^32 ~= 64 ko possible char valeurs, alors il ya (2^32)^(2^31) possible des chaînes de vs 2^32 valeurs de hachage, ce qui signifie qu'il existe (2^32)^(2^31) / (2^32) = (2^32)^(2^30) cordes pour tout code de hachage. Ce qui fait environ 10 ^ 9 milliards de dollars. c'est à dire un Nombre Très Grand.
    • 64 ko"? Ce n' ~= dire par là?
    • "Environ égal à". Les classiques symbole mathématique pour que isnot facilement entrés sur la plupart des claviers.
    • Deux, c'est tout ce que vous devez démontrer qu'il ne peut pas garantir l'unicité. évidemment, le nombre de collisions de hachage pour cordes est trop long pour tenir dans ce commentaire.
    • Tout à fait vrai. Je viens de trouver ça amusant de battre le sujet à la mort.

    InformationsquelleAutor Omry Yadan
  4. 8

    D'autres l'ont fait pourquoi il ne fonctionne pas. Donc je vais juste ajouter de l'additif que le gain serait minime de toute façon.

    Quand on compare deux chaînes de caractères en Java, la Chaîne est égale à la fonction vérifie d'abord si ils sont deux références pour le même objet. Si oui, il retourne immédiatement le vrai. Elle vérifie ensuite si les longueurs sont égales. Sinon, elle retourne false. Alors seulement sera-t-elle la comparaison caractère par caractère.

    Si vous êtes à la manipulation des données dans la mémoire, le même objet peut comparer rapidement la poignée de la "même" cas, et c'est un moyen rapide, umm, entier de 4 octets comparer, je pense. (Quelqu'un me corrige si j'ai de la longueur d'un objet poignée de mal.)

    Pour plus d'inégalités cordes, je serais prêt à parier de la longueur de comparer rapidement les trouve pas égaux. Si vous êtes à la comparaison de deux noms de choses, les clients, les villes, les produits, n'importe quoi, ils ont généralement de longueur inégale. Ainsi, un simple int de comparer rapidement dispose d'entre eux.

    Le pire des cas pour la performance va être deux de long, à l'identique, mais pas le même objet cordes. Alors, il doit faire l'objet poignée de comparer, de faux, de garder le contrôle. La longueur de comparer, de vrai, de garder le contrôle. Ensuite, caractère par caractère sur toute la longueur de la chaîne pour vérifier que oui, en effet, ils sont égaux tout le chemin à la fin.

    • excellente réponse
    • La bonne réponse. Cela aurait bénéficié de la mention de la stagiaire méthode qui fait de la stricte égalité de vérifier plus probable à la matière.
    • Point valide. Si les deux chaînes sont des littéraux de Chaîne, alors oui, leurs objets de comparer l'égalité. Si elles sont lues à partir d'une base de données ou la saisie de l'utilisateur, alors vous pourriez stagiaire de sorte que leurs objets de comparer l'égalité. Si ce n'est de la valeur dépend de la façon dont souvent vous de comparer les chaînes de caractères.
    • Il y a certains cas où l'on serait susceptible de faire de nombreuses comparaisons à l'encontre de longues chaînes de caractères qui peuvent être à peu près identique, et dans de tels cas, la pré-vérification des codes de hachage peut être utile. Dans de tels cas, cependant, le code à l'aide de cordes est libre de consulter le code de hachage avant de tester l'égalité.
    • Pour que cette aide, vous devez calculer le hash codes une fois et les mettre en cache, et vous devez être en train de faire des comparaisons à l'encontre de plusieurs fois la même chaîne. C'est plus de travail pour calculer les codes de hachage pour les deux chaînes de caractères que pour comparer deux chaînes de caractères: vous avez à examiner chaque caractère dans une chaîne pour calculer le code de hachage, et faire de l'arithmétique sur le dessus de cela. Donc, si vous comparez une chaîne de caractères une fois, vous auriez du faire plus de travail pour calculer le hachage qu'il faudrait juste faire la comparaison, et puis si le hachage qui sort de l'égalité, vous avez encore à faire la comparaison, il est donc ...
    • ... perdre/perdre. Si vous comparez plusieurs fois la même chaîne, et vous êtes de le comparer à d'autres chaînes de longueur égale, qui sont les mêmes pour la première quelques-nombre de caractères, puis en calculant la valeur de hachage pourrait aider. Franchement, c'est le genre d'optimisation qui est très dépendante sur les détails de mise en œuvre et la combinaison de données que vous avez. Vous auriez vraiment pu étudier les détails pour voir si cela peut aider ou nuire. BTW la mise en œuvre actuelle de java.lang.String ne cache hash-codes la première fois qu'ils en sont requis, de sorte que vous n'avez pas besoin de cache-toi à eux.
    • Mon point est que, parfois, le code qui est à l'aide de chaînes ont des connaissances spécialisées sur le contenu des autres chaînes, contre qui ils vont être comparativement, et dont le code est avec une telle connaissance peut parfois trouver des comparaisons de codes de hachage utile. Il est tout à fait raisonnable pour le code avec une telle connaissance de comparer chaîne des codes de hachage comme un prélude à la comparaison de leurs valeurs. Une telle base de hachage comparaisons appartiennent dans le code de la utilise les chaînes de caractères, si, plutôt que dans le String classe elle-même.
    • D'ailleurs, à moins que près de matches vont être de plus commun que de matchs, la mise en cache des codes de hachage n'est pas susceptible d'être aussi utile que enrouler les cordes dans une classe qui construit l'équivalence des ensembles. Si chaque instance est titulaire d'un "âge" de la valeur [un long qui est incrémenté chaque fois que l'on est créé], un string, et une référence à une instance plus ancienne qui est connu pour de match, alors quand deux objets wrappers trouver que distincte de la chaîne d'instances de match, celle qui contient une référence à un "récent" de la chaîne peut être mis à jour pour tenir le plus ancien de la chaîne d'instance qui est connu pour être égaux.
    • Assurez-vous. Compte tenu des connaissances suffisantes de vos données, je suis sûr qu'ils sont à toutes sortes d'optimisations une fois que pouvait faire. Comme si les cordes sont en quelque sorte de code et vous savez que la seule chaîne de valeurs "aasdopfu", "aasdopfv", et "aasdoxfu", vous pourriez bien mieux que des exemples, chacun comme il arrive et de le traduire dans une norme de valeur entière, comme 1, 2, et 3, respectivement. Si vous connaissez les chaînes de tous ont tendance à commencer de la même, mais différemment, vous pouvez écrire vos propres comparer que des chèques à partir de la fin vers l'arrière. Etc. Tout dépend de la nature de la ...
    • ... de données, et sur la façon dont un gros problème de performance est et combien le travail que vous êtes prêt à le faire.

    InformationsquelleAutor Jay
  5. 4

    Vous pouvez obtenir l'effet que vous souhaitez à l'aide de String.intern() (qui est mis en œuvre à l'aide d'une table de hachage.)

    Vous pouvez comparer les valeurs de retour de intern() à l'aide de la == de l'opérateur. Si elles se réfèrent à la même chaîne les chaînes étaient équivalents (c'est à dire equals() aurait retourné true), et elle ne nécessite qu'un pointeur de comparaison (qui a le même coût que un int comparaison).

    String a = "Hello";
String b = "Hel" + "lo";

System.out.println(a.equals(b));
System.out.println(a == b);

String a2 = a.intern();
String b2 = b.intern();

System.out.println(a2.equals(b2));
System.out.println(a2 == b2);

    De sortie:

    true
false
true
true
    InformationsquelleAutor finnw
  6. 1

    Le hashCode de la valeur n'est pas unique, ce qui signifie que les Chaînes ne peut pas réellement le match. Pour améliorer les performances, souvent implémentations d'égal à égal effectuera un hashCode vérifier avant d'effectuer plus laborieuse contrôles.

    InformationsquelleAutor Jim Rush
  7. 1

    Raison très simple: les risques de collisions...
    Un code de hachage auront beaucoup moins de valeurs possibles qu'une chaîne de caractères. Ça dépend un peu du type de hachage vous générer, mais prenons un exemple très simple, lorsque vous ajoutez les valeurs ordinales de lettres, multipliée par sa position: a=1, b=2, etc. Ainsi, "bonjour" serait traduit:
    h: 8x1=8, e: 5x2=10, l: 12x3=36, l: 12x4=48, o: 15x5=75. 8+10+36+48+75=177.

    Existe-il d'autres valeurs de chaîne qui pourrait mettre fin à 177 haché? Bien sûr! Beaucoup d'options. Hésitez pas à calculer un peu.

    Encore, cette méthode de hachage utilisé une méthode simple. Java et .NET use de plus en plus complexe algorithme de hachage avec beaucoup moins de chance de telles collisions. Mais encore, il ya une chance que les deux chaînes entraînera la même valeur de hachage, donc cette méthode est moins fiable.

    • zzzda serait également l'égalité de 177. (1x26, 2x26, 3x26, 4x4, 5x1)
    InformationsquelleAutor Wim ten Brink
  8. 0

    Deux différents Chaîne peut facilement générer le même Code de hachage ou différents Code de hachage.
    Si tu veux un test d'égalité de Code de hachage ne donnera pas un résultat unique. Lorsque nous utilisons la classe String, il sera de retour différente de la valeur de Code de hachage. Donc, tampon de Chaîne de classe doit être appliquer pour avoir le même Code de hachage pour chaque concated objet.

    InformationsquelleAutor Shegufa Taranjum
  9. -2

    Il n'y a pas de raison de ne pas utiliser hashCode comme vous le décrivez.

    Cependant, vous devez être conscient de collisions. Il y a une chance, une petite chance, il est vrai - que les deux chaînes ne hachage à la même valeur. Pensez à faire un hashCode au premier abord, et si l'égalité aussi faire la comparaison complète à l'aide de la equals().

    • Donc, en d'autres termes, il existe une raison pour ne pas utiliser le hashcode comme il le décrit?
    • donc il n'y a pas de raison pour l'écarter de la main, seulement un avertissement de faire des vérifications supplémentaires dans certaines circonstances
    • Donc, si vous avez encore à faire l'égal de test, pourquoi s'embêter? Vous avez juste écrit deux fois plus de code pour arriver à la même place.
    • si l'hypothèse est que les chaînes sont peu susceptibles d'être similaires, vous devez obtenir l'efficacité que la personne interrogée.
    • Je dois dire qu'à l'époque où j'écrivais démo des applications pour le début de j2me téléphones, pour les fabricants, et de la performance, même de ce genre de chose vraiment de l'importance, à l'aide de hashCode() pour rabaisser les comparaisons, c'est le genre de chose que nous avons fait tout le temps. Vous avez besoin de profilage pour les sauvegarder, mais sa vaut la peine d'explorer dans les plus critiques des performances du code.
    InformationsquelleAutor Will