Code de hachage d'ArrayList qui se contient comme élément

38

Pouvons-nous trouver le hashcoded'un listqui se contient comme element?

Je sais que c'est une mauvaise pratique, mais c'est ce que l'intervieweur a demandé.

Lorsque j'ai exécuté le code suivant, il lance un StackOverflowError:

public class Main {
    public static void main(String args[]) {
        ArrayList<ArrayList> a = new ArrayList();
        a.add(a);
        a.hashCode();
    }
}

Maintenant, ici, j'ai deux questions:

  1. Pourquoi y en a-t-il StackOverflowError?
  2. Est-il possible de trouver le code de hachage de cette manière?
Joker
la source
7
Parce que vous ajoutez la liste à elle-même. essayez a.hashCode () sans l'instruction add
Jens
Lorsque vous placez un objet dans une liste d'array, vous stockez la référence à l'objet. Dans votre cas, vous mettez une liste ArrayList qui est elle-même une référence.
Vishwa Ratna
Ok, j'ai compris pourquoi il y a stackoverflow, quelqu'un peut-il m'aider à expliquer le problème numéro 2- Comment trouver cela
Joker
9
Comme d'autres l'ont répondu, cela n'est pas possible, par la définition même de l' Listinterface, le fonctionnement hashCoded'une liste dépend de ses membres. Étant donné que la liste est son propre membre, son code de hachage dépend de son hashCode, qui dépend de son hashCode... et ainsi de suite, provoquant une récursion infinie et le que StackOverflowErrorvous rencontrez. Maintenant, la question est: pourquoi avez-vous besoin d'une liste pour se contenir? Je peux vous garantir que vous pouvez réaliser tout ce que vous essayez de faire, d'une meilleure manière, sans exiger une adhésion récursive comme celle-ci.
Alexander - Réintègre Monica le

Réponses:

36

Le code de hachage pour les Listimplémentations conformes a été spécifié dans l'interface :

Renvoie la valeur du code de hachage pour cette liste. Le code de hachage d'une liste est défini comme étant le résultat du calcul suivant:

 int hashCode = 1;
 for (E e : list)
     hashCode = 31*hashCode + (e==null ? 0 : e.hashCode());

Cela garantit que cela list1.equals(list2)implique que list1.hashCode()==list2.hashCode()pour deux listes, list1et list2, comme l'exige le contrat général de Object.hashCode().

Cela ne nécessite pas que l'implémentation ressemble exactement à cela (voir Comment calculer le code de hachage pour un flux de la même manière que List.hashCode () pour une alternative), mais le code de hachage correct pour une liste ne contenant que lui-même serait être un nombre pour lequel x == 31 + xdoit être true, en d'autres termes, il est impossible de calculer un nombre conforme.

Holger
la source
1
@Holger, Eirc veut remplacer le code de la fonction entière hashCode()à retourner 0. Cela résout techniquement x == 31 + xmais ignore l'exigence selon laquelle x doit être au moins 1.
bxk21
4
@EricDuminil le point de ma réponse est, le contrat décrit une logique qui ArrayListimplémente littéralement, conduisant à une récursivité, mais il n'y a pas non plus d'implémentation conforme conforme. Notez que j'ai posté ma réponse à un moment où le PO a déjà compris pourquoi cette mise en œuvre particulière conduit à un StackOverflowError, qui a été traité dans d'autres réponses. Je me suis donc concentré sur l'impossibilité générale d'une implémentation conforme se terminant en temps fini avec une valeur.
Holger
2
@pdem, peu importe que la spécification utilise une description verbeuse d'un algorithme, une formule, un pseudo-code ou un code réel. Comme indiqué dans la réponse, le code donné dans la spécification n'empêche pas les implémentations alternatives en général. La forme de la spécification ne dit pas si l'analyse a eu lieu ou non. La phrase de la documentation de l'interface « S'il est permis aux listes de se contenir comme é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 » suggère qu'une telle analyse a bien eu lieu.
Holger
2
@pdem vous l'inversez. Je n'ai jamais dit que la liste devait être égale à cause du code de hachage. Les listes sont égales, par définition. Arrays.asList("foo")est égal à Collections.singletonList("foo"), est égal à List.of("foo")est égal à new ArrayList<>(List.of("foo")). Toutes ces listes sont égales, point. Puis, comme ces listes sont égales, elles doivent avoir le même code de hachage. Pas l'inverse. Puisqu'ils doivent avoir le même code de hachage, il doit être bien défini. Quelle que soit la façon dont ils l'ont définie (de retour en Java 2), elle doit être bien définie, pour être acceptée par toutes les implémentations.
Holger
2
@pdem exactement, une implémentation personnalisée qui, soit n'implémente pas, Listsoit présente un grand signe d'avertissement «ne pas mélanger avec des listes ordinaires», comparer avec IdentityHashMapet sa « Cette classe n'est pas une implémentation Map à usage général! " Attention. Dans le premier cas, vous êtes déjà prêt à implémenter Collectionmais aussi à ajouter les méthodes d'accès basées sur l'index de style de liste. Ensuite, aucune contrainte d'égalité n'existe, mais elle fonctionne toujours sans problème avec d'autres types de collection.
Holger
23

Découvrez l'implémentation squelettique de la hashCodeméthode en AbstractListclasse.

public int hashCode() {
    int hashCode = 1;
    for (E e : this)
        hashCode = 31*hashCode + (e==null ? 0 : e.hashCode());
    return hashCode;
}

Pour chaque élément de la liste, cela appelle hashCode. Dans votre cas, la liste a elle-même comme seul élément. Maintenant, cet appel ne se termine jamais. La méthode s'appelle récursivement et la récursivité continue de s'enrouler jusqu'à ce qu'elle rencontre le StackOverflowError. Donc, vous ne pouvez pas trouver de hashCodecette façon.

