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

Question

我只是很好奇,因为我猜它会影响性能.它是否考虑完整的字符串？如果是,长字符串会很慢.如果它只考虑字符串的一部分,它将具有不良的性能(例如,如果它只考虑字符串的开头,如果HashSet主要包含具有相同的字符串,则它将具有不良性能.

Answer 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源代码中关闭整个销售功能.WIN32是在目标是32位版本的框架时定义的,mscorlib.dll的64位版本是单独构建的,并存储在GAC的不同子目录中.
• s_UseRandomizedStringHashing变量启用了散列算法的安全版本,旨在使程序员摆脱麻烦,做一些不明智的事情,比如使用GetHashCode()生成密码或加密等内容的哈希值.它由app.exe.config文件中的条目启用
• 该固定语句保持索引串便宜,避免了常规检查索引进行边界
• 第一个Assert确保字符串应该是零终止,这是允许在循环中进行优化所必需的
• 第二个Assert确保字符串与一个4的倍数对应,这是保持循环性能所必需的
• 循环手动展开,每个循环消耗4个字符用于32位版本.转换为int*是一种在int(32位)中存储2个字符(2 x 16位)的技巧.循环之后的额外语句处理长度不是4的倍数的字符串.注意零终止符可能包含也可能不包含在哈希中,如果长度是偶数则不会.它会查看字符串中的所有字符,回答您的问题
• 循环的64位版本以不同方式完成,由2手动展开.请注意,它在嵌入的零点上提前终止,因此不会查看所有字符.否则非常罕见.这很奇怪,我只能猜测这与可能非常大的字符串有关.但想不出一个实际的例子
• 最后的调试代码确保框架中的代码不会依赖于在运行之间可重现的哈希代码.
• 哈希算法非常标准.值1566083941是一个神奇的数字,是梅森捻线机中常见的素数.

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