为什么System.String对象不能缓存其哈希代码？

Question

浏览string.GetHashCode使用Reflector的源代码会显示以下内容(对于mscorlib.dll版本4.0):

public override unsafe int GetHashCode()
{
    fixed (char* str = ((char*) this))
    {
        char* chPtr = str;
        int num = 0x15051505;
        int num2 = num;
        int* numPtr = (int*) chPtr;
        for (int i = this.Length; i > 0; i -= 4)
        {
            num = (((num << 5) + num) + (num >> 0x1b)) ^ numPtr[0];
            if (i <= 2)
            {
                break;
            }
            num2 = (((num2 << 5) + num2) + (num2 >> 0x1b)) ^ numPtr[1];
            numPtr += 2;
        }
        return (num + (num2 * 0x5d588b65));
    }
}

现在,我认识到,实施GetHashCode不指定,是实现相关,所以这个问题"是GetHashCode在X或Y的形式来实现？" 真的不负责任.我只是对一些事情感到好奇:

1. 如果反射器具有正确拆解的DLL,这是实施GetHashCode(在我的环境),我在解释这个代码,指出一个正确的string目标,在此基础上具体的实现,将不缓存的哈希码？
2. 假设答案是肯定的,为什么会这样？在我看来,内存成本将是最小的(一个32位整数,池中的一个下降与字符串本身的大小相比),而节省将是显着的,尤其是在例如使用字符串的情况下作为基于散列表的集合中的键,如Dictionary<string, [...]>.并且因为string类是不可变的,所以返回的值不会像GetHashCode改变那样.

我能错过什么？

---

更新:回应安德拉斯佐尔坦的结束语:

蒂姆的答案中也提到了这一点(+1那里).如果他是对的,而且我认为他是,那么就不能保证字符串在构造之后实际上是不可变的,因此缓存结果将是错误的.

哇,哇!这是一个有趣的观点(是的,这是非常正确的),但我真的怀疑这是在实施中考虑到的GetHashCode.声明"因此缓存结果将是错误的"对我来说意味着框架对字符串的态度是"嗯,它们应该是不可变的,但实际上如果开发人员想偷偷摸摸他们是可变的,所以我们会对待他们就是这样." 这绝对不是框架查看字符串的方式.它完全依赖于它们在很多方面的不变性(字符串文字的实习,将所有零长度字符串赋值给string.Empty等等,基本上,如果你改变一个字符串,你就会编写其行为完全未定义且不可预测的代码.

我想我的观点是,对于这个实现的作者来说,担心"如果在调用之间修改了这个字符串实例,即使公开公开的类是不可变的,该怎么办？" 对于那些计划休闲户外烧烤的人来说,想想他/她自己,"如果有人带来原子弹到聚会怎么办？" 看,如果有人带来原子弹,派对结束了.

Answer 1

显而易见的潜在答案:因为这将耗费内存.

这里有成本/收益分析:

成本:每个字符串4个字节(以及每次调用GetHashCode的快速测试).还要使字符串对象变得可变,这显然意味着你需要小心实现 - 除非你总是预先计算哈希码,这是为每个字符串计算一次的成本,无论你是否曾经哈哈吧.

好处:避免重新计算哈希值,以便对字符串值进行多次哈希处理

我建议在很多情况下,有很多很多的字符串对象,而且很少有它们被多次散列 - 导致净成本.在某些情况下,显然情况并非如此.

我不认为我能够更好地判断哪些更频繁出现......我希望MS已经为各种真实的应用程序提供了工具.(我也希望Sun为Java做同样的事情,它会缓存哈希......)

编辑:我刚刚和Eric Lippert谈过这个问题(NDC很棒:)基本上它是关于额外的内存命中率和有限的好处.

Answer 2

首先 - 不知道缓存此结果是否会实际改善Dictionary<string, ...>等,因为它们不一定使用String.GetHashCode,因为它使用IComparer来获取字符串的哈希码.

如果您遵循StringComparer类的可能调用链,它最终会进入System.Globalization.CompareInfo类,该类最终以此方法终止:

[SecurityCritical, SuppressUnmanagedCodeSecurity, DllImport("QCall",
   CharSet=CharSet.Unicode)]
private static extern int InternalGetGlobalizedHashCode(IntPtr handle, string
   localeName, string source, int length, int dwFlags);

不知道该库(看起来是本机方法)是否不使用某种形式的内部缓存,这种内部缓存基于我们在.Net运行时内无法立即获得的底层.Net对象数据结构.

但是,需要注意的重要一点是,根据您选择解释字符的方式,一个字符串可以有许多不同的哈希码.当然,这种实施具有文化特异性 - 这就是为什么它不适合这些比较者.

因此,虽然额外的内存存储可能是一个因素,但我实际上认为这是因为存储哈希码以及字符串的实例误导了调用者,实际上.Net内部开发团队(!),认为该字符串只有一个哈希码,实际上它完全取决于你将如何解释它 - 作为一系列字节(我们大多数人没有),或者作为一系列可打印字符.

从性能的角度来看,那么,如果我们也接受Dictionary<,>等等使用的这些比较器不能使用内部实现,不缓存这个结果可能没有太大的影响,因为,坦率地说,这个方法多久会有一次实际上在现实世界中被调用:因为大多数时候字符串的哈希码很可能是通过其他机制来计算的.

编辑

蒂姆的答案中也提到了这一点(+1那里).如果他是对的,而且我认为他是,那么就不能保证字符串在构造之后实际上是不可变的,因此缓存结果将是错误的.

另外编辑(!)

Dan指出字符串在Net球体中是不可变的,因此该字符串应该可以自由地基于此来缓存它自己的哈希码.这里的问题是.Net框架还提供了一种合法的方法来更改不涉及特权反射或其他任何东西的所谓不可变字符串.这是字符串的基本问题,它是指向无法控制的缓冲区的指针.不用担心在C#世界中,在C++中,向量和修改内存缓冲区是常见的.仅仅因为你理想情况下不应该这样做并不意味着框架应该指望你不要这样做.

.Net恰好提供了这种功能,因此,如果这是.Net团队针对蒂姆提出的二元犯罪行为做出的设计决定,那么他们考虑到这一点是非常明智的.他们是否这样做,或者是否是侥幸,完全是另一回事!:)

Answer 3

我可能在这里得出了一个错误的结论,但是当字符串在.NET String对象的上下文中不可变时,它仍然可以更改值吗？

例如,如果你倾向于这样做......

String example = "Hello World";

unsafe
{
    fixed (char* strPointer = myString) {
        strPointer[1] = 'a';
    }
} 

...仍然不会example代表相同的String对象,但现在有一个值可以计算不同的值GetHashCode()？我可能在这里偏离基地,但既然你可以很容易地(如果不是毫无意义的话)这样做,那也会引起一些问题.