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

조회수 3765회

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

1 답변

  • 좋아요

    0

    싫어요
    채택 취소하기

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

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

    설명이 됐나요?

답변을 하려면 로그인이 필요합니다.

프로그래머스 커뮤니티는 개발자들을 위한 Q&A 서비스입니다. 로그인해야 답변을 작성하실 수 있습니다.

(ಠ_ಠ)
(ಠ‿ಠ)