Kod skrótu ArrayList, który zawiera się jako element

38

Czy możemy znaleźć hashcodecoś, listco 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:

  1. Dlaczego istnieje StackOverflowError?
  2. Czy w ten sposób można znaleźć kod skrótu?
Żartowniś
źródło
7
Ponieważ dodajesz listę do siebie. wypróbuj a.hashCode () bez instrukcji add
Jens
Kiedy wstawiasz obiekt do tablicy, zapisujesz referencję do obiektu. W twoim przypadku umieszczasz ArrayList, która sama jest referencją.
Vishwa Ratna
Ok, rozumiem, dlaczego występuje przepełnienie stosu, czy ktoś może mi pomóc wyjaśnić problem numer 2 - Jak to znaleźć
Joker
9
Jak odpowiedzieli inni, nie jest to możliwe, z samej definicji Listinterfejsu hashCodelista 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 jej hashCode, który zależy od jego hashCode... i tak dalej, powodując nieskończoną rekurencję i napotkanie StackOverflowError. 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.
Alexander - Przywróć Monikę

Odpowiedzi:

36

Kod skrótu dla zgodnych Listimplementacji został określony w interfejsie :

Zwraca wartość kodu skrótu dla tej listy. Kod skrótu listy jest definiowany jako wynik następujących obliczeń:

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

Zapewnia to, że list1.equals(list2)implikuje to list1.hashCode()==list2.hashCode()dla dowolnych dwóch list list1oraz list2, jak wymaga tego ogólna umowa z Object.hashCode().

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 + xmusi być true, innymi słowy, niemożliwe jest obliczenie zgodnej liczby.

Holger
źródło
1
@Holger, Eirc chce zastąpić kod całej funkcji, hashCode()aby ją zwrócić 0. To technicznie rozwiązuje, x == 31 + xale ignoruje wymóg, że x musi wynosić co najmniej 1.
bxk21
4
@EricDuminil moja odpowiedź brzmi: umowa opisuje logikę, która ArrayListimplementuje 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 a StackOverflowError, 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ą.
Holger
2
@pdem nie ma znaczenia, czy specyfikacja używa błędnego opisu algorytmu, formuły, pseudokodu, czy faktycznego kodu. Jak powiedziano w odpowiedzi, kod podany w specyfikacji nie wyklucza ogólnie alternatywnych implementacji. Forma specyfikacji nie mówi nic o tym, czy analiza się wydarzyła, czy nie. Zdanie dokumentacji interfejsu „ Chociaż listy mogą zawierać się jako elementy, zaleca się zachowanie szczególnej ostrożności: metody equals i hashCode nie są już dobrze zdefiniowane na takiej liście ” sugeruje, że taka analiza miała miejsce.
Holger
2
@pdem cofasz go. Nigdy nie powiedziałem, że lista musi być równa ze względu na kod skrótu. Listy z definicji równe. Arrays.asList("foo")jest równa Collections.singletonList("foo"), jest równa List.of("foo")jest równa new 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.
Holger
2
@pdem dokładnie, niestandardowa implementacja, która albo nie implementuje, Listalbo ma duży znak ostrzegawczy „nie mieszaj się ze zwykłymi listami”, porównaj z nią IdentityHashMapi jej „ Ta klasa nie jest implementacją mapy ogólnego przeznaczenia! " ostrzeżenie. W pierwszym przypadku wszystko jest już w porządku z implementacją, Collectionale 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.
Holger
23

Sprawdź szkieletową implementację hashCodemetody w AbstractListklasie.

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

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 napotkania StackOverflowError. Więc nie możesz znaleźć w hashCodeten sposób.

Ravindra Ranwala
źródło
Więc odpowiedź jest taka, że ​​nie ma sposobu, aby znaleźć kod skrótu w ten sposób?
Joker
3
Tak, z powodu stanu rekurencyjnego
springe
Nie tylko to jest zdefiniowane w ten sposób.
Chrylis
14

Zdefiniowałeś (patologiczną) listę, która zawiera siebie.

Dlaczego nie ma StackOverflowError?

Zgodnie z javadocs (tj. Specyfikacją), kod skrótu a Listjest zdefiniowany jako funkcja kodu skrótu każdego z jego elementów. To mówi:

„Kod skrótu listy jest definiowany jako wynik następujących obliczeń:”

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

Aby obliczyć kod skrótu a, najpierw należy obliczyć kod skrótu a. Jest to nieskończenie rekurencyjne i szybko prowadzi do przepełnienia stosu.

Czy w ten sposób można znaleźć kod skrótu?

Nie. Jeśli weźmiesz pod uwagę powyższą specyfikację algorytmu w kategoriach matematycznych, kod skrótu, Listktó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 .

Stephen C.
źródło
Nie wiem, dlaczego ta odpowiedź jest niższa niż dwie pozostałe, ponieważ w rzeczywistości odpowiada na pytania PO z wyjaśnieniami.
Neyt
1
@Niektórzy niektórzy użytkownicy czytają tylko odpowiedzi u góry.
Holger
8

Nie, dokumentacja ma odpowiedź

Dokumentacja struktury listy wyraźnie stwierdza:

Uwaga: Chociaż listy mogą zawierać się jako elementy, zaleca się szczególną ostrożność: metody equals i hashCode nie są już dobrze zdefiniowane na takiej liście.

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.

Piotr jest
źródło
1
Powiedziałeś, dlaczego jest niezgodny ze specyfikacją, więc wyjaśnia, że ​​to nie błąd. Tego brakowało w pozostałych odpowiedziach.
pdem
3

Odpowiedź Ravindry daje dobre wyjaśnienie dla punktu 1. Aby skomentować pytanie 2:

Czy w ten sposób można znaleźć kod skrótu?

Coś tu jest okrągłe. Co najmniej jeden z tych 2 musi być niepoprawny w kontekście tego błędu przepełnienia stosu:

  • że kod skrótu listy musi uwzględniać te z jego elementów
  • że lista może być własnym elementem

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ć ArrayListi pominąć dodawanie kodów skrótu elementów, coś w rodzaju

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

Korzystają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.

ernest_k
źródło
1
Obliczenia kod skrótu jest mandat w Listumowie . Żadna poprawna implementacja nie może się pominąć. Ze specyfikacji można wywnioskować, że jeśli znajdziesz intnumer, dla którego x == 31 + xjest true, możesz wprowadzić prawidłowy skrót…
Holger
Nie do końca rozumiałem, co mówi @Holger. Ale są dwa problemy z rozwiązaniem: po pierwsze: rozwiązuje problem tylko wtedy, gdy ta lista jest elementem samej siebie, a nie, jeśli lista zawiera element samej siebie (głębsze warstwy rekurencji) po drugie: jeśli lista sama go pominęła może być równy pustej liście.
Jonas Michel
1
@JonasMichel Nie zaproponowałem rozwiązania. Ja tylko filozoficznie debaty wokół absurdalność pytanie 2. Jeśli należy obliczyć kod skrótu dla takiej listy jest, to nie będzie działać, chyba że usunąć ograniczenia z listy array (i wzmacnia Holger że mówiąc, że Listformalnie dyktat logika kodu skrótu, której mają przestrzegać implementacje)
ernest_k
Moim (ograniczonym) zrozumieniem jest to, że Listzapewnia 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.
Teepeemm
1
@Teepeemm Listto 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.
Holger
1

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ócijava.lang.StackOverflowError

Poniżej znajduje się przykładowy kod wyjaśniający podobny scenariusz:

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
źródło