Können wir das hashcode
von 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:
- Warum gibt es eine
StackOverflowError
? - Ist es möglich, den Hash-Code auf diese Weise zu finden?
java
java-8
stack-overflow
hashcode
Joker
quelle
quelle
List
SchnittstellehashCode
hä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 abhashCode
, was von ihremhashCode
... abhängt, und so weiter, was zu einer unendlichen Rekursion und dem, auf dasStackOverflowError
Sie 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.Antworten:
Der Hash-Code für konforme
List
Implementierungen wurde in der Schnittstelle angegeben :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 + x
musstrue
, mit anderen Worten, es ist unmöglich, eine übereinstimmende Zahl zu berechnen.quelle
hashCode()
um Rückkehr0
. Dies löst technischx == 31 + x
, ignoriert jedoch die Anforderung, dass x mindestens 1 sein muss.ArrayList
buchstä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ührtStackOverflowError
, 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.Arrays.asList("foo")
ist gleichCollections.singletonList("foo")
, ist gleichList.of("foo")
ist gleichnew 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.List
oder ein großes Warnzeichen "Nicht mit normalen Listen mischen" aufweist, vergleiche mitIdentityHashMap
und " Diese Klasse ist keine universelle Map-Implementierung!" " Warnung. Im ersteren Fall können Sie bereitsCollection
die 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.Überprüfen Sie die Skelettimplementierung der
hashCode
Methode in derAbstractList
Klasse.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 trifftStackOverflowError
. So kann man denhashCode
Weg nicht finden .quelle
Sie haben eine (pathologische) Liste definiert, die sich selbst enthält.
Gemäß den Javadocs (dh der Spezifikation) wird der Hashcode von a
List
als eine Funktion des Hashcodes jedes seiner Elemente definiert. Es sagt:Um den Hashcode von zu berechnen, berechnen
a
Sie zuerst den Hashcode vona
. Das ist unendlich rekursiv und führt schnell zu einem Stapelüberlauf.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 .quelle
Nein, die Dokumentation hat eine Antwort
In der Dokumentation der Listenstruktur heißt es ausdrücklich:
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.
quelle
Ravindras Antwort gibt eine gute Erklärung für Punkt 1. Um Frage 2 zu kommentieren:
Hier ist etwas kreisförmig. Mindestens eine dieser beiden muss im Zusammenhang mit diesem Stapelüberlauffehler falsch sein:
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 dasArrayList
Hinzufügen der Hash-Codes von Elementen erweitern und überspringen, so etwas wieVerwenden
ArrayList
Sie stattdessen eine solche Klasse .Mit
ArrayList
ist 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.quelle
List
Vertrag . Keine gültige Implementierung kann sich selbst überspringen. Aus der Spezifikation können Sie ableiten, dass Sie, wenn Sie eineint
Nummer finden, für die diesx == 31 + x
gilttrue
, eine gültigeList
formal diktiert die Hash-Code-Logik, die von Implementierungen eingehalten werden muss)List
eine 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.List
ist 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 brechenjava.lang.Object
.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ück
java.lang.StackOverflowError
Unten finden Sie einen Beispielcode, der ein ähnliches Szenario erklärt:
quelle