Czy możemy znaleźć hashcode
coś, list
co zawiera się jako element
?
Wiem, że to zła praktyka, ale o to pytał ankieter.
Kiedy uruchomiłem następujący kod, generuje on StackOverflowError
:
public class Main {
public static void main(String args[]) {
ArrayList<ArrayList> a = new ArrayList();
a.add(a);
a.hashCode();
}
}
Teraz mam dwa pytania:
- Dlaczego istnieje
StackOverflowError
? - Czy w ten sposób można znaleźć kod skrótu?
java
java-8
stack-overflow
hashcode
Żartowniś
źródło
źródło
List
interfejsuhashCode
lista zależy od jej członków. Biorąc pod uwagę, że lista jest jej własnym członkiem, jej kod skrótu zależy od jejhashCode
, który zależy od jegohashCode
... i tak dalej, powodując nieskończoną rekurencję i napotkanieStackOverflowError
. Teraz pytanie brzmi: dlaczego wymaga się, aby lista się zawierała? Gwarantuję ci, że możesz osiągnąć wszystko, co chcesz zrobić, w lepszy sposób, bez konieczności posiadania takiego członkostwa rekurencyjnego.Odpowiedzi:
Kod skrótu dla zgodnych
List
implementacji został określony w interfejsie :Nie wymaga to, aby implementacja wyglądała dokładnie tak (patrz Jak obliczyć kod skrótu dla strumienia w taki sam sposób jak List.hashCode () dla alternatywy), ale poprawny kod skrótu dla listy zawierającej tylko być liczbą, dla której
x == 31 + x
musi byćtrue
, innymi słowy, niemożliwe jest obliczenie zgodnej liczby.źródło
hashCode()
aby ją zwrócić0
. To technicznie rozwiązuje,x == 31 + x
ale ignoruje wymóg, że x musi wynosić co najmniej 1.ArrayList
implementuje się dosłownie, co prowadzi do rekurencji, ale nie ma też zgodnej alternatywnej implementacji. Zauważ, że opublikowałem moją odpowiedź w czasie, gdy PO już zrozumiał, dlaczego ta konkretna implementacja prowadzi do aStackOverflowError
, co zostało omówione w innych odpowiedziach. Skoncentrowałem się więc na ogólnej niemożności zgodnego wdrożenia, które zakończy się w określonym czasie wartością.Arrays.asList("foo")
jest równaCollections.singletonList("foo")
, jest równaList.of("foo")
jest równanew ArrayList<>(List.of("foo"))
. Wszystkie te listy są równe, punkt. Następnie, ponieważ te listy są równe, muszą mieć ten sam kod skrótu. Nie na odwrót. Ponieważ muszą mieć ten sam kod skrótu, musi być dobrze zdefiniowany. Bez względu na to, jak je zdefiniowali (w Javie 2), musi być dobrze zdefiniowane, do uzgodnienia przez wszystkie implementacje.List
albo ma duży znak ostrzegawczy „nie mieszaj się ze zwykłymi listami”, porównaj z niąIdentityHashMap
i jej „ Ta klasa nie jest implementacją mapy ogólnego przeznaczenia! " ostrzeżenie. W pierwszym przypadku wszystko jest już w porządku z implementacją,Collection
ale także dodaniem metod dostępu opartych na indeksie stylu listy. Wtedy nie istnieje żadne ograniczenie równości, ale nadal działa ono płynnie z innymi typami kolekcji.Sprawdź szkieletową implementację
hashCode
metody wAbstractList
klasie.Wywołuje to dla każdego elementu na liście
hashCode
. W twoim przypadku lista ma się jako jedyny element. Teraz to połączenie nigdy się nie kończy. Metoda wywołuje się rekurencyjnie, a rekurencja kręci się do momentu napotkaniaStackOverflowError
. Więc nie możesz znaleźć whashCode
ten sposób.źródło
Zdefiniowałeś (patologiczną) listę, która zawiera siebie.
Zgodnie z javadocs (tj. Specyfikacją), kod skrótu a
List
jest zdefiniowany jako funkcja kodu skrótu każdego z jego elementów. To mówi:Aby obliczyć kod skrótu
a
, najpierw należy obliczyć kod skrótua
. Jest to nieskończenie rekurencyjne i szybko prowadzi do przepełnienia stosu.Nie. Jeśli weźmiesz pod uwagę powyższą specyfikację algorytmu w kategoriach matematycznych, kod skrótu,
List
który się zawiera, jest funkcją, której nie można obliczyć . Obliczenie go w ten sposób (przy użyciu powyższego algorytmu) lub w inny sposób nie jest możliwe .źródło
Nie, dokumentacja ma odpowiedź
Dokumentacja struktury listy wyraźnie stwierdza:
Poza tym nie ma nic więcej do powiedzenia - zgodnie ze specyfikacją Java, nie będziesz w stanie obliczyć hashCode dla listy, która zawiera; inne odpowiedzi szczegółowo wyjaśniają, dlaczego tak jest, ale chodzi o to, że jest on znany i celowy.
źródło
Odpowiedź Ravindry daje dobre wyjaśnienie dla punktu 1. Aby skomentować pytanie 2:
Coś tu jest okrągłe. Co najmniej jeden z tych 2 musi być niepoprawny w kontekście tego błędu przepełnienia stosu:
Ponieważ mamy do czynienia z
ArrayList
, pierwszy punkt został naprawiony. Innymi słowy, być może potrzebujesz innej implementacji, aby móc w znaczący sposób obliczyć kod skrótu listy rekurencyjnej ... Można rozszerzyćArrayList
i pominąć dodawanie kodów skrótu elementów, coś w rodzajuKorzystając z takiej klasy zamiast
ArrayList
, możesz.Z
ArrayList
, drugi punkt jest błędny. Więc jeśli ankieter miał na myśli „Czy można w ten sposób znaleźć kod skrótu (z listą tablic)?” , więc odpowiedź brzmi nie, bo to absurdalne.źródło
List
umowie . Żadna poprawna implementacja nie może się pominąć. Ze specyfikacji można wywnioskować, że jeśli znajdzieszint
numer, dla któregox == 31 + x
jesttrue
, możesz wprowadzić prawidłowy skrót…List
formalnie dyktat logika kodu skrótu, której mają przestrzegać implementacje)List
zapewnia obliczanie kodu skrótu, ale że możemy go zastąpić. Jedynym prawdziwym wymaganiem jest to, że obowiązują ogólne kody skrótu: jeśli obiekty są równe, wówczas kody skrótu muszą być równe. Ta implementacja spełnia ten wymóg.List
to interfejs. Określa umowę , nie zapewnia wdrożenia. Oczywiście umowa obejmuje zarówno kod równości, jak i kod skrótu. Ponieważ ogólna umowa równości jest taka, że musi być symetryczna, jeśli zmienisz jedną implementację listy, będziesz musiał zmienić wszystkie istniejące implementacje listy, w przeciwnym razie złamiesz nawet podstawową umowęjava.lang.Object
.Ponieważ wywołanie tej samej funkcji z tą samą funkcją spowoduje utworzenie warunku rekurencji, który nigdy się nie kończy. Aby zapobiec tej operacji, JAVA powróci
java.lang.StackOverflowError
Poniżej znajduje się przykładowy kod wyjaśniający podobny scenariusz:
źródło