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

显而易见的潜在答案是:因为这会消耗内存。

这里有一个成本/收益分析:

成本 :每个字符串4个字节(以及每次调用GetHashCode时的快速测试)。还要使string对象可变,这显然意味着您需要小心 实施-除非你 预先计算哈希代码,这是计算一次的开销 字符串,不管你是否把它散列过。

利益 :避免重新计算哈希 对于多次散列的字符串值

我建议,在很多情况下,有很多很多字符串对象,很少有对象被多次散列,这导致了净成本。在某些情况下,显然情况并非如此。

我不认为我能很好地判断哪一个更经常出现。。。我希望微软已经安装了各种真正的应用程序(我也希望Sun对Java也这么做 做 缓存哈希…)

是

首先,不知道缓存这个结果是否真的会改善 Dictionary<string, ...>

如果您遵循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<,> etc不能使用内部实现,不缓存这个结果可能没有太大影响,因为坦率地说,这个方法在现实世界中实际被调用的频率有多高:因为大多数时候字符串的hashcode很可能是通过其他机制计算出来的。

编辑

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

附加编辑(!)

Dan指出,字符串在netsphere中是不可变的,因此字符串应该可以基于此自由缓存自己的hashcode。这里的问题是.Net框架还提供了 更改假定不可变字符串的合法方法 这不涉及特权反思或其他任何事情。这是字符串的一个基本问题,它是指向无法控制的缓冲区的指针。不用担心,在C++世界里,C++中,如何引导和修改内存缓冲区是常见的地方。只是因为你 不应该 这样做并不意味着框架应该期望您不这样做。

.Net恰好提供了这个功能,因此,如果这是.Net团队针对Tim建议的那种二进制恶作剧而做出的设计决定,那么他们考虑到这一点是非常明智的。他们是否做到了,或者是出于侥幸,完全是另一回事了!:)

例如,如果你这么想做。。。

String example = "Hello World";

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

…不会的 example 仍然表示相同的字符串对象,但现在使用的值将为 GetHashCode() ? 我在这里可能不太靠谱,但既然你可以很容易(如果不是毫无意义的话)做到这一点,那也会引起一些问题。

另一个可能的原因是,内部字符串(特别是那些由编译器作为共享只读数据添加的字符串)可以与任何其他字符串具有完全相同的格式。这些字符串被加载到只读内存的事实意味着这些数据页可以很容易地在进程间共享,但是也不可能让它们缓存哈希代码。

是的,它会占用内存,但更重要的是,即使您不使用此功能,它也会占用内存。

也许优化hashcode会有好处 string 框架内实施。

不管怎样,实现自己的目标应该很简单:

public sealed class InternedString : IEquatable<InternedString>
{
    public InternedString(string s) => String = string.Intern(s);

    public string String { get; }

    public override bool Equals(object obj) => String.Equals(obj);

    public bool Equals(InternedString other) => String.Equals(other?.String);

    public override int GetHashCode() => RuntimeHelpers.GetHashCode(String);

    public static bool operator ==(InternedString l, InternedString r) =>
        l?.String == r?.String;

    public static bool operator !=(InternedString l, InternedString r) => !(l == r);
}

被拘留了,所以我们可以依靠 一串 strings 里面 InternedString 永远不变。这种方法优化了两者 GetHashCode Equals 打电话,让这个班成为 Dictionary 钥匙。

缺点是实习费用。在任何地方使用它都是一种过度杀伤力。典型的使用场景是 字典 有几个,但很长的字符串键。

升级版本:

顺便说一句,我有 packaged it check it out .

• HashCode有一个int字段,再加上一个bool字段作为是否已经计算HashCode的标志,然后只在第一次请求时计算HashCode(延迟求值),
• HashCode有一个int字段,并且 构造字符串时计算哈希代码。

现在考虑一下 Dictionary<TKey,TValue> . 字典使用的哈希代码取决于使用哪个比较器。默认比较器将使用对象的普通GetHashCode()方法。但是您可以创建一个使用不区分大小写比较器的字典,字典使用的HashCode将由该比较器生成,这可能会生成一个与之完全不同的HashCode String.GetHashCode()

如果是 词典<TKey,TValue>

• 使用构造时提供的相等比较器的GetHashCode()方法计算键的哈希代码,如果未指定任何比较器,则使用默认比较器。
• 去掉HashCode中的符号位
• 存储新条目,该条目由上面修改的HashCode、键、值和映射到同一bucket的条目列表中下一个条目的索引组成。

当字典进行键查找时,它计算要搜索的键的修改的(即正的)HashCode,获取HashCode映射到的bucket,然后查看该bucket中的条目列表。要检查条目是否匹配,它首先检查修改后的哈希码是否匹配(如果键相等,哈希码也必须相等),如果相等,则检查两个键是否相等。在字符串的情况下,这个算法实现了两件事;首先,它通过使用一个简单的整数比较来避免许多字符串比较,首先看是否值得进行字符串比较,其次,它缓存字典中每个键的hashcode。 当键/值对被添加到字典中时,字典中每个键的HashCode只计算一次 .

(如果您想知道为什么Dictionary会从HashCode中删除符号位,那是因为Dictionary在HashCode字段中将-1用作当前为空的条目槽的标记标志值。)