Un HashSet devrait-il pouvoir être ajouté à lui-même en Java?

D’autres ont déjà expliqué pourquoi il est discutable d’un sharepoint vue mathématique, en se référant au paradoxe de Russell .

Cela ne répond pas à votre question au niveau technique , cependant.

Alors disséquons ceci:

Tout d’abord, une fois de plus, la partie pertinente de JavaDoc de l’interface Set :

Note: Il faut faire très attention si des objects mutables sont utilisés comme éléments de l’ensemble. Le comportement d’un ensemble n’est pas spécifié si la valeur d’un object est modifiée d’une manière qui affecte les comparaisons d’égal alors que l’object est un élément de l’ensemble. Un cas particulier de cette interdiction est qu’il n’est pas permis à un ensemble de se contenir comme élément.

Il est intéressant de noter que JavaDoc de l’interface List présente une déclaration similaire, quoique un peu plus faible et en même temps plus technique:

Bien qu’il soit permis aux listes de se contenir en tant qu’éléments, une extrême prudence est conseillée: les méthodes equals et hashCode ne sont plus bien définies sur une telle liste.

Et enfin, le noeud est dans le JavaDoc de l’interface Collection , qui est l’ancêtre commun à la fois de l’interface Set et de la List :

Certaines opérations de collecte qui effectuent un parcours récursif de la collection peuvent échouer avec une exception pour les instances auto-référentielles dans lesquelles la collection se contient directement ou indirectement . Cela inclut les méthodes clone() , equals() , hashCode() et toSsortingng() . Les implémentations peuvent éventuellement gérer le scénario autoréférentiel, mais la plupart des implémentations actuelles ne le font pas.

^{(Accent mis par moi)}

La partie audacieuse est une allusion à pourquoi l’approche que vous avez proposée dans votre question ne serait pas suffisante:

Il semble qu’il y ait un contrôle d’égalité avant d’append un élément pour éviter de violer ce contrat, non?

Cela ne vous aiderait pas ici. Le point essentiel est que vous rencontrerez toujours des problèmes lorsque la collection se contiendra directement ou indirectement . Imaginez ce scénario:

 Set 

De toute évidence, aucun des ensembles ne se contient directement . Mais chacun d’eux contient l’autre – et donc lui-même indirectement . Cela ne pouvait pas être évité par une simple vérification d’égalité référentielle (en utilisant == dans la méthode add ).

Eviter un tel “état incohérent” est fondamentalement impossible dans la pratique. Bien entendu, cela est possible en théorie, en utilisant les calculs de l’ accessibilité référentielle. En fait, le garbage collector doit faire exactement cela!

