왜 hashCode에서 승수로 31을 사용할까?

  hashCode를 구현할 때 31 숫자를 많이 사용한다. 그래서 그 이유에 대해서 찾아보았다.

 

홀수인 소수이다

  첫번째로 31은 소수이기 때문에 사용된다. 소수인 경우에는 값을 곱하였을 때 더 분산이 잘 된다. 만약 소수가 아닌 경우(다른 수로도 배수가 만들어지는 경우)에 충돌이 발생하기 쉽기 때문이다. 짝수로 해시값이 나오는 경우에는 홀수 번째 자리를 효율적으로 사용하지 못한다. 따라서 소수를 사용해서 충돌을 최대한 방지하는 것이다.

 

쉬프트 연산을 사용할 수 있다

  X * 31은 쉬프트 연산과 뺄셈 연산으로 표현할 수 있다.

1. X * 31
2. X * (32 - 1)
3. X * 32 - X
4. X << 5 - X

  최종적으로 X << 5 - X로 표현이 가능하다. 곱셈보다 쉬프트 연산이 속도가 더 빠르기 때문에 성능적으로 장점이 있다.

 

참고

• https://stackoverflow.com/questions/299304/why-does-javas-hashcode-in-string-use-31-as-a-multiplier
• https://www.quora.com/Why-is-31-used-in-Hashcode