Java의 문자열 hashCode()가 승수로 31을 사용하는 이유는 무엇입니까?

String에서 Java의 hashCode()가 31을 승수로 사용하는 이유

Java에서 String 객체의 해시 코드는 다음을 사용하여 계산됩니다. 공식:

s[0]*31^(n-1) + s[1]*31^(n-2) + ... + s[n-1]

여기서 s[i]는 i번째 문자입니다. n은 문자열의 길이이고 ^는 지수를 나타냅니다.

소수 승수의 중요성

이 공식의 주요 측면 중 하나는 소수를 사용하면 해시 충돌 가능성을 줄일 수 있다는 장점이 있습니다. 소수가 아닌 승수를 사용하면 동일한 해시 값을 가진 두 문자열이 공통 인수를 공유할 수 있으므로 해시 충돌이 더 쉽게 발생할 수 있습니다.

왜 또 다른 소수가 아닌가?

31은 홀수 소수이지만 29, 37, 97 등 선택될 수 있는 다른 소수도 있습니다. 31의 선택은 여러 요소의 조합을 기반으로 했습니다:

• 오버플로 방지: 31은 상대적으로 작은 소수로, 곱셈 과정에서 정수 오버플로의 위험을 줄여줍니다. 짝수 소수를 사용하는 경우 2를 곱할 때 오버플로가 발생하여 정보가 손실될 수 있습니다.
• 성능 최적화: Joshua Bloch가 "Effective Java"에서 언급한 것처럼 31을 곱하면 보다 효율적인 이동 및 빼기 연산으로 대체됩니다. 31 * i == (i
• 전통: 해시 함수에 소수 승수를 사용하는 것은 오랜 관행이며, 31이 특히 인기 있는 선택이었습니다. 31을 특별히 선택한 명확한 이유는 없지만 많은 프로그래밍 언어 및 애플리케이션에서 표준 선택이 되었습니다.

위 내용은 Java의 문자열 hashCode()가 승수로 31을 사용하는 이유는 무엇입니까?의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!