Java: pourquoi les collections acceptent-elles un comparateur mais pas (un hypothétique) Hasher et Equator?

25

Ce problème est plus apparent lorsque vous avez différentes implémentations d'une interface, et pour les besoins d'une collection particulière, vous ne vous souciez que de la vue au niveau de l'interface des objets. Par exemple, supposons que vous disposiez d'une interface comme celle-ci:

public interface Person {
    int getId();
}

La manière habituelle d'implémenter hashcode()et equals()d'implémenter des classes aurait du code comme celui-ci dans la equalsméthode:

if (getClass() != other.getClass()) {
    return false;
}

Cela provoque des problèmes lorsque vous mélangez des implémentations de Persondans a HashMap. Si le HashMapseul souci de la vue au niveau de l'interface Person, alors il pourrait se retrouver avec des doublons qui ne diffèrent que par leurs classes d'implémentation.

Vous pouvez faire fonctionner ce cas en utilisant la même equals()méthode libérale pour toutes les implémentations, mais vous courez le risque de equals()faire la mauvaise chose dans un contexte différent (comme comparer deux Persons qui sont soutenus par des enregistrements de base de données avec des numéros de version).

Mon intuition me dit que l'égalité doit être définie par collection au lieu de par classe. Lorsque vous utilisez des collections qui dépendent de la commande, vous pouvez utiliser une méthode personnalisée Comparatorpour choisir la bonne commande dans chaque contexte. Il n'y a pas d'analogue pour les collections basées sur le hachage. Pourquoi est-ce?

Juste pour clarifier, cette question est distincte de " Pourquoi est .compareTo () dans une interface alors que .equals () est dans une classe en Java? " Car elle traite de l'implémentation des collections. compareTo()et equals()/ les hashcode()deux souffrent du problème de l'universalité lors de l'utilisation des collections: vous ne pouvez pas choisir différentes fonctions de comparaison pour différentes collections. Donc, pour les besoins de cette question, la hiérarchie d'héritage d'un objet n'a pas d'importance du tout; tout ce qui compte est de savoir si la fonction de comparaison est définie par objet ou par collection.

Sam
la source
5
Vous pouvez toujours introduire des objets wrapper pour Personimplémenter le comportement attendu equalset hashCode. Vous auriez alors un HashMap<PersonWrapper, V>. C'est un exemple où une approche pure-POO n'est pas élégante: toutes les opérations sur un objet n'ont pas de sens en tant que méthode de cet objet. Le Objecttype entier de Java est un amalgame de responsabilités différentes - seules les méthodes getClass, finalizeet toStringsemblent à distance justifiables par les meilleures pratiques d'aujourd'hui.
amon
1
1) En C #, vous pouvez passer un IEqualityComparer<T>à une collection basée sur le hachage. Si vous n'en spécifiez pas, il utilise une implémentation par défaut basée sur Object.Equalset Object.GetHashCode(). 2) L'OMI remplaçant Equalsun type de référence mutable est rarement une bonne idée. De cette façon, l'égalité par défaut est assez stricte, mais vous pouvez utiliser une règle d'égalité plus détendue lorsque vous en avez besoin via une personnalisation IEqualityComparer<T>.
CodesInChaos

Réponses:

23

Cette conception est parfois connue sous le nom d '«égalité universelle», c'est la croyance selon laquelle deux choses sont égales ou non est une propriété universelle.

De plus, l'égalité est une propriété de deux objets, mais dans OO, vous appelez toujours une méthode sur un seul objet , et cet objet décide uniquement comment gérer cet appel de méthode. Ainsi, dans une conception comme Java, où l'égalité est une propriété de l'un des deux objets comparés, il n'est même pas possible de garantir certaines propriétés de base de l'égalité telles que la symétrie ( a == bb == a), car dans le premier cas, la méthode est sollicitée aet dans le second cas elle est sollicitée bet en raison des principes de base de l'OO, c'est uniquement ala décision de (dans le premier cas) oubdécision (dans le deuxième cas) de se considérer ou non comme égale à l 'autre. La seule façon de gagner en symétrie est de faire coopérer les deux objets, mais s'ils ne le font pas… pas de chance.

Une solution consisterait à faire de l'égalité non pas une propriété d'un objet, mais soit une propriété de deux objets, soit une propriété d'un troisième objet. Cette dernière option résout également le problème de l'égalité universelle, car si vous faites de l'égalité une propriété d'un troisième objet "contexte", alors vous pouvez imaginer avoir des EqualityComparerobjets différents pour des contextes différents.

C'est la conception choisie pour Haskell, par exemple, avec la Eqclasse de types. C'est également la conception choisie par certaines bibliothèques Scala tierces (ScalaZ, par exemple), mais pas le noyau Scala ou la bibliothèque standard, qui utilise l'égalité universelle pour la compatibilité avec la plate-forme hôte sous-jacente.

