hashCode에 소수점을 사용하는 이유는 무엇입니까?

hashCode에 소수점을 사용하는 이유는 무엇입니까?

?hashCode()★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★hashCode()은 31 삭제:

public int hashCode() {
     final int prime = 31;
     //...
}

참고 자료:

다음은 해시 코드에 대한 좋은 입문서와 내가 발견한 해싱의 구조에 대한 기사입니다(C# 단, 개념은 전송 가능합니다).Eric Lippert의 GetHashCode() 가이드라인 및 규칙

소수점은 해시 버킷 간에 데이터를 가장 잘 분배하기 위해 선택됩니다.입력의 분포가 랜덤하고 균등하게 분산되어 있는 경우 해시 코드/계수의 선택은 중요하지 않습니다.입력에 특정 패턴이 있을 때만 영향을 미칩니다.

이것은 메모리 위치를 다룰 때 자주 발생합니다.예를 들어, 32비트 정수는 모두 4로 나눌 수 있는 주소로 정렬됩니다.프라임 계수 대 비프라임 계수 사용의 효과를 시각화하려면 아래 표를 참조하십시오.

Input       Modulo 8    Modulo 7
0           0           0
4           4           4
8           0           1
12          4           5
16          0           2
20          4           6
24          0           3
28          4           0

소수 계수 대 비 소수 계수 사용 시 거의 완벽한 분포에 주목하십시오.

단, 위의 예는 대부분 계획되어 있지만, 일반적인 원칙은 입력 패턴을 다룰 때 소수 계수를 사용하는 것이 최선의 분포를 산출한다는 것입니다.

곱하는 숫자와 삽입하는 버킷 수에 직교 소인수를 가지려고 하기 때문입니다.

삽입할 버킷이 8개 있다고 가정합니다.곱셈에 사용하는 숫자가 8의 몇 배일 경우 에 삽입된 버킷은 최하위 엔트리(전혀 곱셈되지 않음)에 의해서만 결정됩니다.유사한 엔트리가 충돌합니다.해시 함수에는 적합하지 않습니다.

31은 버킷의 수가 분할될 가능성이 거의 없을 정도로 큰 소수입니다(실제로 최신 Java HashMap 구현에서는 버킷의 수를 2의 거듭제곱으로 유지합니다).

Effective Java 2nd Edition에서는 수학 문제에 대해 설명하면서 31을 선택하는 이유는 다음과 같습니다.

• 왜냐하면 홀수 소수이고 소수점을 사용하는 것은 "전통적"이기 때문이다.
• 또한 2의 거듭제곱보다 1이 적기 때문에 비트 단위의 최적화가 가능합니다.

다음은 항목 9의 전체 인용문입니다. 재정의할 때 항상 재정의합니다.

31은 홀수 소수이기 때문에 선택되었습니다.짝수이고 곱셈 오버플로우일 경우 2의 곱셈은 이동과 같기 때문에 정보가 손실됩니다.프라임 사용의 장점은 명확하지 않지만, 전통적이다.

31의 좋은 특성은 곱셈을 시프트(θ15.19)와 뺄셈으로 대체할 수 있다는 것입니다.

 31 * i == (i << 5) - i

최신 VM은 이러한 최적화를 자동으로 수행합니다.

---

이 항목의 레시피는 상당히 좋은 해시 함수를 제공하지만 최신 해시 함수를 제공하지는 않습니다.또한 Java 플랫폼 라이브러리는 릴리스 1.6을 기준으로 이러한 해시 함수를 제공하지 않습니다.이러한 해시함수를 쓰는 것은 수학자와 이론 컴퓨터 과학자들에게 맡기는 것이 가장 좋은 연구 주제이다.

아마도 플랫폼의 이후 릴리스는 클래스 및 유틸리티 메서드를 위한 최첨단 해시 함수를 제공하여 일반 프로그래머가 이러한 해시 함수를 구성할 수 있도록 할 것이다.한편, 이 항목에서 설명하는 기법은 대부분의 애플리케이션에 적합해야 합니다.

간단히 말하면, 다수의 제수가 있는 승수를 사용하면 더 많은 해시 충돌이 발생한다고 할 수 있습니다.효과적인 해시를 위해 충돌 횟수를 최소화하고 싶기 때문에 제수가 적은 승수를 사용하려고 합니다.정의상 소수는 정확히 두 개의 서로 다른 양의 제수를 가지고 있다.

관련 질문

• 하나의 필드에서 Java hashCode - 레시피와 Apache Commons Lang의 빌더를 사용하는 예
• 객체의 해시 코드를 모든 클래스 변수 해시 코드의 합계, 곱셈, 기타로 정의하는 것은 올바르지 않은가?
• 비트 시프트에 대한 절대적인 초보자 가이드?

컴파일러가 곱셈을 왼쪽 5비트로 최적화하고 값을 뺄 수 있도록 31이 선택되었다고 합니다.

여기 출처와 좀 더 가까운 인용문이 있습니다.

요약하면 다음과 같습니다.

• 31은 충돌을 줄이는 소수입니다.
• 31은 적절한 분포를 생성하며,
• 속도에서의 합리적인 트레이드오프

모듈로 2^32의 )를합니다.int2^32로 비교적 소수가 필요한 경우(소수는 공통 제수가 없다는 것을 의미합니다).그건 홀수라도 상관없습니다.

