42

浏览一下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. 如果 Reflector 正确地反汇编了 DLL 并且这是（在我的环境中）的实现GetHashCode，我是否正确地解释了这段代码以指示string基于这个特定实现的对象不会缓存其哈希码？
  2. 假设答案是肯定的，为什么会这样？在我看来，内存成本将是最小的（多一个 32 位整数，与字符串本身的大小相比减少了），而节省的成本将是显着的，尤其是在使用字符串的情况下作为基于哈希表的集合中的键，例如Dictionary<string, [...]>. 而且由于string该类是不可变的，因此返回的值GetHashCode甚至不会改变。

我会错过什么？

更新：回应安德拉斯佐尔坦的闭幕词：

蒂姆的回答（+1 那里）也很重要。如果他是对的，我认为他是对的，那么就不能保证字符串在构造后实际上是不可变的，因此缓存结果是错误的。

哇哇哇！_ 这是一个有趣的观点（是的，这是非常正确的），但我真的怀疑在GetHashCode. “因此缓存结果是错误的”这句话对我来说意味着框架对字符串的态度是“好吧，它们应该是不可变的，但如果开发人员想要偷偷摸摸，它们是可变的，所以我们会处理他们就是这样。” 这绝对不是框架查看字符串的方式。它在很多方面完全依赖于它们的不变性（字符串文字的实习，将所有零长度字符串分配给string.Empty等），基本上，如果你改变一个字符串，你正在编写其行为完全未定义和不可预测的代码。

我想我的意思是让这个实现的作者担心，“如果这个字符串实例在调用之间被修改了怎么办，即使它公开暴露的类是不可变的？” 就像一个计划休闲户外烧烤的人会想他/她自己，“如果有人把原子弹带到聚会上怎么办？” 听着，如果有人带了原子弹，派对就结束了。

4

6 回答 6

28

明显的潜在答案：因为那会消耗内存。

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

成本：每个字符串 4 个字节（以及对每次调用 GetHashCode 的快速测试）。还要使字符串对象可变，这显然意味着您需要小心实现 - 除非您总是预先计算哈希码，这是为每个字符串计算一次的成本，无论您是否曾经哈希它。

好处：避免为多次散列的字符串值重新计算散列值

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

我认为我无法判断哪个出现频率更高……我希望 MS 已经检测了各种真实的应用程序。（我也希望 Sun 对 Java 做同样的事情，它确实缓存了哈希......）

编辑：我刚刚和 Eric Lippert 谈过这个问题（NDC 很棒:)，基本上是关于额外的内存命中与有限的好处。

于 2010-06-16T13:51:22.413 回答
13

首先 - 不知道缓存这个结果是否真的会改善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<,>etc 使用的这些比较器不能使用内部实现，那么不缓存此结果可能不会产生太大影响，因为坦率地说，这种方法多久会实际上在现实世界中被调用：因为大多数时候字符串的哈希码很可能是通过其他机制计算的。

编辑

蒂姆的回答（+1 那里）也很重要。如果他是对的，我认为他是对的，那么就不能保证字符串在构造后实际上是不可变的，因此缓存结果是错误的。

附加编辑（！）

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

.Net 恰好提供了这个功能，因此，如果这是 .Net 团队为响应 Tim 建议的那种二进制攻击而做出的设计决定，那么考虑到这一点是非常明智的。他们是否这样做，或者是否是侥幸，完全是另一回事！:)

于 2010-06-16T14:07:18.173 回答
12

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

例如，如果您愿意这样做...

String example = "Hello World";

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

...不会example仍然代表相同的 String 对象，但现在有一个值可以计算不同的值GetHashCode()? 我可能在这里偏离了基地，但是由于您可以轻松（如果不是毫无意义地）这样做，那也会导致一些问题。

于 2010-06-16T14:21:23.100 回答
1

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

但正如其他人所提到的，不缓存该值的主要原因是额外的内存使用可能远远超过哈希码缓存的潜在节省。GetHashCode 的执行时间在字符串长度上为 O(N)，因此重复散列的最坏情况是有界的。

于 2010-06-16T15:25:26.917 回答
1

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

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

这里的想法是确保每个被包装string的都是实习的，所以我们可以依赖string相同strings内部的引用InternedString始终相同。这种方法优化了GetHashCode和Equals调用，使这个类成为Dictionary键的完美候选者。

缺点是实习费用。到处使用它是一种矫枉过正。典型的使用场景是Dictionary有几个但很长的字符串键。

升级版：

顺便说一句，我已经打包了它，并添加了一个基准，检查一下。

于 2019-10-25T17:25:02.923 回答
0

任何 int 值都是有效的 HashCode。这意味着没有像 -1 或 0 这样的默认 int 值可以用来指示我们尚未计算 HashCode。因此，如果一个字符串要缓存其 HashCode，则需要执行以下操作之一：

  • 有一个 HashCode 的 int 字段，加上一个 bool 字段作为 HashCode 是否已计算的标志，然后仅在第一次请求时计算 HashCode（延迟评估），或
  • HashCode 有一个 int 字段，并在构造字符串时始终计算 HashCode。

这两种选择都有一个缺点。第一个需要更多额外的内存，第二个具有计算可能永远不需要的 HashCode 的性能成本。

现在考虑 的情况Dictionary<TKey,TValue>。Dictionary 使用的 HashCode 取决于所使用的比较器。默认比较器将使用对象的普通 GetHashCode() 方法。但是您可以创建一个使用不区分大小写的比较器的 Dictionary，并且 Dictionary 使用的 HashCode 将由该比较器生成，这可能会生成与String.GetHashCode(). 那么字符串缓存的是哪个HashCode呢？一个字符串可能在两个字典中，每个字典都使用不同的比较器，它们都不使用普通字符串 GetHashCode。因此，该字符串可能正在缓存一个字典甚至都没有使用的 HashCode。

在 的情况下Dictionary<TKey,TValue>，还有一个更重要的原因是让字符串缓存其 HashCode 可能不会提供性能优势。Dictionary 的内部实现在添加新条目时执行以下操作：

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

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

（如果您想知道 Dictionary 为什么从 HashCode 中去除符号位，那是因为它在 hashCode 字段中使用 -1 作为当前为空的条目槽的标记标志值。）

于 2012-06-22T23:11:50.253 回答