Hash-Code von ArrayList, der sich selbst als Element enthält

38

Können wir das hashcodevon einem finden list, das sich selbst enthält als element?

Ich weiß, dass dies eine schlechte Praxis ist, aber das hat der Interviewer gefragt.

Wenn ich den folgenden Code ausgeführt habe, wird ein StackOverflowError:

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

Hier habe ich zwei Fragen:

  1. Warum gibt es eine StackOverflowError?
  2. Ist es möglich, den Hash-Code auf diese Weise zu finden?
Joker
quelle
7
Weil Sie die Liste zu sich selbst hinzufügen. versuche a.hashCode () ohne die add-Anweisung
Jens
Wenn Sie ein Objekt in eine Arrayliste einfügen, speichern Sie die Referenz auf das Objekt. In Ihrem Fall setzen Sie eine ArrayList, die selbst eine Referenz ist.
Vishwa Ratna
Ok, ich habe verstanden, warum es einen Stackoverflow gibt. Kann mir jemand helfen, das Problem Nummer 2 zu erklären? So finden Sie das
Joker
9
Wie andere geantwortet haben, ist dies nicht möglich. Nach der Definition der ListSchnittstelle hashCodehängt das einer Liste von ihren Mitgliedern ab. Angesichts der Tatsache, dass die Liste ein eigenes Mitglied ist, hängt der Hash-Code von ihrem ab hashCode, was von ihrem hashCode... abhängt, und so weiter, was zu einer unendlichen Rekursion und dem, auf das StackOverflowErrorSie stoßen, führt. Die Frage ist nun: Warum benötigen Sie eine Liste, um sich selbst zu enthalten? Ich kann Ihnen garantieren, dass Sie alles, was Sie versuchen, besser erreichen können, ohne eine solche rekursive Mitgliedschaft zu erfordern.
Alexander - Monica

Antworten:

36

Der Hash-Code für konforme ListImplementierungen wurde in der Schnittstelle angegeben :

Gibt den Hashcode-Wert für diese Liste zurück. Der Hash-Code einer Liste ist das Ergebnis der folgenden Berechnung:

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

Dies stellt sicher, list1.equals(list2)dass list1.hashCode()==list2.hashCode()für zwei beliebige Listen list1und list2, wie im Generalvertrag von vorgeschrieben Object.hashCode().

Dies erfordert nicht, dass die Implementierung genau so aussieht (siehe So berechnen Sie den Hash-Code für einen Stream auf die gleiche Weise wie List.hashCode () für eine Alternative), aber der richtige Hash-Code für eine Liste, die nur sich selbst enthält, würde dies tun eine Zahl sein, für die es sein x == 31 + xmuss true, mit anderen Worten, es ist unmöglich, eine übereinstimmende Zahl zu berechnen.

