Как работает нативная реализация 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 может представлять только 4 миллиарда различных значений.

Расчет хеш-кода для структуры - сложная задача.Первое, что делает CLR, это проверяет, содержит ли структура какие-либо ссылки на ссылочный тип или есть ли пропуски между полями.Ссылка требует особого отношения, потому что эталонное значение является случайным.Это указатель, значение которого изменяется, когда сборщик мусора сжимает кучу.Пробелы в структуре структуры создаются из-за выравнивания.Структура с байтами и целыми числами имеет 3-байтовый промежуток между двумя полями.

Если ни один из этих случаев не имеет значения, то все биты в значении структуры значимы.CLR быстро вычисляет хэш, сохраняя 32 бита за раз.Это «хороший» хеш, все поля в структуре участвуют в хеш-коде.

Если структура имеет поля ссылочного типа или имеет пробелы, тогда необходим другой подход.CLR повторяет поля структуры и ищет то, которое можно использовать для генерации хеша.Используемое поле - это поле типа значения или ссылка на объект, которая не является нулевой.Как только он находит его, он берет хеш этого поля, перезаписывает его с указателем таблицы методов и завершает работу .

Другими словами, только одно полев структуре участвует в расчете хеш-кода.В вашем случае используется только поле id .Вот почему значение строкового члена не имеет значения.

Это неясный фактоид, о котором, очевидно, важно знать, если вы когда-нибудь оставите его в CLR для генерации хеш-кодов для структуры.Безусловно, лучшее, что нужно сделать, это просто никогда не делать этого.Если вам нужно, то не забудьте упорядочить поля в структуре, чтобы первое поле дало вам лучший хэш-код.В вашем случае просто поменяйте местами поля id и Name .

---

Еще один интересный трюк, код вычисления хорошего хеша содержит ошибку.Он будет использовать быстрый алгоритм, когда структура содержит 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!");
}

Answer 2

k1 и k2 содержат одинаковые значения.Почему вы удивлены тем, что они имеют одинаковый хэш-код?Контракт возвращает одно и то же значение для двух объектов, которые сравниваются как равные.

Answer 3

Хеш-коды создаются из состояния (значений внутри) структуры / объекта. Не от того, где это сохранено. И в соответствии с этим: Почему ValueType.GetHashCode () реализован так, как он есть? , поведение по умолчанию GetHashCode для типов значений, которым является struct, - возвращать хеш на основе значений. И я считаю, что это правильное поведение, особенно для структур, которые считаются неизменными.