왜 String의 hashCode()에선 곱하기할때 31을 사용하나요?


자바에서 String객체의 해시 코드는 s[0]*31n-1 + s[1]*31n-2 + ... + s[n-1]이렇게 연산되잖아요. 위 수식을 설명하자면 s[i]는 문자열에서 i번째 문자고 n은 문자열의 길이고 지수를 의미하는데 제가 궁금한건 왜 곱할때 31을 사용하는거죠? 곱할때 큰 소수를 사용해야하는건 이해했는데 왜 29, 37, 97말고 하필 31인거죠?

  • 2016년 01월 18일에 작성됨

조회수 293


1 답변


좋아요
0
싫어요
채택취소하기

이펙티브 자바라는 책을 보면 그부분에 대해 이렇게 설명합니다.

"수식의 31은 소수이기 때문에 선택한 것이다. 만일 이 값이 짝수면서 곱셈의 결과가 오버플로우 되었다면 해시 값이 유실되었을 것이다. 2(의 배수)를 곱한다는 것은 비트의 이동을 의미하기 때문이다. 소수를 사용했을 때 어떤 장점이 있는지는 분명하지 않지만 관례적으로 그렇게 한다. 31의 좋은 점은 비트 이동과 뺄셈으로 곱셈을 대체할 수 있어서 성능을 향상시킬 수 있다는 것이다. 즉 31*i는 (i<<5)-i와 같다. 근래의 자바VM들은 이런 부류의 최적화를 자동적으로 수행한다. "

설명이 됐나요?

  • 2016년 01월 18일에 작성됨

로그인이 필요한 기능입니다.

Hashcode는 개발자들을 위한 무료 QnA사이트 입니다. 작성한 답변에 다른 개발자들이 댓글을 작성하거나 좋아요/싫어요를 할 수 있기 때문에 계정을 필요로 합니다.
► 로그인
► 계정만들기
Close