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

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

---

왜 소수가 클래스의 hashCode()메소드에 사용되는지 궁금합니다 . 예를 들어, Eclipse를 사용하여 내 hashCode()메소드 를 생성 할 때 항상 소수가 31사용됩니다.

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

참고 문헌 :

다음은 Hashcode에 대한 좋은 입문서와 내가 찾은 해싱의 작동 방식에 대한 기사입니다 (C #이지만 개념을 양도 할 수 있음). Eric Lippert의 GetHashCode () 지침

---

곱할 수와 삽입하는 버킷 수에 직교 소수 인수를 사용하기를 원하기 때문입니다.

삽입 할 버킷이 8 개 있다고 가정합니다. 곱하기 위해 사용하는 숫자가 8의 배수 인 경우 삽입 된 버킷은 가장 중요하지 않은 항목 (곱하지 않은 항목)에 의해서만 결정됩니다. 유사한 항목이 충돌합니다. 해시 함수에는 좋지 않습니다.

31은 버킷 수를 나눌 수 없을 정도로 큰 소수입니다 (실제로 현대 Java HashMap 구현은 버킷 수를 2의 거듭 제곱으로 유지합니다).

---

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

메모리 위치를 다룰 때 종종 그렇습니다. 예를 들어, 모든 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

프라임 모듈러스 대 비 프라임 모듈러스를 사용할 때 거의 완벽한 분포를 확인하십시오.

그러나, 위의 예가 주로 고안되었지만, 일반적 으로 입력 패턴을 처리 할 때 소수 모듈러스를 사용하면 최상의 분포를 얻을 수 있습니다.

---

가치있는 것을 위해, Effective Java 2nd Edition 은 수학 문제를 해결하고 31을 선택하는 이유는 다음과 같습니다.

• 그것은 소수이며, 소수를 사용하는 것이 "전통적"이기 때문에
• 또한 2의 거듭 제곱보다 1이 적으므로 비트 단위 최적화가 가능합니다.

항목 9hashCodeequals 의 전체 인용문은 다음과 같습니다 . 재정의 하면 항상 재정의하십시오 .

값 31은 홀수 소수이므로 선택되었습니다. 짝수이고 곱셈이 오버플로 된 경우 2의 곱셈은 이동과 동일하므로 정보가 손실됩니다. 소수를 사용하는 이점은 명확하지 않지만 전통적입니다.

31의 좋은 속성은 곱셈 을 더 나은 성능을 위해 교대 ( §15.19 )와 빼기 로 대체 할 수 있다는 것입니다 .

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

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

---

이 항목의 레시피는 상당히 좋은 해시 함수를 생성하지만 최신 해시 함수를 생성하지는 않으며 Java 플랫폼 라이브러리가 릴리스 1.6 현재와 같은 해시 함수를 제공하지도 않습니다. 이러한 해시 함수를 작성하는 것은 수학자 및 이론적 컴퓨터 과학자에게 가장 적합한 연구 주제입니다.

아마도이 플랫폼의 이후 릴리스는 일반 프로그래머가 그러한 해시 함수를 구성 할 수 있도록 클래스 및 유틸리티 메소드에 최신 해시 함수를 제공 할 것입니다. 그 동안이 항목에서 설명하는 기술은 대부분의 응용 프로그램에 적합해야합니다.

간단히 말해서, 제수가 많은 승수를 사용하면 더 많은 해시 충돌 이 발생한다고 말할 수 있습니다 . 효과적인 해싱을 위해 충돌 횟수를 최소화하고자하므로 제수가 적은 곱셈기를 사용하려고합니다. 정의에 의한 소수는 정확히 두 개의 구별되는 양의 제수를 갖습니다.

관련 질문

• 한 필드의 Java hashCode- 레시피와 Apache Commons Lang 빌더 사용 예제
• 객체의 해시 코드를 모든 클래스 변수 해시 코드의 합, 곱셈 등으로 정의하는 것이 올바르지 않습니까?
• 비트 시프 팅에 대한 절대 초보자 안내서?

---

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

---

여기 소스에 조금 더 가까운 인용 이 있습니다.

그것은 다음과 같이 요약됩니다 :

• 31은 소수이며 충돌을 줄입니다.
• 31은
• 합리적인 속도의 균형

---

먼저 해시 값 modulo 2 ^ 32 (a의 크기 int)를 계산하므로 2 ^ 32에 상대적으로 소수를 원합니다 (상대적으로는 제수가 없다는 것을 의미합니다). 홀수는 그렇게 할 것입니다.

Then for a given hash table the index is usually computed from the hash value modulo the size of the hash table, so you want something that is relatively prime to the size of the hash table. Often the sizes of hash tables are chosen as prime numbers for that reason. In the case of Java the Sun implementation makes sure that the size is always a power of two, so an odd number would suffice here, too. There is also some additional massaging of the hash keys to limit collisions further.

The bad effect if the hash table and the multiplier had a common factor n could be that in certain circumstances only 1/n entries in the hash table would be used.

---

It generally helps achieve a more even spread of your data among the hash buckets, especially for low-entropy keys.

---

31 is also specific to Java HashMap which uses a int as hash data type. Thus the max capacity of 2^32. There is no point in using larger Fermat or Mersenne primes.

---

The reason why prime numbers are used is to minimize collisions when the data exhibits some particular patterns.

First things first: If the data is random then there’s no need for a prime number, you can do a mod operation against any number and you will have the same number of collisions for each possible value of the modulus.

But when data is not random then strange things happen. For example consider numeric data that is always a multiple of 10.

If we use mod 4 we find:

10 mod 4 = 2

20 mod 4 = 0

30 mod 4 = 2

40 mod 4 = 0

50 mod 4 = 2

So from the 3 possible values of the modulus (0,1,2,3) only 0 and 2 will have collisions, that is bad.

If we use a prime number like 7:

10 mod 7 = 3

20 mod 7 = 6

30 mod 7 = 2

40 mod 7 = 4

50 mod 7 = 1

etc

We also note that 5 is not a good choice but 5 is prime the reason is that all our keys are a multiple of 5. This means we have to choose a prime number that doesn’t divide our keys, choosing a large prime number is usually enough.

So erring on the side of being repetitive the reason prime numbers are used is to neutralize the effect of patterns in the keys in the distribution of collisions of a hash function.

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