hashCode와 31

Java의 hashCode 메소드를 살펴보면 31을 곱하는 경우를 자주 발견할 수 있습니다.
하필이면 왜 31을 곱하는 걸까요? 그냥 넘어가도 될 부분이지만 문뜩 궁금해져서 조사해보았습니다.

목표

🎯 Hash가 무엇인지 알아봅니다.
🎯 비트연산에 대해서 이해합니다.
🎯 Stirng class의 hashCode 메소드에서 왜 31을 더하는지 생각해봅니다.

String Class의 hashCode 메소드 살펴보기

//String
public int hashCode() {
        int h = hash;
        if (h == 0 && value.length > 0) {
            hash = h = isLatin1() ? StringLatin1.hashCode(value)
                                  : StringUTF16.hashCode(value);
        }
        return h;
    }

String class의 hashCode메소드를 살펴보면 위와 같습니다.(Open JDK 11)
현재 객체의 인코딩을 기준으로 분기하여 StringLatin1과 StringUTF16의 hashCode()를 호출하고 있습니다.
두 객체의 hashCode()는 계산과정이 유사하므로 StringUTF16객체의 메소드를 기준으로 살펴보겠습니다.

// StringUTF16
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;
    }

문자열이 담겨있는 value로부터 순차적으로 접근하여 character 값을 받아와 31을 곱하고 있습니다.
왜 31을 곱하는 걸까요?
그냥 2를 곱하면 안되는걸까?
아니면 음... 지금 딱 떠오른 수인 54를 곱하면 안될까요?
이 질문에 대해서 살펴보려면 우선 배경되는 지식들이 있으니 이것부터 살펴보려고 합니다.

Hash가 뭐에요?

우리는 hashCode라는 메소드가 어떻게 연산하는지 알아보고 있습니다.
그렇다면 hash라는 것이 어떤 것을 의미하는지 용어부터 살펴보는 것이 좋겠습니다.
위키백과를 살펴보도록하죠.

해쉬함수

해시 함수(hash function) 또는 해시 알고리즘(hash algorithm) 또는 해시함수알고리즘(hash函數algorithm)은 임의의 길이의 데이터를 고정된 길이의 데이터로 매핑하는 함수이다. 해시 함수에 의해 얻어지는 값은 해시 값, 해시 코드, 해시 체크섬 또는 간단하게 해시라고 한다. - 위키백과

여기서 포인트는 바로 "매핑"입니다. Hash Function은 일종의 Mapping Function인 것입니다.
이는 암호학이나 HashMap같은 자료구조에도 이용됩니다.
hash 알고리즘을 통해 생성된 데이터는 원본 데이터가 어떤 데이터인지 유추하기 어렵다는 성질을 가지고 있어서 암호학에 활용됩니다. 이러한 성질의 예로 대표적으로 아주 큰 합성수가 어떤 두 소수로 이뤄져있는지 찾아내기가 힘들다는 것이 있습니다.
또한 어떤 길이의 데이터라도 고정된 데이터로 바뀐다는 점과 같은 값을 넣으면 같은 결과를 가진다는 성질을 이용하여 빠르게 데이터를 검색할 수 있다는 장점을 얻을 수 있습니다. 이러한 성질을 통해 HashMap 자료구조에서는 같은 key값으로 항상 같은 value를 얻을 수 있습니다. 이때의 시간복잡도는 O(1)을 갖게 됩니다. 물론 해쉬충돌이 일어날 수록 O(N)에 가까워집니다. 여기서 해쉬충돌이란 다른 데이터를 input했는데 같은 hash결과가 나왔 때를 의미하고 이에 대한 해결방법도 다양히 존재합니다.
이러한 HashMap 자료구조에 대한 이야기는 이 문서에서 자세히 다루진 않겠습니다.
중요한 것은 String class의 hashCode라는 메소드에 왜 hash라는 단어가 들어갔느냐 입니다.
이 메소드는 String 객체가 가지고 있는 문자열을 어떤 정수값으로 매핑한다 라고 이해하시면 될 것 습니다.

Shift 연산이 뭐에요?

우리는 String 클래스의 hashCode()가 임의의 문자열을 어떤 정수값으로 매핑해준다는 것을 알 수 있습니다. 그리고 매핑을 위해서 31 곱한다는 것도 알 수 있습니다.

그렇다면 우리는 컴퓨터가 곱하기를 하는 과정에 대해서 살펴볼 필요가 있습니다.
그래야 31을 곱할 때 자바에서 어떤 일이 일어나는지 알 수 있습니다.
이는 아래 문서를 살펴보시면 간단하게 파악하실 수 있습니다.

쉬프트 연산 - 해시넷

즉, 이진수에서 2의 배수를 곱하는 것은 shift연산을 하는 것과 같은 것입니다.
간단한 예를 살펴보겠습니다.

이진수 (1byte)에서의 shift(<<)연산
0000 0101(2) = 5
0000 1010(2) = 5 X 2
0001 0100(2) = 5 X 2 X 2

즉, 어떤 수 a에 2의 n제곱을 곱한 것은 shift연산 a << n 과같습니다.
이는 아래와 같은 java코드로 확인해볼 수 있습니다.

    public static void main(String[] args) {
        for(int j = 0; j < 10; j ++){
            x = 5 << j;
            y = 5 * (int)Math.pow(2, j);
            System.out.printf("x == y(%d) :  %b %n", x , y, j, (y == x));
        }
    }

    // 결과
    5 = 5(0) :  true 
	10 = 10(1) :  true 
    20 = 20(2) :  true 
    40 = 40(3) :  true 
    80 = 80(4) :  true 
    160 = 160(5) :  true 
    320 = 320(6) :  true 
    640 = 640(7) :  true 
    1280 = 1280(8) :  true 
	....

