一尘不染

C#字符串的GetHashCode()如何实现?

c#

我只是好奇,因为我想它将对性能产生影响。是否考虑完整字符串?如果是,则在长字符串上会变慢。如果仅考虑字符串的一部分,则会导致性能下降(例如,如果仅考虑字符串的开头,则当HashSet主要包含相同的字符串时,它将导致性能下降。


阅读 840

收藏
2020-05-19

共1个答案

一尘不染

遇到类似问题时,请确保获取参考源源代码。除了从反编译器中可以看到的内容之外,还有很多其他功能。选择与您的首选.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源代码中关闭全部功能。当目标是框架的32位版本时定义WIN32,mscorlib.dll的64位版本是单独构建的,并存储在GAC的其他子目录中。

  • s_UseRandomizedStringHashing变量启用哈希算法的安全版本,该版本旨在使程序员摆脱麻烦,因为这样做不明智,例如使用GetHashCode()生成密码或加密之类的哈希。通过app.exe.config文件中的条目启用它
  • 固定 语句保持索引串便宜,避免了常规检查索引进行边界
  • 第一个Assert确保字符串应以零结尾,以允许在循环中进行优化
  • 第二个断言确保将字符串对齐为应为4的倍数的地址,以保持循环性能
  • 手动展开该循环,对于32位版本,每个循环消耗4个字符。强制转换为int *是在int(32位)中存储2个字符(2 x 16位)的一种技巧。循环后的多余语句处理的字符串长度不是4的倍数。请注意,散列中可以包含零终止符,也可以不包含零终止符,长度不等于偶数。它查看字符串中的 所有 字符,并回答您的问题
  • 循环的64位版本以不同的方式完成,由2手动展开。请注意,它以嵌入的零提前终止,因此不会查看所有字符。否则非常不常见。这很奇怪,我只能猜测这与可能很大的字符串有关。但是想不出一个实际的例子
  • 最后的调试代码可确保框架中的任何代码都不依赖哈希代码在运行之间可重现。
  • 哈希算法是相当标准的。值1566083941是一个幻数,是梅森捻线机中常见的素数。
2020-05-19