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

Question

我创建了两个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
1375984
17
1593144
hash1 = 346948941
hash2 = 346948941

Answer 1

它比眼睛要复杂得多.对于初学者,给key2值一个完全不同的字符串.请注意哈希码如何仍然相同:

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

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

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

如果不是这种情况,那么结构值中的所有位都是重要的.CLR通过一次对32位进行xor运算来快速计算哈希值.这是一个"好"的哈希,结构中的所有字段都参与哈希码.

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

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

这是一个模糊的事实,如果你把它留给CLR生成一个结构的哈希码,显然很重要.到目前为止,最好的办法就是永远不要这样做.如果必须,请确保在结构中对字段进行排序,以便第一个字段为您提供最佳的哈希代码.在您的情况下,只需交换id和Name字段.

另一个有趣的消息,'好'哈希计算代码有一个bug.当结构包含System.Decimal时,它将使用快速算法.问题是,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!");
}

Answer 2

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