Holger
quelle
1
@Holger will Eirc den Code der gesamten Funktion ersetzen , hashCode()um Rückkehr 0. Dies löst technisch x == 31 + x, ignoriert jedoch die Anforderung, dass x mindestens 1 sein muss.
bxk21
4
@EricDuminil Der Punkt meiner Antwort ist, dass der Vertrag eine Logik beschreibt, die ArrayListbuchstäblich implementiert wird und zu einer Rekursion führt, aber es gibt auch keine konforme alternative Implementierung. Beachten Sie, dass ich meine Antwort zu einem Zeitpunkt veröffentlicht habe, als das OP bereits verstanden hat, warum diese bestimmte Implementierung zu einem führt StackOverflowError, das in anderen Antworten angesprochen wurde. Daher konzentrierte ich mich auf die allgemeine Unmöglichkeit einer konformen Implementierung, die in endlicher Zeit mit einem Wert abgeschlossen wird.
Holger
2
@pdem Es spielt keine Rolle, ob die Spezifikation eine wortreiche Beschreibung eines Algorithmus, einer Formel, eines Pseudocodes oder eines tatsächlichen Codes verwendet. Wie in der Antwort erwähnt, schließt der in der Spezifikation angegebene Code alternative Implementierungen im Allgemeinen nicht aus. Die Form der Spezifikation sagt nichts darüber aus, ob eine Analyse stattgefunden hat oder nicht. Der Satz der Schnittstellendokumentation „ Obwohl es zulässig ist, dass sich Listen als Elemente enthalten, ist äußerste Vorsicht geboten: Die Methoden equals und hashCode sind in einer solchen Liste nicht mehr genau definiert “ deutet darauf hin, dass eine solche Analyse stattgefunden hat.
Holger
2
@pdem du machst es rückgängig. Ich habe nie gesagt, dass die Liste wegen des Hash-Codes gleich sein muss. Die Listen sind per Definition gleich. Arrays.asList("foo")ist gleich Collections.singletonList("foo"), ist gleich List.of("foo")ist gleich new ArrayList<>(List.of("foo")). Alle diese Listen sind gleich, Punkt. Da diese Listen gleich sind, müssen sie denselben Hashcode haben. Nicht umgekehrt. Da sie denselben Hash-Code haben müssen, muss er gut definiert sein. Unabhängig davon, wie sie es definiert haben (zurück in Java 2), muss es gut definiert sein, damit alle Implementierungen zustimmen.
Holger
2
@pdem genau, eine benutzerdefinierte Implementierung, die entweder nicht implementiert ist Listoder ein großes Warnzeichen "Nicht mit normalen Listen mischen" aufweist, vergleiche mit IdentityHashMapund " Diese Klasse ist keine universelle Map-Implementierung!" " Warnung. Im ersteren Fall können Sie bereits Collectiondie auf dem Listenstilindex basierenden Zugriffsmethoden implementieren, aber auch hinzufügen. Dann gibt es keine Gleichheitsbeschränkung, aber es funktioniert immer noch reibungslos mit anderen Sammlungstypen.
Holger
23

Überprüfen Sie die Skelettimplementierung der hashCodeMethode in der AbstractListKlasse.

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

Dies ruft für jedes Element in der Liste auf hashCode. In Ihrem Fall hat sich die Liste als einziges Element. Jetzt endet dieser Anruf nie. Die Methode ruft sich selbst rekursiv auf und die Rekursion wird so lange gewickelt, bis sie auf die trifft StackOverflowError. So kann man den hashCodeWeg nicht finden .

Ravindra Ranwala
quelle
Die Antwort ist also, dass es keine Möglichkeit gibt, den Hash-Code auf diese Weise zu finden.
Joker
3
Ja, wegen der rekursiven Bedingung
springe
Nicht nur das, es ist auch so definiert .
Chrylis
14

Sie haben eine (pathologische) Liste definiert, die sich selbst enthält.

Warum gibt es StackOverflowError?

Gemäß den Javadocs (dh der Spezifikation) wird der Hashcode von a Listals eine Funktion des Hashcodes jedes seiner Elemente definiert. Es sagt:

"Der Hash-Code einer Liste ist das Ergebnis der folgenden Berechnung:"

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

Um den Hashcode von zu berechnen, berechnen aSie zuerst den Hashcode von a. Das ist unendlich rekursiv und führt schnell zu einem Stapelüberlauf.

Ist es möglich, Hash-Code auf diese Weise zu finden?

Nein. Wenn Sie die obige algorithmische Spezifikation mathematisch betrachten, ist der Hashcode von a List, der sich selbst enthält, eine nicht berechenbare Funktion . Es ist nicht möglich, es auf diese Weise (unter Verwendung des obigen Algorithmus) oder auf andere Weise zu berechnen .

Stephen C.
quelle
Ich weiß nicht, warum diese Antwort niedriger ist als die beiden anderen, da sie tatsächlich auf die OP-Fragen mit Erklärungen antwortet.
Neyt
1
@Neyt einige Benutzer lesen nur die Antworten oben.
Holger
8

Nein, die Dokumentation hat eine Antwort

In der Dokumentation der Listenstruktur heißt es ausdrücklich:

Hinweis: Es ist zwar zulässig, dass sich Listen als Elemente enthalten, es ist jedoch äußerste Vorsicht geboten: Die Methoden equals und hashCode sind in einer solchen Liste nicht mehr genau definiert.

