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

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?

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.

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.

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 .

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.

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.

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);
    }

}