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

Я создал две структуры типа TheKey k1 = {17,1375984} и k2 = {17,1593144}. Obviosly указатели во вторых полях разные. Но оба имеют одинаковый hash-код = 346948941. Ожидается, что вы увидите разные hash-коды. См. Код ниже.

 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 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

Это намного сложнее, чем кажется на первый взгляд. Для начала дайте значение key2 совершенно другой строке. Обратите внимание, как hash-код остается прежним:

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

Что вполне справедливо, единственным требованием для хеш-кода является то, что одно и то же значение создает один и тот же хеш-код. Разным значениям не нужно создавать разные hash-коды. Это физически невозможно, так как hash-код .NET может представлять только 4 миллиарда различных значений.

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

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

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

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

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


Еще один интересный лакомый кусочек, «хороший» код вычисления hashа имеет ошибку. Он будет использовать быстрый алгоритм, если структура содержит 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 содержат одни и те же значения. Почему вы удивлены тем, что у них одинаковый hash-код? Он сжимается, чтобы вернуть одно и то же значение для двух объектов, которые сравниваются как равные.

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

  • Обоснование макроса container_of в linux / list.h
  • Несовместимое неявное объявление встроенной функции 'malloc'
  • Класс смешивания и структура
  • Как скомпилировать C-код с анонимными структурами / объединениями?
  • Скопировать структуру в структуру в C
  • Перейти к встроенному методу дочернего метода struct call вместо родительского метода
  • Структура массивов по сравнению с массивом структур в CUDA
  • Почему я не могу определить конструктор по умолчанию для структуры в .NET?
  • Почему GCC не оптимизирует структуры?
  • Как проверить, имеет ли переменная определенный тип (сравнивают два типа) в C?
  • Почему открытые поля быстрее, чем свойства?
  • Давайте будем гением компьютера.