[Java/Java SE, EE] 객체의 해시코드를 반환하는 hashcode(), 해시코드 연산에 31을 사용하는 이유

hashcode()

객체의 해시코드를 반환하는 hashcode() 메소드는 Object 클래스에서 정의하고 있습니다. 따라서 자바의 모든 클래스에서는 hashcode()를 호출 할 수 있습니다.

• 모든 객체에서 호출 가능
• 일반적으로 객체의 메모리 주소를 이용하여 고유한 값을 반환
• 오버라이딩하여 사용 가능

Object 클래스는 hashcode()가 호출되면 객체의 메모리 주소를 이용하여 해시코드를 생성하고 반환합니다. 따라서 두 객체가 동일한 메모리 주소를 참조하는 경우 동일한 해시코드를 갖게됨을 알 수 있습니다.

테스트

간단한 테스트를 위해 Object 클래스의 hashcode() 메소드를 그대로 상속받는 HashcodeTest 클래스를 작성했습니다.

HashcodeTest a = new HashcodeTest(1234);
HashcodeTest b = new HashcodeTest(1234);
HashcodeTest c = b;

System.out.println(a.hashCode());
System.out.println(b.hashCode());
System.out.println(c.hashCode());

객체 a와 b는 새로 인스턴싱되었으므로 서로 다른 메모리 주소를 갖고 있습니다. 반면 객체 c는 b의 메모리 주소를 참조하고 있습니다. 따라서 객체 a와 b는 서로 다른 해시코드를 갖고, 객체 b와 c는 서로 동일한 해시코드를 갖게 됨을 기대 할 수 있습니다. 테스트 코드의 실행 결과는 다음과 같습니다.

1456208737
288665596
288665596

String 클래스의 hashcode()

이전 섹션에서 Object 클래스의 hashcode()는 오버라이딩 될 수 있다고 설명했습니다. 자바의 String 클래스 역시 hashcode()를 오버라이딩하여 사용하고 있습니다.

public static int hashCode(byte[] value) {
    int h = 0;
    int length = value.length >> 1;
    for (int i = 0; i < length; i++) {
        h = 31 * h + getChar(value, i);
    }
    return h;
}

hashcode()의 구현 코드를 살펴보면 String 클래스에 저장된 문자열을 하나씩 꺼내와 아스키 코드를 합한 값을 해시코드 생성에 사용하고 있습니다. 따라서 String은 두 객체가 다른 주소를 참조하더라도 저장된 문자열이 같은 값이면 동일한 해시코드를 반환합니다.

String a = "abcd";
String b = new String("abcd");
String c = String.valueOf("abcd");

// 변수 a와 c는 상수풀을 사용하기 떄문에 a == c
System.out.println(a == b);
System.out.println(b == c);
System.out.println(c == a);

// 변수 a, b, c는 동일한 문자열을 저장하므로 a == b == c
System.out.println(a.hashCode() == b.hashCode());
System.out.println(b.hashCode() == c.hashCode());
System.out.println(c.hashCode() == a.hashCode());

String에서 해시코드를 만들 때 정수 31을 곱하는 이유는 짝수를 곱했을 때 오버플로우 발생에 따른 데이터 손실 가능성이 있기 때문입니다.

int a = Integer.MAX_VALUE;
int b = Integer.MAX_VALUE;
int c = Integer.MAX_VALUE;

System.out.println(a);
System.out.println(b * 3);
System.out.println(c * 2);

예시에서 변수 b와 c에는 각각 홀수 3과 짝수 2를 곱한 결과를 출력합니다. 실행 결과는 다음과 같습니다.

2147483647
2147483645
-2

간단한 예시를 하나 더 살펴보겠습니다. 정수 2에 각각 홀수와 짝수를 곱한 결과를 이진수로 표현하는 코드입니다. 정수에 짝수(2의 배수)를 곱한다는 것은 비트 시프트 연산을 수행하는 것과 같은 결과를 나타냅니다. 따라서 짝수의 곱은 오버플로우가 발생 할 수 있고, 데이터 손실 가능성을 갖고 있음을 의미합니다.

int a = 2;
int b = 2;
int c = 2;
int d = 2;
int e = 2;

System.out.println(Integer.toBinaryString(a));        // 0010
System.out.println(Integer.toBinaryString(b * 3));    // 0110
System.out.println(Integer.toBinaryString(c * 5));    // 1010 

System.out.println(Integer.toBinaryString(a));        // 0010
System.out.println(Integer.toBinaryString(d * 2));    // 0100
System.out.println(Integer.toBinaryString(e * 4));    // 1000

그렇다면 수 많은 홀수 중 왜 하필 31일까요? 31의 장점은 곱셈 연산을 비트 시프트 연산과 뺄셈으로 대체 할 수 있기 때문입니다. 연산이 오래 걸리는 곱셈보다는 비트 시프트 연산과 뺄셈을 사용하여 성능상 이점을 얻을 수 있기 때문입니다. 하지만 근래의 자바 VM에서는 자동으로 최적하하기 때문에 다른 홀수를 사용하여도 무관합니다.

value * 31 == (value << 5) - value;