C#를 GetHashCode 구현

Question

는

public override int GetHashCode() 
{ 
    return Word.GetHashCode(); 
} 

는 고유성에 관한

public override int GetHashCode() 
{ 
    return (int) Word.GetHashCode() * 7; 
} 

에 정말 동일합니까?

Word

유형이다 String

편집 : 내가 어느 프로그램, 옵션 1 또는 2에 구현하는 것이 좋습니다, 말을 잊으 셨나요?

Answer 1

Word.GetHashCode() 구현에서 충돌이 발생하면 (int) Word.GetHashCode() * 7 구현에서 충돌이 발생합니다. 동일한 숫자를 곱하면 동일한 결과가 산출되므로 분명합니다.

더 흥미로운 질문은 첫 번째 구현의 비 충돌 해시 코드가 두 번째 구현 내에서 충돌을 일으키는 경우입니다. int과 7의 범위는 서로 소숫자이기 때문에 대답은 "아니오"입니다. 따라서 곱셈은 오버플로를 제거한 후에 고유 한 매핑을 생성합니다.

const int Max = 1<<16; 
var count = new int[Max]; 
for (int i = 0 ; i != Max ; i++) { 
    count[(i * 7) & (Max-1)]++; 
} 
var notOne = 0; 
for (int i = 0 ; i != Max ; i++) { 
    if (count[i] != 1) { 
     notOne++; 
    } 
} 
Console.WriteLine("Count of duplicate mappings found: {0}", notOne); 

이 프로그램은, i, 해시 코드 값을 매핑 모듈 2 ¹⁶7 * i에, 각 있는지 확인합니다 :

당신은 어떻게되는지 2 바이트 해시 코드와 함께 작은 테스트를 실행할 수 있습니다 범위의 숫자는 정확히 한 번만 생성됩니다.

Demo.

당신이 짝수로 7를 교체 할 경우

Count of duplicate mappings found: 0 

는, 결과는 매우 다를 것입니다. 이제 원본 세트의 여러 해시 코드가 대상 세트의 단일 해시 코드에 매핑됩니다. 짝수로 곱하면 항상 최하위 비트가 0이된다는 것을 기억하면 직관적으로 이것을 이해할 수 있습니다. 따라서 짝수를 2로 나눌 수있는 횟수에 따라 일부 정보가 손실됩니다.

어느 쪽이 더 낫습니까?

차이는 없습니다.

참고 : 위의 내용은 정수 오버플로를 무시하고 있다고 가정합니다.

Answer 2

unchecked 컨텍스트에서 코드를 실행하지 않으므로 후자는 오버플로가 발생할 때마다 예외를 throw하므로 합리적으로 가능성이 높습니다 (해시 범위의 6/7이 발생하므로 일반적으로 균등하게 분산됩니다 해시 코드는 ~ 6/7의 예외가 발생할 가능성이 있습니다.