ValueType.GetHashCode 的原生实现如何工作

本文关键字：工作 何工作 GetHashCode 原生 实现 ValueType | 更新日期: 2023-09-27 17:55:15

我创建了两个TheKey类型为k1={17,1375984}和k2={17,1593144}的结构。显然，第二个字段中的指针是不同的。但两者都得到相同的哈希代码=346948941。预计会看到不同的哈希代码。请参阅下面的代码。

struct TheKey
{
    public int id;
    public string Name;
    public TheKey(int id, string name)
    {
       this.id = id;
       Name = name;
   }
}
static void Main() {
    // assign two different strings to avoid interning
    var k1 = new TheKey(17, "abc");
    var k2 = new TheKey(17, new string(new[] { 'a', 'b', 'c' }));
    Dump(k1); // prints the layout of a structure
    Dump(k2);
    Console.WriteLine("hash1={0}", k1.GetHashCode());
    Console.WriteLine("hash2={0}", k2.GetHashCode());
}
unsafe static void Dump<T>(T s) where T : struct
{
    byte[] b = new byte[8];
    fixed (byte* pb = &b[0])
    {
        IntPtr ptr = new IntPtr(pb);
        Marshal.StructureToPtr(s, ptr, true);
        int* p1 = (int*)(&pb[0]); // first 32 bits
        int* p2 = (int*)(&pb[4]);
        Console.WriteLine("{0}", *p1);
        Console.WriteLine("{0}", *p2);
    }
}

输出：
17

137598417

1593144哈希1=346948941
哈希2=346948941

ValueType.GetHashCode 的原生实现如何工作

它比眼睛看到的要复杂得多。 对于初学者，为 key2 值提供一个完全不同的字符串。 请注意哈希代码如何仍然相同：

    var k1 = new TheKey(17, "abc");
    var k2 = new TheKey(17, "def");
    System.Diagnostics.Debug.Assert(k1.GetHashCode() == k2.GetHashCode());

这是非常有效的，哈希代码的唯一要求是相同的值产生相同的哈希代码。 不同的值不必生成不同的哈希代码。 这在物理上是不可能的，因为 .NET 哈希代码只能表示 40 亿个不同的值。

计算结构的哈希代码是一项棘手的工作。 CLR 要做的第一件事是检查结构是否包含任何引用类型引用或字段之间是否有间隙。 引用需要特殊处理，因为引用值是随机的。 它是一个指针，当垃圾回收器压缩堆时，其值会发生变化。 结构布局中的间隙是由于对齐而创建的。 具有字节和整数的结构在两个字段之间有 3 个字节的间隙。

如果两者都不是这种情况，则结构值中的所有位都很重要。 CLR 通过对位进行异或运算来快速计算哈希，一次 32 个。 这是一个"好"的哈希，结构中的所有字段都参与哈希代码。

如果结构具有引用类型的字段或具有间隙，则需要另一种方法。 CLR 迭代结构的字段，并查找可用于生成哈希的字段。 可用字段是值类型的字段或非 null 的对象引用。 一旦找到一个，它就会获取该字段的哈希值，使用方法表指针对其进行 xor 并退出。

换句话说，结构中只有一个字段参与哈希代码计算。 在这种情况下，仅使用 id 字段。 这就是字符串成员值无关紧要的原因。

这是一个晦涩难懂的事实，如果您将其留给 CLR 为结构生成哈希代码，显然需要注意这一点。 到目前为止，最好的办法就是永远不要这样做。 如果必须这样做，请确保对结构中的字段进行排序，以便第一个字段为您提供最佳哈希代码。 在您的情况下，只需交换 id 和名称字段。

另一个有趣的花絮，"好"哈希计算代码有一个错误。 当结构包含 System.Decimal 时，它将使用快速算法。 问题是，十进制的位不能代表其数值。 试试这个：

struct Test { public decimal value; }
static void Main() {
    var t1 = new Test() { value = 1.0m };
    var t2 = new Test() { value = 1.00m };
    if (t1.GetHashCode() != t2.GetHashCode())
        Console.WriteLine("gack!");
}

k1 和 k2 包含相同的值。为什么你对它们具有相同的哈希代码感到惊讶？它被约定为为两个比较相等的对象返回相同的值。

哈希代码是从结构/对象的状态（内部值）创建的。不是从保存的地方。根据这个：为什么ValueType.GetHashCode（）像它一样实现？，GetHashCode值类型的默认行为，struct是，是基于值返回哈希。我相信这是正确的行为，特别是对于应该是可识别的结构。

相关文章：