[java] 자신을 요소로 포함하는 ArrayList의 해시 코드

Program / 글쓴이

자체를 포함 hashcode하는의 list를 찾을 수 있습니까 element?

나는 이것이 나쁜 습관이라는 것을 알고 있지만 이것은 면접관이 요구 한 것입니다.

다음 코드를 실행하면 다음이 발생합니다 StackOverflowError.

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

이제 두 가지 질문이 있습니다.

  1. 왜 StackOverflowError있습니까?
  2. 이런 식으로 해시 코드를 찾을 수 있습니까?

답변

적합한 List구현 을 위한 해시 코드 가 인터페이스에 지정되었습니다 .

이리스트의 해시 코드 값을 리턴합니다. 목록의 해시 코드는 다음 계산 결과로 정의됩니다.

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

이를 통해 두 목록에 대한 및 의 일반 계약에서 요구하는 사항 을 list1.equals(list2)암시합니다 .list1.hashCode()==list2.hashCode()list1list2Object.hashCode()

이것은 구현이 정확히 그렇게 보일 필요는 없지만 ( 대안의 경우 List.hashCode ()와 같은 방식으로 스트림의 해시 코드를 계산하는 방법 참조 ) 자체를 포함하는 목록의 올바른 해시 코드는 즉, 일치하는 숫자를 계산할 수없는 숫자 x == 31 + x여야합니다 true.

답변

클래스 에서 hashCode메소드 의 골격 구현을 확인하십시오 AbstractList.

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

목록의 각 요소에 대해을 호출합니다 hashCode. 귀하의 경우 목록은 유일한 요소입니다. 이제이 전화는 끝나지 않습니다. 이 메소드는 재귀 적으로 호출되며 재귀는를 만날 때까지 계속 감습니다 StackOverflowError. 따라서이 hashCode방법을 찾을 수 없습니다 .

답변

자체가 포함 된 (병리학 적) 목록을 정의했습니다.

왜 StackOverflowError있습니까?

javadocs (즉, 스펙) 에 따르면 , Lista의 해시 코드는 각 요소의 해시 코드 함수에 정의됩니다. 그것은 말한다 :

“목록의 해시 코드는 다음 계산 결과로 정의됩니다.”

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

의 해시 코드를 계산 a하려면 먼저의 해시 코드를 계산합니다 a. 그것은 무한히 재귀 적이며 스택 오버플로로 빠르게 이어집니다.

이 방법으로 해시 코드를 찾을 수 있습니까?

아닙니다 . 위의 알고리즘 사양을 수학 용어로 고려하면 List자체를 포함 하는의 해시 코드는 계산할 수없는 함수 입니다. 이 방법으로 (위의 알고리즘을 사용하여) 또는 다른 방법으로 는 계산할 수 없습니다 .

답변

아니요, 설명서에 답이 있습니다

List 구조 의 문서는 다음과 같이 명시 적으로 설명되어 있습니다.

참고 :리스트가 자신을 요소로 포함하는 것이 허용되지만 극도의주의가 필요합니다. equals 및 hashCode 메소드는 더 이상 이러한리스트에서 잘 정의되지 않습니다.

Java 사양에 따르면 자신을 포함하는 목록에 대해 hashCode를 계산할 수 없습니다. 다른 답변은 그 이유에 대해 자세히 설명하지만 요점은 그것이 알려지고 의도적이라는 것입니다.

답변

Ravindra의 답변은 포인트 1에 대한 좋은 설명입니다. 질문 2 :

이런 식으로 해시 코드를 찾을 수 있습니까?

여기에 원형이 있습니다. 이 스택 오버플로 오류와 관련하여 다음 중 하나 이상이 잘못되어야합니다.

  • 목록의 해시 코드는 요소의 해시 코드를 고려해야합니다
  • 리스트가 자신의 요소가되는 것은 괜찮습니다.

이제 우리는를 다루기 때문에 ArrayList첫 번째 요점이 고정되었습니다. 다시 말해, 재귀 목록의 해시 코드를 의미있게 계산하려면 다른 구현이 필요할 수 있습니다. ArrayList요소의 해시 코드 추가를 확장 하거나 건너 뛸 수 있습니다.

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

대신 이러한 클래스를 사용 ArrayList하면 가능합니다.

로 ArrayList두 번째 요점이 잘못되었습니다. 인터뷰자가 “이러한 방식으로 (배열 목록으로) 해시 코드를 찾을 수 있습니까?” 그 말은 터무니없는 대답입니다.

답변

같은 함수에서 같은 함수를 호출하면 결코 끝나지 않는 재귀 조건을 생성하기 때문입니다. 그리고이 작업을 방지하기 위해 JAVA는java.lang.StackOverflowError

다음은 유사한 시나리오를 설명하는 예제 코드입니다.

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

}

답변