왜 소수가 클래스의 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을 선택했다고 들었습니다.
답변
답변
먼저 해시 값 modulo 2 ^ 32 (a의 크기 int)를 계산하므로 2 ^ 32에 상대적으로 소수를 원합니다 (상대적으로는 제수가 없습니다). 홀수는 그렇게 할 것입니다.
그런 다음 주어진 해시 테이블의 색인은 일반적으로 해시 테이블의 크기를 해시 값 모듈로 계산하므로 해시 테이블의 크기에 비해 상대적으로 소수의 것을 원합니다. 이러한 이유로 해시 테이블의 크기는 종종 소수로 선택됩니다. Java의 경우 Sun 구현은 크기가 항상 2의 거듭 제곱인지 확인하므로 홀수로도 충분합니다. 충돌을 더욱 제한하기 위해 해시 키의 일부 추가 마사지가 있습니다.
해시 테이블과 승수가 공통 요소를 갖는 경우 나쁜 영향 n은 특정 상황에서 해시 테이블의 1 / n 항목 만 사용한다는 것입니다.
답변
소수가 사용되는 이유는 데이터가 특정 패턴을 나타낼 때 충돌을 최소화하기 위해서입니다.
가장 먼저해야 할 일 : 데이터가 무작위 인 경우 소수가 필요하지 않은 경우 임의의 수에 대해 mod 연산을 수행 할 수 있으며 모듈의 가능한 각 값에 대해 동일한 충돌 횟수가 발생합니다.
그러나 데이터가 무작위가 아닌 경우 이상한 일이 발생합니다. 예를 들어 항상 10의 배수 인 숫자 데이터를 고려하십시오.
mod 4를 사용하면 다음을 찾을 수 있습니다.
10 모드 4 = 2
20 모드 4 = 0
30 모드 4 = 2
40 모드 4 = 0
50 모드 4 = 2
따라서 모듈러스 (0,1,2,3)의 3 가지 가능한 값에서 0과 2 만 충돌이 발생합니다.
7과 같은 소수를 사용하면
10 모드 7 = 3
20 모드 7 = 6
30 모드 7 = 2
40 모드 7 = 4
50 모드 7 = 1
기타
또한 5는 좋은 선택이 아니라 5는 소수입니다. 이유는 모든 키가 5의 배수이기 때문입니다. 즉, 키를 나누지 않는 소수를 선택해야합니다. 보통 충분합니다.
따라서 소수가 사용되는 이유는 반복적이라는 측면에서 잘못된 것은 해시 함수의 충돌 분포에서 키의 패턴 효과를 중화하는 것입니다.
