왜 String의 hashCode()에선 곱하기할때 31을 사용하나요?
조회수 3767회
자바에서 String객체의 해시 코드는 s[0]*31n-1 + s[1]*31n-2 + ... + s[n-1]이렇게 연산되잖아요. 위 수식을 설명하자면 s[i]는 문자열에서 i번째 문자고 n은 문자열의 길이고 는 지수를 의미하는데 제가 궁금한건 왜 곱할때 31을 사용하는거죠? 곱할때 큰 소수를 사용해야하는건 이해했는데 왜 29, 37, 97말고 하필 31인거죠?
1 답변
-
이펙티브 자바라는 책을 보면 그부분에 대해 이렇게 설명합니다.
"수식의 31은 소수이기 때문에 선택한 것이다. 만일 이 값이 짝수면서 곱셈의 결과가 오버플로우 되었다면 해시 값이 유실되었을 것이다. 2(의 배수)를 곱한다는 것은 비트의 이동을 의미하기 때문이다. 소수를 사용했을 때 어떤 장점이 있는지는 분명하지 않지만 관례적으로 그렇게 한다. 31의 좋은 점은 비트 이동과 뺄셈으로 곱셈을 대체할 수 있어서 성능을 향상시킬 수 있다는 것이다. 즉 31*i는 (i<<5)-i와 같다. 근래의 자바VM들은 이런 부류의 최적화를 자동적으로 수행한다. "
설명이 됐나요?
댓글 입력