컴퓨터 입장에서는 비트를 옆으로 한 칸씩 옴기는 것이 곱하기 연산을 하는 것보다 더 간편할 것입니다.
JVM에서는 이러한 최적화가 이루워져있습니다.
다만 쉬프트 연산 시 짝수로 곱해 오버플로우가 일어날 시 오른쪽은 모두 0으로 차게 되고 이 경우 정보의 손실이 있기 때문에 홀수를 곱해야 합니다.

0000 0101 = 5
0001 0100 = 5 << 1
0010 1000 = 5 << 2
0101 0000 = 5 << 3
1010 0000 = 5 << 4
0100 0000 = 5 << 5
1000 0000 = 5 << 6
0000 0000 = 5 << 7
...이와 같은 일이 일어나는 겁니다 😅
위에서 곱하기 hash를 할 때 쉬프트 연산의 값이 7이상으로 커지면 해쉬충돌이 일어날 가능성이 높아지는 것이죠

JVM에서 홀수의 곱을 할 때는 다음과 같이 최적화 됩니다.

a * 31은 JVM에서 a << 5 - a으로 계산한다.

즉 31을 곱하게 되면 쉬프트 연산과 뻴셈연산을 통해서 오른쪽에 채워지는 데이터가 0이 아닌 다른 값으로 올 수가 있습니다.

이에 대해서는 이진수의 뺄셈연산 시 2의 보수를 취해주는 것과 연관이 있습니다.
아래 문서를 참고해주시기 바랍니다.
2의 보수와 뺄셈 - 위키백과

그래서 왜 31을 곱하는거에요?

위의 내용들로 생각해볼 때 사실 어떤 홀수를 곱하더라도 상관이 없습니다.
이에 대해서 이펙티브 자바 2판의 저자인 Joshua Bloch은 다음과 같이 책에서 언급하였습니다.

31은 소수이면서 홀수이기 때문에 선택된 값이다. 만일 그 값이 짝수였고 곱셈 결과가 오버플로되었다면 정보는 사라졌을 것이다. 2로 곱하는 것은 비트를 왼쪽으로 shift하는 것과 같기 때문이다. 소수를 사용하는 이점은 그다지 분명하지 않지만 전통적으로 널리 사용된다. 31의 좋은 점은 곱셈을 시프트와 뺄셈의 조합으로 바꾸면 더 좋은 성능을 낼 수 있다는 것이다(31 * i는 (i << 5) - i 와 같다). 최신 VM은 이런 최적화를 자동으로 실행한다.

위 내용에서 31이 홀수이므로 선택되었다는 것은 이해가 갑니다. 하지만 소수이기 때문에 선택했다는 것에 대해서는 의문이 아직 남습니다. 합성수이면 안되는 걸까요? 사실 합성수로 곱하는 경우도 있다고 합니다.
Joshua Bloch가 언급한 바로 보면 그저 관행적으로 31을 곱한다고 말할 수 있습니다. 🤫
실제로 31보다 더 효율적인 계산결과를 얻을 수 있는 숫자도 많습니다.

롬복의 사례

Project Lombok의 EqualsAndHashCode어노테이션 document
롬복의 hashCode 메소드의 구현을 보면 다음과 같습니다.

@Override public int hashCode() {
    final int PRIME = 59;
    int result = 1;
    final long temp1 = Double.doubleToLongBits(this.score);
    result = (result*PRIME) + (this.name == null ? 43 : this.name.hashCode());
    result = (result*PRIME) + (int)(temp1 ^ (temp1 >>> 32));
    result = (result*PRIME) + Arrays.deepHashCode(this.tags);
    return result;
  }

PRIME이라는 지역변수는 59의 소수로 선언되어있습니다. 59도 31의 사례와 같이 쉬프트 연산과 빼기연산을 사용하여 계산할 수 있습니다.
이렇게 보면 31이 꼭 사용해야하는 숫자는 아니라고 생각해볼 수 있습니다.

결론

🎯 인터넷을 여기저기 뒤지고 다니며 알아보았지만, 허무하게도 31은 어떤 특별한 숫자가 아니였습니다.
하지만 여기서 중요한 것은 31이란 숫자가 아닌 것 같습니다.
hash나 shift 연산과 보수에 대한 개념을 아는 것이 중요하다고 생각합니다.
어떤 수를 곱하거나 나누더라도 hash 알고리즘에 적당한 수를 찾아낼 수 있다면 그 수를 사용하면 될 것입니다.

정리

1. String의 hashCode메소드를 실행하면 문자열의 각 Character를 순회하며 31을 곱한다.
2. HashFunction이랑 매핑 함수로 생각해볼 수 있다. 즉 String에서의 hashCode 메소드는 문자열을 정수로 매핑한다는 의미이다.
3. 이 매핑방식에는 곱하시 hash가 있는데, 이때 짝수로 곱하면 다음과 같은 문제가 발생한다.
4. 컴파일러는 짝수 곱을 왼쪽 쉬프트 연산으로 처리한다.
5. 충분히 큰 짝수를 곱하게 되면 왼쪽으로 한칸씩 비트를 옴기면서 오른쪽을 0으로 채운다.
6. 이 방식으로 계속하여 왼쪽으로 쉬프트 연산을 하면 결국 기존 모든 비트가 overflow되고 0만 가득차게된다.
7. 이렇게 충분히 짝수를 곱하면 Hash 충돌이 일어날 가능성이 높아지기에 홀수를 곱하게된다.
8. 소수를 선택하는 이유는 관례나 미신에 가깝다. 합성수인 홀수를 선택하는 사례도 있다.