그런 다음 특정 해시 테이블에 대해 인덱스는 보통 해시 테이블 크기의 해시 값 모듈로 계산되므로 해시 테이블 크기에 비해 비교적 작은 값을 원합니다.해시 테이블의 사이즈는, 그러한 이유로 소수로서 선택되는 경우가 많습니다.Java의 경우 Sun 구현에서는 크기가 항상 2의 거듭제곱이므로 홀수로도 충분합니다.또한 충돌을 더 제한하기 위해 해시 키를 추가로 마사지할 수도 있습니다.

해시 테이블과 승수가 공통 인자를 갖는 경우의 악영향n특정 상황에서는 해시 테이블의 1/n 엔트리만 사용될 수 있습니다.

소수가 사용되는 이유는 데이터가 특정 패턴을 나타낼 때 충돌을 최소화하기 위해서입니다.

첫 번째: 데이터가 랜덤일 경우 소수가 필요 없으며 임의의 숫자에 대해 mod 연산을 수행할 수 있으며 modulus의 각 가능한 값에 대해 동일한 수의 collision이 발생합니다.

그러나 데이터가 랜덤이 아닐 경우 이상한 일이 발생합니다.예를 들어, 숫자 데이터는 항상 10의 배수입니다.

mod 4를 사용하면 다음과 같은 결과가 나옵니다.

10 mod 4 = 2

20 mod 4 = 0

30 mod 4 = 2

40 mod 4 = 0

50 mod 4 = 2

따라서 계수(0,1,2,3)의 3가지 가능한 값 중 0과 2만이 충돌합니다. 이는 좋지 않습니다.

7과 같은 소수를 사용하는 경우:

10 mod 7 = 3

20 mod 7 = 6

30 mod 7 = 2

40 mod 7 = 4

50 mod 7 = 1

기타

또한 5는 좋은 선택은 아니지만 5가 가장 좋은 선택입니다.왜냐하면 모든 키가 5의 배수이기 때문입니다.이것은 키를 나누지 않는 소수를 선택해야 한다는 것을 의미합니다. 보통 큰 소수를 선택하면 충분합니다.

따라서 반복적인 편에서 오류가 발생하는 이유는 해시함수의 충돌 분포에서 키의 패턴 효과를 중화시키기 위해서입니다.

31은 해시 데이터 유형으로 int를 사용하는 Java HashMap에도 고유합니다.따라서 최대 용량은 2^32입니다.더 큰 페르마나 메르센 소수를 사용하는 것은 의미가 없다.

일반적으로 해시 버킷, 특히 낮은 엔트로피 키의 경우 데이터를 더 균등하게 분산하는 데 도움이 됩니다.

언급URL : https://stackoverflow.com/questions/3613102/why-use-a-prime-number-in-hashcode