[Java] "서로 다른 두 객체는 결코 같은 해시코드를 가질 수 없다."?

자바의 정석 453쪽에 보면 "서로 다른 두 객체는 결코 같은 해시코드를 가질 수 없다."라는 말이 나와있다.

 

 

물론 Object의 hashCode는 오버라이드가 가능하므로 다음과 같이 코드를 짠다면 무조건 같은 해시코드만 반환이 될 것이다.

public class Foo {
    @Override
    public int hashCode() {
        return 1;
    }
    public static void main(String[] args) {
        Foo foo1 = new Foo();
        Foo foo2 = new Foo();

        System.out.println(foo1 == foo2);
        System.out.println(foo1.hashCode() == foo2.hashCode());
    }
}

위의 코드를 실행한다면

false
true

가 나온다.

 

내가 궁금한 것은 오버라이드를 하지 않은 모든 클래스의 부모인 Object.hashCode 원래 코드가 다른 두 객체가 같은 해시코드를 가질 수 없느냐는 것이다.

비둘기 집의 원리

자바 언어 스펙에서는 인스턴스화 할 수 있는 객체의 개수에 대해 제한을 명시하고 있지 않다.

반면 hashCode() 가 반환하는 타입은 int이다. 즉, 2^32 만큼의 경우의 수로 제한이 된다.

따라서 객체의 개수가 늘어날 수록 동일한 해시코드를 가질 수 있는 가능성은 높아진다.
더군다나 64비트 체계에서는 메모리주소 크기가 int의 범위를 초과한다.

따라서 해당 명제는 틀렸다.

반례에 의한 증명

"서로 다른 두 객체는 결코 같은 해시코드를 가질 수 없다." 가 틀렸음을 증명하기 위해서는

서로 다른 두 객체가 동일한 해시코드를 가질 수 있음을 예로 들어보이면 된다.

이러한 예를 반례라고 한다.

 

다음과 같은 코드를 돌려보면 된다.

public class IsAllObjectDistinguishHashcode {
    public static void main(String[] args) {
        Map<Integer, Object> objectMap = new HashMap<>();

        for (long i = Integer.MIN_VALUE; i < Integer.MAX_VALUE + 1L; i++) {
            Object obj = new Object();
            int hashCode = obj.hashCode();

            Object beforeObj = objectMap.get(hashCode);
            if (beforeObj != null) {
                System.out.println("Repeat " + (i - Integer.MIN_VALUE + 1L));
                System.out.println("before: " + beforeObj.hashCode());
                System.out.println("later: " + obj.hashCode());
                System.out.println("Is same: " + beforeObj == obj);
                return;
            }

            objectMap.put(hashCode, obj);
        }
    }
}

객체를 생성해서 해시맵에 넣는다. 키는 바로 hashCode의 값이고, 값은 객체를 넣는다.

Map에서 get을 했을 때 null이 아니라는 것은 해당 해시값이 이미 점유하고 있다고 볼 수 있다.

 

위의 코드를 돌려보면, 다음과 같은 결과가 나온다.
(환경에 따라 충돌된 반복(Repeat)과 해시값은 다를 수 있다. java version "11.0.2" 2019-01-15 LTS 에서 돌렸다.)

Repeat 104892
before: 2134400190
later: 2134400190
false

104,892번째 객체를 생성했을 때 hashCode가 2134400190 라는 값으로 충돌함을 알 수 있다.

객체의 동일성 비교(==)의 결과는 false이다.

즉, 다른 객체지만 동일한 hashCode를 반환할 수 있다는 이야기이다.