Pourquoi la méthode equals dans Ssortingng n’utilise-t-elle pas le hachage?

Le code de la méthode equals dans la classe Ssortingng est

 public boolean equals(Object anObject) { if (this == anObject) { return true; } if (anObject instanceof Ssortingng) { Ssortingng anotherSsortingng = (Ssortingng)anObject; int n = count; if (n == anotherSsortingng.count) { char v1[] = value; char v2[] = anotherSsortingng.value; int i = offset; int j = anotherSsortingng.offset; while (n-- != 0) { if (v1[i++] != v2[j++]) return false; } return true; } } return false; } 

J’ai une question – pourquoi cette méthode n’utilise-t-elle pas hashCode ()?

A ma connaissance, hashCode () peut rapidement comparer deux chaînes.

MISE À JOUR: Je sais que deux chaînes inégales peuvent avoir les mêmes hachages. Mais deux chaînes égales ont des hachages égaux. Donc, en utilisant hashCode (), nous pouvons immédiatement voir que deux chaînes sont inégales.

Je pense simplement que l’utilisation de hashCode () peut être un bon filtre en equals .

MISE À JOUR 2: Voici du code, nous parlons ici.

C’est un exemple de la façon dont la méthode Ssortingng peut ressembler

 public boolean equals(Object anObject) { if (this == anObject) { return true; } if (anObject instanceof Ssortingng) { Ssortingng anotherSsortingng = (Ssortingng)anObject; if (hashCode() == anotherSsortingng.hashCode()){ int n = count; if (n == anotherSsortingng.count) { char v1[] = value; char v2[] = anotherSsortingng.value; int i = offset; int j = anotherSsortingng.offset; while (n-- != 0) { if (v1[i++] != v2[j++]) return false; } return true; } }else{ return false; } } return false; } 

Hashcode pourrait être une vérification de premier plan pour l’inégalité. Cependant, cela présente des compromis.

  1. Ssortingng codes de hachage des Ssortingng sont calculés avec précaution, bien qu’ils utilisent une valeur de “garde”. Si vous comparez des chaînes avec des durées de vie longues (c.-à-d. Qu’elles ont probablement le code de hachage calculé), ce n’est pas un problème. Sinon, vous êtes bloqué par le calcul du hashcode (potentiellement coûteux) ou par l’ignorance de la vérification lorsque le hashcode n’a pas encore été calculé. Si vous avez beaucoup de chaînes de courte durée, vous allez ignorer le chèque plus souvent que vous ne l’utiliserez.
  2. Dans le monde réel, la plupart des chaînes diffèrent par leurs premiers caractères, vous ne économiserez donc pas beaucoup en vérifiant d’abord le hashcode. Il y a, bien sûr, des exceptions (telles que les URL), mais encore une fois, dans la programmation du monde réel , elles se produisent rarement.

Cette question a effectivement été considérée par les développeurs du JDK. Je n’ai pas pu trouver dans les divers messages la raison pour laquelle elle n’a pas été incluse. L’amélioration est également répertoriée dans la firebase database de bogues .

A savoir, l’un des changements proposés est:

 public boolean equals(Object anObject) { if (this == anObject) // 1st check identitiy return true; if (anObject instanceof Ssortingng) { // 2nd check type Ssortingng anotherSsortingng = (Ssortingng)anObject; int n = count; if (n == anotherSsortingng.count) { // 3rd check lengths if (n != 0) { // 4th avoid loading registers from members if length == 0 int h1 = hash, h2 = anotherSsortingng.hash; if (h1 != 0 && h2 != 0 && h1 != h2) // 5th check the hashes return false; 

Il y avait aussi une discussion pour utiliser == pour les chaînes internes (c.-à-d. Si les deux chaînes sont internées: if (this != anotherSsortingng) return false; ).

1) Le calcul du hashCode peut ne pas être plus rapide que de comparer directement les chaînes.

2) si le hashCode est égal, les chaînes peuvent ne pas être égales

Cela peut être une bonne idée pour de nombreux cas d’utilisation.

Cependant, en tant que classe de base largement utilisée dans toutes sortes d’applications, l’auteur n’a vraiment aucune idée si cette vérification supplémentaire peut permettre d’économiser ou de nuire aux performances en moyenne.

Je suppose que la majorité de Ssortingng.equals() est appelée dans une Hashmap, après que les codes de hachage soient connus pour être égaux, donc tester à nouveau les codes de hachage est inutile.

Si nous considérons la comparaison de deux chaînes aléatoires, même avec un petit jeu de caractères comme US ASCII, il est très probable que les hachages soient différents et que la comparaison char-by-car échoue sur le premier caractère. Donc, ce sera un gaspillage de vérifier les hachages.

