Java의 `String.hashCode()`가 승수로 31을 사용하는 이유는 무엇입니까?

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

Java에서 String 객체의 hashCode() 메서드는 다음을 사용합니다. 공식:

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

여기서 s[i]는 i번째입니다. 문자에서 n은 문자열 길이이고 ^는 지수를 나타냅니다. 이로 인해 질문이 제기됩니다. 왜 31이 승수로 선택되었나요?

소수 승수의 이론적 근거

문서에서는 상대적으로 큰 소수를 승수로 사용하도록 제안합니다. 해시 테이블의 충돌을 최소화합니다. 충돌은 서로 다른 개체가 동일한 해시 코드를 생성할 때 발생하며 잠재적으로 성능 문제를 일으킬 수 있습니다. 소수는 해시 코드의 더 나은 분포를 제공하여 충돌 가능성을 줄입니다.

왜 다른 소수가 아닌가?

다른 소수 중에서 31을 선택한 것은 두 가지에 기인합니다. 요인:

1. 오버플로 방지: 승수가 짝수인 경우 곱셈이 오버플로되면 정보가 손실됩니다. 이는 2를 곱하는 것이 시프트 연산과 동일하기 때문입니다.
2. 성능 최적화: 값 31은 곱셈을 시프트 및 뺄셈으로 대체할 수 있는 최적화를 허용합니다. 31 * i = = (i

따라서 31은 소수라는 두 가지 기준을 모두 충족하여 충돌을 방지하는 동시에 Java에서 문자열 객체에 대한 효율적인 해싱 작업을 가능하게 합니다.

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