Darüber hinaus gibt es nicht viel mehr zu sagen - gemäß der Java-Spezifikation können Sie den HashCode für eine Liste, die sich selbst enthält, nicht berechnen. Andere Antworten gehen ins Detail, warum es so ist, aber der Punkt ist, dass es bekannt und beabsichtigt ist.

Peter ist
quelle
1
Sie haben gesagt, warum es außerhalb der Spezifikation liegt, und es erklärt, dass es kein Fehler ist. Das war der Teil, der in den anderen Antworten fehlte.
pdem
3

Ravindras Antwort gibt eine gute Erklärung für Punkt 1. Um Frage 2 zu kommentieren:

Ist es möglich, Hash-Code auf diese Weise zu finden?

Hier ist etwas kreisförmig. Mindestens eine dieser beiden muss im Zusammenhang mit diesem Stapelüberlauffehler falsch sein:

  • dass der Hash-Code der Liste die seiner Elemente berücksichtigen muss
  • dass es in Ordnung ist, wenn eine Liste ein eigenes Element ist

Nun, da es sich um eine handelt ArrayList, ist der erste Punkt festgelegt. Mit anderen Worten, vielleicht benötigen Sie eine andere Implementierung, um einen Hash-Code einer rekursiven Liste sinnvoll berechnen zu können ... Sie können das ArrayListHinzufügen der Hash-Codes von Elementen erweitern und überspringen, so etwas wie

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

Verwenden ArrayListSie stattdessen eine solche Klasse .

Mit ArrayListist der zweite Punkt falsch. Wenn der Interviewer also meinte: "Ist es möglich, Hash-Code auf diese Weise zu finden (mit einer Array-Liste)?" dann lautet die Antwort nein, denn das ist absurd.

ernest_k
quelle
1
Die Hash - Code - Berechnung wird durch den Auftrag des ListVertrag . Keine gültige Implementierung kann sich selbst überspringen. Aus der Spezifikation können Sie ableiten, dass Sie, wenn Sie eine intNummer finden, für die dies x == 31 + xgilt true, eine gültige
Holger
Ich habe nicht ganz verstanden, was @Holger sagte. Es gibt jedoch zwei Probleme mit der Lösung: Erstens: Dies löst das Problem nur, wenn diese Liste ein Element von sich selbst ist und nicht, wenn die Liste ein Element eines Elements von sich selbst enthält (tiefere Rekursionsebenen). Zweitens: Wenn die Liste sich selbst übersprungen hat könnte gleich einer leeren Liste sein.
Jonas Michel
1
@ JonasMichel Ich habe keine Lösung vorgeschlagen. Ich diskutiere nur philosophisch über die Absurdität von Frage 2. Wenn wir einen Hash-Code für eine solche Liste berechnen müssen , dann funktioniert es nur, wenn wir die Einschränkung einer Array-Liste entfernen (und Holger verstärkt dies, indem er sagt, dass dies Listformal diktiert die Hash-Code-Logik, die von Implementierungen eingehalten werden muss)
ernest_k
Mein (begrenztes) Verständnis ist, dass Listeine Hash-Code-Berechnung bereitgestellt wird, diese jedoch überschrieben werden kann. Die einzige wirkliche Anforderung ist die der allgemeinen Hashcodes: Wenn die Objekte gleich sind, müssen die Hashcodes gleich sein. Diese Implementierung folgt dieser Anforderung.
Teepeemm
1
@Teepeemm Listist eine Schnittstelle. Es definiert einen Vertrag , es bietet keine Implementierung. Natürlich umfasst der Vertrag sowohl die Gleichstellung als auch den Hash-Code. Da der allgemeine Gleichheitsvertrag lautet, dass er symmetrisch sein muss, müssten Sie, wenn Sie eine Listenimplementierung ändern, alle vorhandenen Listenimplementierungen ändern, andernfalls würden Sie sogar den Grundvertrag von brechen java.lang.Object.
Holger
1

Denn wenn Sie dieselbe Funktion mit derselben Funktion aufrufen, wird eine Rekursionsbedingung erstellt, die niemals endet. Und um diesen Vorgang zu verhindern, kehrt JAVA zurückjava.lang.StackOverflowError

Unten finden Sie einen Beispielcode, der ein ähnliches Szenario erklärt:

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
quelle