정수 곱하기, 오버플로 및 정보 손실시

나는 조슈아 블로흐의 의 Chapter 3을 통해 읽었습니다. 항목 8 : 37 선정 이유를 그는 다음 설명정수 곱하기, 오버플로 및 정보 손실시

result = 37 * result + c;

(강조 추가) :

재정의 할 때는 항상에 해당 해시 코드를 오버라이드 (override), 저자는 자신의 해시 함수에서 다음과 같은 결합 단계를 사용합니다
곱셈기 37이 홀수 소수이기 때문에 선택되었습니다. 이 짝수이고 곱셈이 오버플로 된 경우 정보가 손실됩니다. 은 2로 시프트하는 것과 동일합니다. 소수를 사용하면 얻을 수있는 이점은 덜 있지만 이지만이 목적으로 소수를 사용하는 것이 일반적입니다.

내 질문에 왜 조합 계수 (37)가 홀수일까요? 곱셈 오버 플로우가 요인이 홀수인지 짝수인지에 관계없이 정보가 손실되지 않을까요?

출처

2011-12-20 Bill the Lizard

기본 -2 표현에서 양수 값이 2로 반복 될 때 어떤 일이 일어나는 지 고려하십시오. 모든 세트 비트가 결국 끝에서 행진하여 0으로 남습니다.

짝수 배수를 사용하면 해시 코드의 다양성이 감소합니다.

반면에 홀수는 오버플로가 발생할 수 있지만 다양성은 손실되지 않습니다.

출처

2011-12-20 15:16:50

아, 우리가 걱정하는 오버 플로우에서 얻을 수있는 정보 손실이 조금도 아닙니다. 결과를 제로로 만들면 얻을 수있는 정보가 완전히 손실됩니다. –

@BilltheLizard : 사실, 서로 에뮬레이션하는 여러 속성의 데이터입니다. 위의 알고리즘'result = 2 * (2 * a + b) + c'를 사용하여 세 개의 프로퍼티 a, b, c를 가정하면, 아마도'a, b, c'의 많은 공통 집합에 중복이 있음을 알 수 있습니다. 홀수 프라임을 상수로 사용하면 같은 해시 값을 가진 집합을 가질 가능성이 훨씬 줄어 듭니다. –

결과를 완전히 초기화하기 전에 문제가 발생합니다. 8 비트 해시에 2의 승수를 한 번만 곱하면 256 개의 가능한 값으로 시작하고 128 개의 가능한 값으로 끝납니다. –

해시 코드의 목적은 (2)에 의한 여러는 최하위 비트 만 0으로 할 수있는 경우 이는 랜덤 부족 (특히 다음과 같은 하위 비트가 종종 사용된다) 입력

에 기초하여 임의의 비트를 가지고있다 . 홀수로 배수가되면 가장 낮은 비트가 홀수 또는 짝수 일 수 있습니다.

비슷한 질문은 당신이 모든 두 번째 숫자가 짝수

여기까지

public static void main(String... args) { 
    System.out.println(factorial(66)); 
} 

public static long factorial(int n) { 
    long product = 1; 
    for (; n > 1; n--) 
     product *= n; 
    return product; 
}

인쇄 할 것입니다, 4 등의 모든 등 여러

출처

2011-12-20 15:25:29

귀여운, 당신은 손으로 그것을 0으로 오버플로 보여줄 수 있습니다. 그래서 해시 함수로서 어떤 계승도 ... 내가 그것을 해내 지 못한 것은 아닙니다. – toto2

트릭의 일부는 왜 66이 0이 될 첫 번째 계승인지를 알아 내고 있습니다. 예를 들어 128 개가 아니고 64 개의 짝수 개 요소가 있습니다. –

해결책은 Number Theory와 승수와 모듈 번호의 Lowest common denominator입니다.

예가 도움이 될 수 있습니다. 말하자면 32 비트 대신 숫자를 나타내는 데 2 비트 밖에 없습니다. 그래서 네 개의 숫자 (클래스)가 있습니다. 0, 1, 2, 3

는 CPU에서 오버플 만 가능한 한 번호 (등급) 남았 2 작업 후에

Class - x2 - mod 4 - x2 - mod 4 

0  0  0  0  0 

1  2  2  4  0 

2  4  0  0  0 

3  6  2  4  0

모듈러 연산과 동일하다. 그래서 당신은 '잃어버린'정보를 가지고 있습니다.

Class - x3 - mod 4 - x3 - mod 4 ... 

0  0  0  0  0 

1  3  3  9  1 

2  6  2  6  2 

3  9  1  3  3

이것은 영원히 계속 될 수 있으며 여전히 4 개의 클래스가 있습니다. 그래서 당신은 정보를 잃지 않습니다.

열쇠는 당신의 muliplier와 귀하의 모듈로 클래스의 LCD가 1이라는 것입니다. 귀하의 모듈 숫자가 현재 2의 거듭 제곱이기 때문에 모든 홀수에도 해당됩니다. 그들은 소수 일 필요가 없습니다. 구체적으로 37입니다. 그러나 정보 손실 37 선택됩니다 다른 CRITERIAS 등 값

소수 다양성을 유지하기 위해 해싱에 사용되는 이유는 ...의

출처

2011-12-20 16:06:23 Stefan

비 수학 간단한 버전의 분포를 왜 하나의 기준입니다.

아마도 다양성은 Set 및 Map 구현 때문에 더 중요합니다. 이러한 구현은 객체 해시 번호의 마지막 비트를 사용하여 내부 항목 배열을 인덱싱합니다.

예를 들어, 크기가 8 인 항목에 대한 내부 테이블 (배열)이있는 HashMap에서 테이블 항목을 처리하기 위해 마지막 3 비트의 해시가 사용됩니다. Integer 객체가

 

    hash = 4 * number;

테이블 요소의 대부분이 비어있을 것이지만, 일부는 너무 많은 항목을 포함 할 경우

 

    static int indexFor(int h, int length) { 
     return h & (length-1); 
    }

은 사실이 아니지만. 이렇게하면 특정 항목을 검색하는 동안 추가 반복 및 비교 작업이 수행됩니다.

조슈아 블로흐 (Joshua Bloch)의 주된 관심사는 해시 정수를 가능한 한 많이 배포하여지도 및 세트에서 객체를 균등하게 분산시켜 컬렉션의 성능을 최적화하는 것입니다. 소수는 직관적으로 배포의 좋은 요소 인 것처럼 보입니다.

출처

2011-12-20 16:15:02 andrey

다양성을 보장하기 위해 소수는 꼭 필요한 것은 아닙니다. 필요한 것은 계수가 모듈러스와 상대적으로 소수라는 것입니다.

이진 산술에 대한 모듈러스는 항상 2의 거듭 제곱이므로 모든 홀수는 상대적으로 소수이며 충분할 것입니다. 오버플로가 아닌 다른 모듈을 사용한다면, 소수는 계속 다양성을 유지할 것입니다 (동일한 소수를 선택하지 않았다면 ...).

출처

2011-12-20 16:27:40

정수 곱하기, 오버플로 및 정보 손실시

답변

관련 문제