C# 문자열의 GetHashCode()는 어떻게 구현됩니까?

Question

성능에 영향을 미칠 것 같아서 궁금합니다. 전체 문자열을 고려합니까? 그렇다면 긴 문자열에서 느려질 것입니다. 문자열의 일부만을 고려하면 성능이 떨어집니다 (예 : 문자열 시작 부분 만 고려할 경우 HashSet에 대부분 문자열이 포함되어 있으면 성능이 저하됩니다)

Answer 1

것은이 같은 질문이있을 때 Reference Source source code를 취득해야합니다. 그것에 더 많은 당신이 볼 수있는 것보다 있습니다 디 컴파일러에서. 원하는 .NET 대상과 일치하는 것을 선택하십시오.이 메서드는 버전간에 큰 차이가 있습니다. 여기에서 가져온 .NET 4.5 버전을 Source.NET 4.5 \ 4.6.0.0 \ NET \ CLR \ SRC \ BCL \ 시스템 \ String.cs \ 604,718 \ String.cs

 public override int GetHashCode() { 

#if FEATURE_RANDOMIZED_STRING_HASHING 
      if(HashHelpers.s_UseRandomizedStringHashing) 
      { 
       return InternalMarvin32HashString(this, this.Length, 0); 
      } 
#endif // FEATURE_RANDOMIZED_STRING_HASHING 

      unsafe { 
       fixed (char *src = this) { 
        Contract.Assert(src[this.Length] == '\0', "src[this.Length] == '\\0'"); 
        Contract.Assert(((int)src)%4 == 0, "Managed string should start at 4 bytes boundary"); 

#if WIN32 
        int hash1 = (5381<<16) + 5381; 
#else 
        int hash1 = 5381; 
#endif 
        int hash2 = hash1; 

#if WIN32 
        // 32 bit machines. 
        int* pint = (int *)src; 
        int len = this.Length; 
        while (len > 2) 
        { 
         hash1 = ((hash1 << 5) + hash1 + (hash1 >> 27))^pint[0]; 
         hash2 = ((hash2 << 5) + hash2 + (hash2 >> 27))^pint[1]; 
         pint += 2; 
         len -= 4; 
        } 

        if (len > 0) 
        { 
         hash1 = ((hash1 << 5) + hash1 + (hash1 >> 27))^pint[0]; 
        } 
#else 
        int  c; 
        char *s = src; 
        while ((c = s[0]) != 0) { 
         hash1 = ((hash1 << 5) + hash1)^c; 
         c = s[1]; 
         if (c == 0) 
          break; 
         hash2 = ((hash2 << 5) + hash2)^c; 
         s += 2; 
        } 
#endif 
#if DEBUG 
        // We want to ensure we can change our hash function daily. 
        // This is perfectly fine as long as you don't persist the 
        // value from GetHashCode to disk or count on String A 
        // hashing before string B. Those are bugs in your code. 
        hash1 ^= ThisAssembly.DailyBuildNumber; 
#endif 
        return hash1 + (hash2 * 1566083941); 
       } 
      } 
     } 

이 나는 ​​코드에 주석을 달 수 있습니다, 당신이 예상했던 것보다 아마도 더 비트 :

• #if 조건부 컴파일 명령은이 코드를 다른 .NET 대상에 맞게 조정합니다. FEATURE_XX 식별자는 다른 곳에서 정의되며 .NET 소스 코드 전체에서 기능을 완전히 판매하지 않습니다. WIN32는 대상이 프레임 워크의 32 비트 버전이고 mscorlib.dll의 64 비트 버전이 별도로 만들어져 GAC의 다른 하위 디렉터리에 저장 될 때 정의됩니다.
• s_UseRandomizedStringHashing 변수는 암호 나 암호화 같은 것에 대해 해시를 생성하기 위해 GetHashCode()를 사용하는 것과 같은 현혹적인 일을 프로그래머가 막지 않도록 설계된 해시 알고리즘의 보안 버전을 사용 가능하게합니다. 그것이 app.exe.config의 파일 고정 문이 싼 문자열 색인 유지
• 에 an entry으로 활성화되어,
• 첫 번째 어설 문자열이 제로 종료되는 것을 보장 정규 인덱서에 의해 수행 검사의 경계를 피할 수 루프에서 최적화를 허용해야합니다.
• 두 번째 Assert는 문자열이 루프의 성능을 유지하는 데 필요한 4의 배수가되는 주소로 정렬되도록합니다.
• 루프는 다음과 같습니다. 32 비트 버전의 경우 루프 당 4자를 소비하면서 손으로 풀립니다. int * 로의 캐스트는 int (32 비트)에 2 문자 (2 x 16 비트)를 저장하는 트릭입니다. 루프 이후의 추가 명령문은 길이가 4의 배수가 아닌 문자열을 처리합니다. 길이가 짝수 인 경우 제로 터미네이터가 해시에 포함되거나 포함되지 않을 수 있습니다. 모두 보이는 질문에 대답하는 문자열의 문자
• 64 비트 버전의 루프가 다르게 처리되고 2로 손으로 풀립니다. 삽입 된 0에서 일찍 끝나기 때문에주의하십시오. 모든 캐릭터를보세요. 그렇지 않으면 매우 드물다. 그것은 꽤 이상한 일이며, 나는 이것이 문자열이 잠재적으로 매우 큰 것과 관련이 있다고 추측 할 수 있습니다. 그러나 실용적인 예를 생각할 수 없다.
• 결국 디버그 코드는 실행 중에 재사용 가능한 해시 코드에 대한 의존성을 프레임 워크의 코드가 취하지 않도록 보장한다.
• 해시 알고리즘은 꽤 표준 적입니다. 값 1566083941은 마법 번호이며, Mersenne twister에서 흔히 사용되는 소수입니다.

Answer 2

소스 코드 검사 ILSpy의 의례), 우리는 문자열의 길이를 반복 않는 것을 볼 수 있습니다.

// string 
[ReliabilityContract(Consistency.WillNotCorruptState, Cer.MayFail), SecuritySafeCritical] 
public unsafe override int GetHashCode() 
{ 
    IntPtr arg_0F_0; 
    IntPtr expr_06 = arg_0F_0 = this; 
    if (expr_06 != 0) 
    { 
     arg_0F_0 = (IntPtr)((int)expr_06 + RuntimeHelpers.OffsetToStringData); 
    } 
    char* ptr = arg_0F_0; 
    int num = 352654597; 
    int num2 = num; 
    int* ptr2 = (int*)ptr; 
    for (int i = this.Length; i > 0; i -= 4) 
    { 
     num = ((num << 5) + num + (num >> 27)^*ptr2); 
     if (i <= 2) 
     { 
      break; 
     } 
     num2 = ((num2 << 5) + num2 + (num2 >> 27)^ptr2[(IntPtr)4/4]); 
     ptr2 += (IntPtr)8/4; 
    } 
    return num + num2 * 1566083941; 
}