AFAIK, La vérification suivante pourrait être ajoutée à Ssortingng. Cela vérifie que si les codes de hachage sont définis et qu’ils sont différents, alors les chaînes ne peuvent pas être égales.

 if (hash != 0 && anotherSsortingng.hash != 0 && hash != anotherSsortingng.hash) return false; if (hash32 != 0 && anotherSsortingng.hash32 != 0 && hash32 != anotherSsortingng.hash32) return false; 

Le code de hachage de chaîne n’est pas disponible gratuitement et automatiquement. Afin de s’appuyer sur le code de hachage, il doit être calculé pour les deux chaînes et peut alors être comparé. Comme les collisions sont possibles, la deuxième comparaison char-by-char est requirejse si les codes de hachage sont égaux.

Alors que Ssortingng apparaît comme immuable pour le programmeur habituel, il possède le champ privé pour stocker son code de hachage une fois qu’il est calculé. Cependant, ce champ n’est calculé que lorsque le premier mot de passe est requirejs. Comme vous pouvez le voir dans le code source de Ssortingng ici :

  private int hash; public int hashCode() { int h = hash; if (h == 0) { ... hash = h; } return h; } 

Par conséquent, il n’est pas évident qu’il soit logique de calculer le hashcode en premier. Pour votre cas spécifique (peut-être que les mêmes instances de chaînes très longues sont comparées les unes aux autres un très grand nombre de fois), cela peut toujours être: profile.

Comme je le pense, hashCode () peut rendre la comparaison de deux chaînes plus rapide.

Arguments?

Arguments contre cette proposition:

  • Plus d’opérations

hashcode() from Ssortingng doit accéder à tous les caractères de la chaîne et doit effectuer 2 calculs pour chaque caractère.
Nous avons donc besoin d’une chaîne de caractères avec 5*n caractères d’opérations 5*n (chargement, multiplication, recherche / chargement, multiplication, stockage). Deux fois, car nous comparons deux chaînes. (Ok, un magasin et un chargement ne comptent pas vraiment dans une implémentation raisonnable.)
Dans le meilleur des cas, cela fait un total de 10*x opérations 10*x pour deux chaînes de longueur m et n et x=min(m,n) . Le pire cas est 10*x avec x=m=n . Moyenne quelque part entre peut-être (m*n)/2 .

Le courant est égal aux besoins de mise en œuvre dans le meilleur des cas. 2 charges, 1 comparer. Le pire est 3*x opérations pour deux chaînes de longueur m et n et x=m=n . La moyenne se situe entre, peut-être 3*(m*n)/2 .

  • Même si nous cachons le hash, il n’est pas clair que nous sauvons quelque chose

Nous devons parsingr les modèles d’utilisation. Il se pourrait que la plupart du temps, nous ne demandions qu’une seule fois pour des égaux, pas plusieurs fois. Même si nous demandons plusieurs fois, cela ne pourrait pas être suffisant pour avoir un gain de temps de la mise en cache.

Pas direct contre la vitesse, mais toujours de bons contre-arguments:

  • Contre-intuitif

Nous n’attendons pas de code de hachage égal, car nous soaps avec certitude que le hash(a)==hash(b) pour certains a!=b Tout le monde qui lit ceci (et ses connaissances sur le hachage) se demandera ce qui se passe là-bas.

  • Conduit à de mauvais exemples ou à un comportement inattendu

Je peux déjà voir la question suivante sur SO: “J’ai un Ssortingng avec quelques milliards de fois” a “. Pourquoi faut-il toujours le comparer avec equal () contre” b “?” 🙂

Si le code de hachage prend en compte tout le contenu de la chaîne, le calcul du code de hachage d’une chaîne avec n caractères prend n opérations. Pour les longues cordes, c’est beaucoup. Comparer deux chaînes prend n opérations si elles sont identiques, pas plus longtemps que le calcul du hachage. Mais si les chaînes sont différentes, alors une différence sera probablement trouvée beaucoup plus tôt.

Les fonctions de hachage de chaînes ne prennent généralement pas en compte tous les caractères pour les très longues chaînes. Dans ce cas, si je compare deux chaînes, je pourrais d’abord comparer les caractères utilisés par la fonction de hachage, et je vérifie au moins aussi rapidement les hachages. Mais s’il n’y a pas de différence entre ces caractères, la valeur de hachage sera la même, alors je dois comparer les chaînes complètes de toute façon.

Résumé: Une bonne comparaison de chaînes n’est jamais plus lente mais souvent beaucoup plus rapide que la comparaison des hachages (et la comparaison de chaînes lorsque les hachages correspondent).