Il est intéressant de noter que c'est aussi le design choisi avec Java Comparable/ Comparatorinterfaces. Les concepteurs de Java étaient clairement conscients du problème, mais pour une raison quelconque, ils ne l'ont résolu que pour la commande, mais pas pour l'égalité (ou le hachage).

Donc, quant à la question

pourquoi y a-t-il une Comparatorinterface mais pas Hasheret Equator?

la réponse est "je ne sais pas". De toute évidence, les concepteurs de Java étaient conscients du problème, comme en témoigne l'existence de Comparator, mais ils ne pensaient évidemment pas que c'était un problème d'égalité et de hachage. D'autres langues et bibliothèques font des choix différents.

Jörg W Mittag
la source
7
+1, mais notez qu'il existe des langages OO où plusieurs répartitions existent (Smalltalk, Common Lisp). Donc, c'est toujours trop fort dans la phrase suivante: "dans OO, vous appelez toujours une méthode sur un seul objet".
coredump
J'ai trouvé la citation que je cherchais; selon JLS 1.0, The methods equals and hashCode are declared for the benefit of hashtables such as java.util.Hashtablec'est-à-dire les deux equalset hashCodeont été introduits comme Objectméthodes par les développeurs Java uniquement pour le plaisir de Hashtable- il n'y a aucune notion d'UE ou quoi que ce soit de silimar dans la spécification, et la citation est assez claire pour moi; sans le Hashtable, equalsaurait probablement été dans une interface comme Comparable. En tant que tel, même si je pensais autrefois que votre réponse était correcte, je considère maintenant qu'elle n'est pas étayée.
vaxquis
@ JörgWMittag c'était une faute de frappe, IFTFY. BTW, parlant de clone- c'était à l'origine un opérateur , pas une méthode (voir Oak Language Specification), citation: The unary operator clone is applied to an object. (...) The clone operator is normally used inside new to clone the prototype of some class, before applying the initializers (constructors)- les trois opérateurs de type mot clé étaient instanceof new clone(section 8.1, opérateurs). Je suppose que c'est la vraie raison (historique) du clone/ Cloneablemess - Cloneablec'était simplement une invention plus tardive, et le clonecode existant était mis à niveau avec.
vaxquis
2
"C'est la conception choisie pour Haskell, par exemple, avec la classe de types Eq" C'est un peu vrai, mais il convient de noter que Haskell déclare explicitement à l'avance que deux objets de types différents ne sont jamais égaux, contrairement à l'approche de Java. L'opération d'égalité fait donc partie du type , (donc "typeclass") ne fait pas partie d'une troisième valeur de contexte.
Jack
19

La vraie réponse à

pourquoi y a-t-il une Comparatorinterface mais pas Hasheret Equator?

est, avec l'aimable autorisation de Josh Bloch :

Les API Java d'origine ont été réalisées très rapidement dans un délai serré pour respecter une fenêtre de marché de fermeture. L'équipe Java d'origine a fait un travail incroyable, mais toutes les API ne sont pas parfaites.

Le problème réside uniquement dans l'histoire de Java, comme avec d' autres questions similaires, par exemple .clone()vs Cloneable.

tl; dr

c'est principalement pour des raisons historiques; le comportement / abstraction actuel a été introduit dans JDK 1.0 et n'a pas été corrigé plus tard car il était pratiquement impossible de le faire avec le maintien de la compatibilité du code en arrière.


Tout d'abord, résumons quelques faits Java bien connus:

  1. Java, du tout début à nos jours, était fièrement rétrocompatible, nécessitant que les API héritées soient toujours prises en charge dans les versions plus récentes,
  2. en tant que tel, presque chaque construction de langage introduite avec JDK 1.0 a vécu jusqu'à nos jours,
  3. Hashtable, .hashCode()& .equals()ont été implémentés dans JDK 1.0, ( Hashtable )
  4. Comparable/ a Comparatorété introduit dans JDK 1.2 ( comparable ),

