C＃字符串的GetHashCode（）是如何實現的？

Question

我只是好奇，因爲我猜它會影響性能。它考慮完整的字符串嗎？如果是的話，那麼長串會慢。如果它只考慮字符串的一部分，它會有不好的表現（例如，如果它只考慮字符串的開始，如果一個HashSet包含大部分字符串，性能會很差

Answer 1

一定要獲得Reference Source source code當你有這樣的問題。還有很多更給它比你能看到什麼從一個反編譯器中選擇一個符合你的首選.NET目標的方法，這個方法改變了很多版本之間的差異，我將在這裏重現它的.NET 4.5版本，從Source.NET 4.5 \ 4.6.0.0 \網絡\ CLR \ SRC \ BCL \ SYSTEM \ String.cs \ 604718個\ 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源代碼中將功能關閉。當目標是32位版本的框架時定義了WIN32，mscorlib.dll的64位版本是單獨構建的，並存儲在GAC的不同子目錄中。
• s_UseRandomizedStringHashing變量啓用了哈希算法的安全版本，該算法旨在讓程序員擺脫麻煩，像使用GetHashCode（）爲諸如密碼或加密之類的事情生成哈希值那樣不明智。它是由an entry在app.exe.config文件
• 的固定聲明保持索引字符串便宜啓用，避免了常規索引
• 第一斷言確保字符串是零結尾做檢查的範圍理所應當，要求允許在循環優化
• 第二個斷言確保串對準那是4的倍數，因爲它應該是一個地址，以保持環路高性能
• 所需的循環是手動展開，對於32位版本，每個循環消耗4個字符。轉換爲int *是將2個字符（2 x 16位）存儲在int（32位）中的技巧。循環後的額外語句處理長度不是4的倍數的字符串。請注意，零終止符可能包含在哈希中，也可能不包含在哈希中，如果長度是偶數，它將不會被包含。它看起來在全部字符串中的字符，回答你的問題
• 循環的64位版本完成不同，手動展開2.注意它在一個嵌入的零早期終止，所以不看看所有的角色。否則非常罕見。這很奇怪，我只能猜測這與可能非常大的字符串有關。但不能想到一個實際的例子
• 最後的調試代碼確保框架中的任何代碼都不依賴於運行之間可重現的哈希代碼。
• 散列算法非常標準。值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; 
}