Mais cela devient impossible en pratique lorsque des classes personnalisées sont impliquées. Imaginez une classe comme celle-ci:

 class Container { Set 

Et déconner avec ceci et son set :

 Set 

La méthode add de l’ Set n’a aucun moyen de détecter si l’object ajouté contient une référence (indirecte) à l’ensemble lui-même.

Longue histoire courte:

Vous ne pouvez pas empêcher le programmeur de tout gâcher.

L’ajout de la collection en elle-même provoque le passage du test. L’append deux fois provoque l’ StackOverflowError que vous StackOverflowError .

Du sharepoint vue du développeur personnel, cela n’a aucun sens d’imposer une vérification dans le code sous-jacent pour empêcher cela. Le fait que vous obteniez un StackOverflowError dans votre code si vous tentez de le faire trop souvent ou que vous StackOverflowError le hashCode – qui provoquerait un débordement instantané – devrait suffire à garantir qu’aucun développeur sensé ne conserve ce type de code dans son code. base.

Vous devez lire le document complet et le citer intégralement:

Le comportement d’un ensemble n’est pas spécifié si la valeur d’un object est modifiée d’une manière qui affecte les comparaisons d’égal alors que l’object est un élément de l’ensemble. Un cas particulier de cette interdiction est qu’il n’est pas permis à un ensemble de se contenir comme élément.

La ressortingction actuelle se trouve dans la première phrase. Le comportement n’est pas spécifié si un élément d’un ensemble est muté.

Comme l’ajout d’un ensemble à lui-même le mute, et l’ajoute à nouveau, le résultat est indéterminé.

Notez que la ressortingction est que le comportement n’est pas spécifié et qu’un cas particulier de cette ressortingction ajoute le jeu à lui-même.

En d’autres termes, le document dit que l’ajout d’un ensemble à lui-même entraîne un comportement non spécifié, ce que vous voyez. C’est à la mise en œuvre concrète de traiter (ou non).

Je suis d’accord avec vous que, d’un sharepoint vue mathématique, ce comportement n’a vraiment aucun sens.

Il y a deux questions intéressantes ici: d’abord, dans quelle mesure les concepteurs de l’interface Set essayé de mettre en œuvre un ensemble mathématique? Deuxièmement, même si ce n’était pas le cas , dans quelle mesure cela les exclut-il des règles de la théorie des ensembles?

Pour la première question, je vous dirigerai vers la documentation du Set:

Une collection qui ne contient aucun élément en double. Plus formellement, les ensembles ne contiennent aucune paire d’éléments e1 et e2 tels que e1.equals (e2) et au plus un élément nul. Comme son nom l’indique, cette interface modélise l’abstraction d’ensemble mathématique.

Il convient de mentionner ici que les formulations actuelles de la théorie des ensembles ne permettent pas aux ensembles d’être membres d’eux-mêmes. (Voir l’ axiome de régularité ). Cela est dû en partie au paradoxe de Russell , qui exposait une contradiction dans la théorie naïve des ensembles (qui permettait à un ensemble d’être une collection d’objects – il n’y avait aucune interdiction contre les ensembles eux-mêmes). Ceci est souvent illustré par le paradoxe de Barber : supposons que, dans une ville donnée, un coiffeur rase tous les hommes – et seulement les hommes – qui ne se rasent pas eux-mêmes. Question: le coiffeur se rase lui-même? S’il le fait, cela viole la deuxième contrainte; s’il ne le fait pas, cela viole la première contrainte. Ceci est clairement logiquement impossible, mais en fait, il est parfaitement acceptable selon les règles de la théorie des ensembles naïfs (c’est pourquoi la nouvelle formulation “standard” de la théorie des ensembles interdit explicitement aux ensembles de se contenir).

Il y a plus de discussions dans cette question sur Math.SE sur les raisons pour lesquelles les ensembles ne peuvent pas être un élément d’eux-mêmes.

Cela dit, cela soulève la deuxième question: même si les concepteurs n’avaient pas explicitement essayé de modéliser un ensemble mathématique, cela serait-il complètement «exempt» des problèmes associés à la théorie des ensembles naïfs? Je pense que non – je pense que bon nombre des problèmes qui affligeaient la théorie des ensembles naïfs affligeraient toute forme de collection insuffisamment limitée de manière analogue à la théorie des ensembles naïfs. En effet, je suis peut-être en train d’en lire trop, mais la première partie de la définition d’un Set dans la documentation ressemble étrangement au concept intuitif d’un ensemble en théorie naïve des ensembles:

Une collection qui ne contient aucun élément en double.

Certes (et à leur crédit), ils imposent au moins quelques contraintes à cela plus tard (notamment en déclarant que vous ne devriez vraiment pas essayer d’avoir un Set lui-même), mais vous pourriez vous demander si c’est vraiment “suffisant” pour éviter les problèmes. avec la théorie des ensembles naïfs. C’est pourquoi, par exemple, vous avez un problème de “tortues tout en bas” lorsque vous essayez de calculer le code de hachage d’un HashSet qui se contient. Ce n’est pas, comme d’autres l’ont suggéré, simplement un problème pratique – c’est une illustration des problèmes théoriques fondamentaux de ce type de formulation.

En guise de brève digression, je reconnais que, bien sûr, il existe des limites à la mesure dans laquelle une classe de collection peut réellement modéliser un ensemble mathématique. Par exemple, la documentation de Java met en garde contre les dangers d’inclure des objects mutables dans un ensemble. Certains autres langages, tels que Python, tentent au moins d’ interdire complètement plusieurs types d’objects mutables :

Les classes de set sont implémentées à l’aide de dictionnaires. En conséquence, les exigences pour les éléments de set sont les mêmes que celles pour les clés de dictionnaire; à savoir que l’élément définit à la fois __eq__() et __hash__() . Par conséquent, les ensembles ne peuvent pas contenir d’éléments mutables tels que des listes ou des dictionnaires. Cependant, ils peuvent contenir des collections immuables telles que des tuples ou des instances d’ImmutableSet. Pour faciliter la mise en œuvre d’ensembles d’ensembles, les ensembles internes sont automatiquement convertis sous une forme immuable, par exemple, Set([Set(['dog'])]) est transformé en Set([ImmutableSet(['dog'])]) .

Deux autres différences majeures que d’autres ont signalées sont

• Les jeux Java sont mutables
• Les ensembles Java sont finis. Évidemment, cela sera vrai pour toute classe de collection: mis à part les problèmes d’ infini , les ordinateurs n’ont qu’une quantité de mémoire limitée. (Certaines langues, comme Haskell, ont des structures de données infinies paresseuses; cependant, à mon avis, une séquence de choix conforme à la loi semble être un modèle plus naturel que la théorie des ensembles classique, mais ce n’est que mon opinion).

TL; DR Non, cela ne devrait vraiment pas être autorisé (ou du moins, vous ne devriez jamais le faire) car les ensembles ne peuvent pas être membres d’eux-mêmes.