Maintenant, il suit:

  1. il était pratiquement impossible et insensé de moderniser .hashCode()et .equals()d'interfaces distinctes tout en conservant la compatibilité descendante après que les gens se soient rendus compte qu'il y avait de meilleures abstractions que de les mettre en superobjet, parce que par exemple, chaque programmeur Java par 1.2 savait que tout le monde Objectles avait, et ils avaient y rester physiquement pour assurer également la compatibilité du code compilé (JVM) - et l'ajout d'une interface explicite à chaque Objectsous-classe qui les a réellement implémentées rendrait ce désordre égal (sic!) à Clonableun ( Bloch explique pourquoi Cloneable craint , également abordé par exemple dans EJ 2nd et bien d'autres endroits, dont SO),
  2. ils les ont simplement laissés là pour que la future génération ait une source constante de WTF.

Maintenant, vous pouvez demander "qu'est-ce qui Hashtablea tout cela"?

La réponse est: hashCode()/ equals()contrat et compétences en conception de langage pas si bonnes des principaux développeurs Java en 1995/1996.

Citation de Java 1.0 Language Spec, datée de 1996 - 4.3.2 The Class Object, p.41:

Les méthodes equalset hashCodesont déclarées au profit de tables de hachage telles que java.util.Hashtable(§21.7). La méthode equals définit une notion d'égalité d'objet, qui est basée sur une comparaison de valeur et non de référence.

(notez que cette déclaration exacte a été modifiée dans les versions ultérieures, à savoir, citation:, The method hashCode is very useful, together with the method equals, in hashtables such as java.util.HashMap.rendant impossible la connexion directe Hashtable- hashCode- equalssans lire l'historique JLS!)

L'équipe Java a décidé qu'ils voulaient une bonne collection de style dictionnaire, et ils ont créé Hashtable(bonne idée jusqu'à présent), mais ils voulaient que le programmeur puisse l'utiliser avec le moins de code / courbe d'apprentissage possible (oups! Problèmes entrants!) - et, comme il n'y avait pas encore de génériques [c'est JDK 1.0 après tout], cela signifierait que chaque Object entrée Hashtabledevrait implémenter explicitement une interface (et les interfaces n'en étaient qu'à leurs débuts à l'époque ... pas Comparableencore même!) , ce qui en fait un moyen de dissuasion de l'utiliser pour beaucoup - ou Objectdevrait implicitement implémenter une méthode de hachage.

De toute évidence, ils ont opté pour la solution 2, pour les raisons décrites ci-dessus. Ouais, maintenant nous savons qu'ils avaient tort. ... il est facile d'être intelligent avec le recul. glousser

Maintenant, il hashCode() faut que chaque objet l'ayant doit avoir une equals()méthode distincte - il était donc tout à fait évident qu'il equals()fallait également y mettre Object.

Étant donné que les défaut mises en œuvre de ces méthodes sur valide aet b Objects sont essentiellement inutiles en étant redondants ( ce qui a.equals(b) égale à a==bet a.hashCode() == b.hashCode() égale à peu près à a==baussi, à moins que hashCodeet / ou equalsest surchargé, ou vous GC des centaines de milliers de Objects au cours du cycle de vie de votre application 1 ) , il est sûr de dire qu'ils ont été fournis principalement à titre de mesure de sauvegarde et pour des raisons de commodité d'utilisation. C'est exactement comme cela que nous arrivons au fait bien connu qui remplace toujours les deux .equals()et .hashCode()si vous avez l'intention de comparer les objets ou de les stocker par hachage. Surcharger un seul d'entre eux sans l'autre est un bon moyen de visser votre code (en comparant les résultats ou les valeurs de collision incroyablement élevées) - et de le contourner est une source de confusion et d'erreurs constantes pour les débutants (recherchez SO pour voir pour vous-même) et une nuisance constante pour les plus aguerris.

Notez également que bien que C # traite les égaux et le code de hachage de manière un peu meilleure, Eric Lippert lui-même déclare qu'ils ont fait presque la même erreur avec C # que Sun a fait avec Java des années avant la création de C # :

Mais pourquoi devrait-il être le cas que chaque objet devrait pouvoir se hacher pour être inséré dans une table de hachage? Cela semble étrange d'exiger que chaque objet soit capable de le faire. Je pense que si nous repensions le système de type à partir de zéro aujourd'hui, le hachage pourrait être fait différemment, peut-être avec une IHashableinterface. Mais lorsque le système de type CLR a été conçu, il n'y avait pas de types génériques et donc une table de hachage à usage général devait être en mesure de stocker n'importe quel objet.

1 bien sûr, Object#hashCodepeut encore entrer en collision, mais cela demande un peu d'effort, voir: http://bugs.java.com/bugdatabase/view_bug.do?bug_id=6809470 et les rapports de bogues liés pour plus de détails; /programming/1381060/hashcode-uniqueness/1381114#1381114 couvre ce sujet plus en profondeur.

vaxquis
la source
Mais ce n'est pas seulement Java. Beaucoup de ses contemporains (Ruby, Python,…) et de ses prédécesseurs (Smalltalk,…) et certains de ses successeurs ont également Universal Equality et Universal Hashability (est-ce un mot?).
Jörg W Mittag
@ JörgWMittag voir programmers.stackexchange.com/questions/283194/… - Je ne suis pas d'accord sur "UE" en Java; UE n'a jamais été une préoccupation réelle dans Objectla conception de; l'habilité était.
vaxquis
@vaxquis Je ne veux pas insister là-dessus, mais mon commentaire précédent montre que deux objets accessibles simultanément peuvent avoir le même code de hachage (par défaut).
Rétablir Monica
1
@vaxquis OK. J'achète ça. Ma préoccupation est que quelqu'un qui apprend le voit et pense qu'il est intelligent en utilisant le code de hachage du système au lieu de l'égal, etc. S'ils le font, cela fonctionnera probablement assez bien, sauf pour les rares fois où il ne le fait pas et il y aura aucun moyen de reproduire le problème de manière fiable.
JimmyJames
1
Cela devrait être la réponse acceptée, car la conclusion de la réponse acceptée est "je ne sais pas"
Phoenix