Ravindra Ranwala
la source
Donc, la réponse est qu'il n'y a aucun moyen de trouver le code de hachage de cette façon?
Joker
3
Oui, en raison de la condition récursive
springe
Non seulement cela, c'est défini de cette façon.
chrylis
14

Vous avez défini une liste (pathologique) qui se contient.

Pourquoi il y en a StackOverflowError?

Selon les javadocs (c'est-à-dire la spécification), le hashcode d'un Listest défini en fonction du hashcode de chacun de ses éléments. Ça dit:

"Le code de hachage d'une liste est défini comme étant le résultat du calcul suivant:"

int hashCode = 1;
    for (E e : list)
         hashCode = 31*hashCode + (e==null ? 0 : e.hashCode());

Donc, pour calculer le code de hachage de a, vous devez d'abord calculer le code de hachage de a. C'est infiniment récursif et conduit rapidement à un débordement de pile.

Est-il possible de trouver le code de hachage de cette manière?

Non. Si vous considérez la spécification algorithmique ci-dessus en termes mathématiques, le code de hachage d'un Listqui se contient est une fonction non calculable . Il n'est pas possible de le calculer de cette façon (en utilisant l'algorithme ci-dessus) ou de toute autre manière .

Stephen C
la source
Je ne sais pas pourquoi cette réponse est inférieure aux deux autres car elle répond en fait aux questions du PO avec des explications.
Neyt
1
@Neyt certains utilisateurs ne lisent que les réponses en haut.
Holger
8

Non, la documentation a une réponse

La documentation de la structure List indique explicitement:

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

Il n'y a pas grand-chose à dire au-delà de cela - selon la spécification Java, vous ne pourrez pas calculer hashCode pour une liste qui se contient; d'autres réponses expliquent en détail pourquoi il en est ainsi, mais le fait est qu'elle est connue et intentionnelle.

Peter est
la source
1
Vous avez dit pourquoi cela est en dehors de la spécification, donc cela explique que ce n'est pas un bug. C'était la partie manquante des autres réponses.
pdem
3

La réponse de Ravindra donne une bonne explication pour le point 1. Pour commenter la question 2:

Est-il possible de trouver le code de hachage de cette manière?

Quelque chose est circulaire ici. Au moins l'un de ces 2 doit être erroné dans le contexte de cette erreur de débordement de pile:

  • que le code de hachage de la liste doit prendre en compte ceux de ses éléments
  • qu'il est normal qu'une liste soit son propre élément

Maintenant, parce que nous avons affaire à un ArrayList, le premier point est fixe. En d'autres termes, vous avez peut-être besoin d'une implémentation différente pour pouvoir calculer de manière significative le code de hachage d'une liste récursive ... On pourrait étendre ArrayListet ignorer l'ajout des codes de hachage des éléments, quelque chose comme

for (E e : this)
  if(e == this) continue; //contrived rules
  hashCode = 31*hashCode + (e==null ? 0 : e.hashCode());

ArrayListVous pourriez utiliser une telle classe au lieu de .

Avec ArrayList, le deuxième point est faux. Donc, si l'intervieweur voulait dire "Est-il possible de trouver du code de hachage de cette manière (avec une liste de tableaux)?" , alors la réponse est non, car c'est absurde.

ernest_k
la source
1
Le calcul du code de hachage est obligatoire par le Listcontrat . Aucune implémentation valide ne peut se sauter. De la spécification, vous pouvez déduire que si vous trouvez un intnuméro pour lequel x == 31 + xest true, vous pouvez mettre en œuvre un raccourci valide ...
Holger
Je ne comprenais pas vraiment ce que disait @Holger. Mais il y a 2 problèmes avec la solution: Premièrement: Cela ne résout le problème que lorsque cette liste est un élément en soi et non si la liste contient un élément d'un élément en lui-même (couches plus profondes de récursivité) Deuxièmement: Si la liste s'est ignorée, elle peut être égal à une liste vide.
Jonas Michel
1
@JonasMichel Je n'ai pas vraiment proposé de solution. Je ne fais que débattre philosophiquement autour de l'absurdité de la question 2. Si nous devons calculer un code de hachage pour une telle liste, cela ne fonctionnera pas à moins que nous supprimions la contrainte d'une liste de tableaux (et Holger le renforce en disant que cela Listdicte formellement la logique du code de hachage à respecter par les implémentations)
ernest_k
Ma compréhension (limitée) est que Listfournit un calcul de code de hachage, mais que nous pourrions le remplacer. La seule vraie exigence est celle des codes de hachage généraux: si les objets sont égaux, alors les codes de hachage doivent être égaux. Cette implémentation suit cette exigence.
Teepeemm
1
@Teepeemm Listest une interface. Il définit un contrat , il ne fournit pas de mise en œuvre. Bien sûr, le contrat couvre à la fois l'égalité et le code de hachage. Puisque le contrat général d'égalité est qu'il doit être symétrique, si vous changez une implémentation de liste, vous devrez changer toutes les implémentations de liste existantes, sinon, vous briseriez même le contrat fondamental de java.lang.Object.
Holger
1

Parce que lorsque vous appelez la même fonction avec la même fonction, cela crée une condition de récursivité qui ne se termine jamais. Et pour empêcher cette opération, JAVA reviendrajava.lang.StackOverflowError

Voici un exemple de code qui explique un scénario similaire:

public class RefTest {

    public static void main(String... strings) {
        RefTest rf = new RefTest();
        rf.message(message("test"));
    }

    public static String message2(String s){
        return message(s);
    }

    public static String message(String s){
        return message2(s);
    }

}   
Simmant
la source