如何实现C#string的GetHashCode()?

我只是好奇,因为我猜它会影响性能。 它考虑完整的string吗? 如果是的话,长串会慢。 如果只考虑string的一部分,那么性能会很差(例如,如果只考虑string的开始,如果HashSet包含大部分相同的string,则性能会很差。

当你有这样的问题时,一定要获得参考源代码 。 还有更多的东西比你可以从反编译器看到。 select一个匹配你首选的.NET目标的方法,版本之间的方法已经改变了很多。 我将在这里重现它的.NET 4.5版本,从Source.NET 4.5 \ 4.6.0.0 \ net \ 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源代码中将functionclosures。 当目标是32位版本的框架时定义了WIN32,mscorlib.dll的64位版本是单独构build的,并存储在GAC的不同子目录中。
  • s_UseRandomizedStringHashingvariables启用了哈希algorithm的一个安全版本,该algorithm旨在让程序员避免麻烦,像使用GetHashCode()为诸如密码或encryption之类的东西生成哈希。 它由app.exe.config文件中的条目启用
  • 固定语句不断索引string便宜,避免了常规索引器所做的边界检查
  • 第一个Assert确保该string是零终止的,因为它是允许在循环中进行优化的必要条件
  • 第二个Assert确保该stringalignment到一个应该是4的倍数的地址,以保持循环的高性能
  • 循环被手动展开,每个循环的32位版本消耗4个字符。 转换为int *是将2个字符(2 x 16位)存储在int(32位)中的技巧。 循环后面的额外语句处理长度不是4的倍数的string。请注意,零终止符可能包含或不包含在散列中,如果长度是偶数,则不会包含它。 它看着string中的所有字符,回答你的问题
  • 循环的64位版本是以不同的方式完成的,用2进行手动展开。注意,它在embedded的零处提前终止,所以不会查看所有的字符。 否则非常罕见。 这很奇怪,我只能猜测这跟string可能非常大有关。 但是想不出一个实际的例子
  • 最后的debugging代码确保框架中的任何代码都不会依赖运行之间可重现的散列码。
  • 散列algorithm非常标准。 价值1566083941是一个魔法数字,在梅森扭转者中是一个常见的素数。

检查源代码(由ILSpy提供 ),我们可以看到它遍历了string的长度。

 // 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; }