Как работает встроенная реализация ValueType.GetHashCode?

Я создал две структуры типа TheKey типа k1 = {17,1375984} и k2 = {17,1593144}. Obviosly указатели во вторых полях разные. Но оба имеют одинаковый хэш-код = 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

Ответы

Ответ 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, это проверить, содержит ли структура какие-либо ссылки ссылочного типа или имеет пробелы между полями. Ссылка требует специального лечения, потому что эталонное значение является случайным. Это указатель, значение которого изменяется, когда сборщик мусора сжимает кучу. Разрывы в структуре структуры создаются из-за выравнивания. Структура с байтом и int имеет 3-байтовый промежуток между двумя полями.

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

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

Иными словами, только одно поле в структуре участвует в вычислении хэш-кода. В вашем случае используется только поле 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!");
}

Ответ 2

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

Ответ 3

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