Откуда растут руки у GetHashCode в .NET

    Введение


    Данная статья посвящена теме генерации хеш-кодов на платформе .NET. Тема является достаточно интересной, и думаю любой уважающий себя .NET разработчик должен ее знать. Поэтому поехали!

    Что хранится в объектах помимо их полей?


    Начнем нашу статью с того, что узнаем что хранится у объектов ссылочного типа помимо их полей.

    У каждого объекта ссылочного типа есть так называемый заголовок (Header), который состоит из двух полей: указатель на тип которым является данный объект (MethodTablePointer), а так же индекс синхронизации (SyncBlockIndex).

    Для чего они нужны?

    Первое поле необходимо для того, чтобы каждый управляемый объект мог предоставить информацию о своем типе во время выполнения, то есть нельзя выдать один тип за другой, это сделано для безопасности типов. Так же этот указатель используется для реализации динамической диспетчеризации методов, фактически через него вызываются методы данного объекта. Метод Object.GetType фактически возвращает именно указатель MethodTablePointer.

    Второе поле необходимо для многопоточного окружения, а именно для того чтобы каждый объект можно было использовать потокобезопасно.

    Когда загружается CLR, она создает так называемый пул блоков синхронизации, можно сказать обычный массив этих блоков синхронизации. Когда объекту необходимо работать в многопоточном окружении (это делается с помощью метода Monitor.Enter или конструкции языка C# lock), CLR отыскивает свободный блок синхронизации в своем списке и записывает его индекс в то самое поле в заголовке объекта. Как только объект перестает нуждаться в многопоточном окружение, CLR просто присваивает значение -1 этому полю и тем самым освобождает блок синхронизации.

    Блоки синхронизации — это фактически новое воплощение критических секций из С++. Создатели CLR посчитали, что ассоциировать с каждым управляемым объектом структуру критической секции будет слишком накладно, учитывая, что большинство объектов вообще не используют многопоточное окружение.

    Для большего понимания ситуации рассмотрим следующую картинку:


    По картинке видно, что ObjectA и ObjectB имеют один тип, поскольку их MethodTablePointer-ы указывают на один и тот же тип. ObjectC же имеет другой тип. Так же видно, что ObjectA и ObjectC задействуют пул блоков синхронизации, то есть фактически используют многопоточное окружение. ObjectB не использует пул поскольку его SyncBlockIndex = -1.

    Теперь после того как мы рассмотрели как хранятся объекты, мы можем перейти к генерации хеш-кодов.

    Как работает GetHashCode у ссылочных типов


    То, что метод GetHashCode возвращает адрес объекта в управляемой куче — это миф. Этого быть не может, в виду его не постоянства, сборщик мусора, уплотняя кучу, смещает объекты и соответственно меняет им всем адреса.

    Я не зря начал статью с объяснения того, что такое SyncBlock, поскольку в первых версиях фреймворка в качестве хеш-кода ссылочного типа использовался именно свободный индекс некоторого SyncBlock-а. Таким образом, в .NET 1.0 и .NET 1.1 вызов метода GetHashCode приводил к созданию SyncBlock и занесением его индекса в заголовок объекта в поле SyncBlockIndex. Как вы понимаете это не очень хорошая реализация для хеш-функции, поскольку во-первых создаются не нужные внутренние структуры, которые занимают память + тратиться время на их создание, во-вторых хеш-коды будут идти подряд, то есть будут предсказуемыми. Вот ссылка на блог, в котором один из разработчиков CLR говорит, что такая реализация плохая, и что они ее поменяют в следующей версии.

    Начиная с .NET 2.0 алгоритм хеширования изменился. Теперь он использует manage идентификатор потока, в котором выполняется метод. Если верить реализации в SSCLI20, то метод выглядит так:

    inline DWORD GetNewHashCode()
    {
      // Every thread has its own generator for hash codes so that we won't get into a situation
      // where two threads consistently give out the same hash codes.        
      // Choice of multiplier guarantees period of 2**32 - see Knuth Vol 2 p16 (3.2.1.2 Theorem A)
       DWORD multiplier = m_ThreadId*4 + 5;
       m_dwHashCodeSeed = m_dwHashCodeSeed*multiplier + 1;
       return m_dwHashCodeSeed;
    }
    

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

    Как и раньше хеш-код вычисляется один раз и сохраняется в заголовке объекта в поле SyncBlockIndex (это оптимизация CLR). Теперь возникает вопрос, что если после вызова метода GetHashCode нам понадобиться использовать индекс синхронизации? Куда его записывать? И что делать с хеш-кодом?

    Для ответа на эти вопросы рассмотрим структуру SyncBlock.


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

    Как работает GetHashCode у значимых типов


    Теперь поговорим о том, как работает метод GetHashCode у значимых типов. Скажу заранее, он работает достаточно интересно.

    Первое, что надо сказать так это то, что создатели CLR рекомендуют всегда переопределять данный метод у пользовательских типов, поскольку он может работать не очень быстро, да и поведение его по умолчанию, возможно, не всегда Вас удовлетворит.

    На самом деле у CLR есть две версии реализации метода GetHashCode для значимых типов, и то какая версия будет использована, исключительно зависит от самого типа.

    Первая версия:
    Если структура не имеет ссылочных полей, а так же между ее полями нет свободного места, то используется быстрая версия метода GetHashCode. CLR просто xor — ит каждый 4 байта структуры и получает ответ. Это хороший хеш, так как задействовано всё содержимое структуры. Например, структура, у которой есть поле типа bool и int будет иметь свободное пространство в 3 байта, поскольку JIT когда размещает поля выравнивает их по 4 байта, а, следовательно, будет использована вторая версия для получения хеш-кода.

    Кстати, в реализации данной версии был баг, который исправлен только в .NET 4. Он заключается в том, что хеш-код для типа decimal вычислялся не правильно.

    Рассмотрим код

    decimal d1 = 10.0m;
    decimal d2 = 10.00000000000000000m;
    

    С точки зрения чисел d1 и d2 равны, но их битовые представления отличаются (из-за особенностей представления decimal). А поскольку CLR xor — ит каждый 4 байта (которых всего 4 так как decimal занимает 16 байт), то получаются разные хеш-коды. Кстати, данный баг проявлялся не только у decimal, но и у любой структуры, которая содержит данный тип, а так же использует быструю версию для вычисления хеш-кода.

    Вторая версия:
    Если структура содержит ссылочные поля или между ее полями имеется свободное пространство, то используется медленная версия метода. CLR выбирает первое поле структуры, на основание которого и создает хеш-код. Это поле по возможности должно быть неизменяемым, например, иметь тип string, иначе при его изменении хеш-код будет так же меняться, и мы не сможем уже найти нашу структуру в хеш-таблице, если она использовалась в качестве ключа. Получается, если первое поле структуры будет изменяемым, то это ломает стандартную логику метода GetHashCode. Это еще одна причина по которой структуры должны быть не изменяемыми. CLR xor-ит хеш-код данного поля с указателем на тип данного поля (MethodTablePointer). CLR не рассматривает статические поля, так как статичным полем может быть поле с данным же типов, в результате чего мы впадем в бесконечную рекурсию.

    Комментарий разработчиков CLR к методу GetHashCode у ValueType:
    /*=================================GetHashCode==================================
    ** Action: Our algorithm for returning the hashcode is a little bit complex.  We look
    ** for the first non-static field and get it's hashcode.  If the type has no
    ** non-static fields, we return the hashcode of the type.  We can't take the
    ** hashcode of a static member because if that member is of the same type as
    ** the original type, we'll end up in an infinite loop.
    **Returns: The hashcode for the type.
    **Arguments: None.
    **Exceptions: None.
    ==============================================================================*/
    [MethodImplAttribute(MethodImplOptions.InternalCall)]
    public extern override int GetHashCode();
    // Note that for correctness, we can't use any field of the value type
    // since that field may be mutable in some way.  If we use that field
    // and the value changes, we may not be able to look up that type in a
    // hash table.  For correctness, we need to use something unique to
    // the type of this object.                                                         
    
    // HOWEVER, we decided that the perf of returning a constant value (such as
    // the hash code for the type) would be too big of a perf hit.  We're willing
    // to deal with less than perfect results, and people should still be
    // encouraged to override GetHashCode.                                                              
    


    На заметку

    Структуры не могут содержать экземплярные поля своего же типа. То есть следующий код не будет компилироваться:

    public struct Node
     {
       int data;
       Node node;
     }
    

    Связано это с тем, что структура не может принимать значения null. Следующий код подтверждение тому, что это невозможно:

    var myNode = new Node();
    myNode.node.node.node.node.node.node.node.node.node.......
    

    Однако вполне допускаются статические поля своего же типа, поскольку они хранятся в единственном экземпляре у типа данной структуры. То есть следующий код вполне допустим.

    public struct Node
     {
       int data;
       static Node node;
     }
    

    На заметку

    Чтобы понять ситуацию лучше рассмотрим следующий код:

    var k1 = new KeyValuePair<int, int>(10, 29);
    var k2 = new KeyValuePair<int, int>(10, 31);
    Console.WriteLine("k1 - {0}, k2 - {1}", k1.GetHashCode(), k2.GetHashCode());
    
    var v1 = new KeyValuePair<int, string>(10, "abc");
    var v2 = new KeyValuePair<int, string>(10, "def");
    Console.WriteLine("v1 - {0}, v2 - {1}", v1.GetHashCode(), v2.GetHashCode());
    

    В первом случае у структуры нет ссылочных полей и нет свободного расстояние между полями, поскольку поле int занимает 4 байта, поэтому используется быстрая версия для вычисления хеш-кода, таким образом, будет выведено на консоль:

    k1 — 411217769, k2 — 411217771

    Во втором же случае, у структуры есть ссылочное поле (string), поэтому используется медленная версия. CLR в качестве поля для генерации хеш- кода выбирает поле с типом int, а строковое поле просто игнорируется в результате чего на консоль будет выведено следующее:

    v1 — 411217780, v2 — 411217780

    Теперь думаю понятно, почему разработчики CLR говорят, чтобы все пользовательские значимые типы данных (да и не только значимые, а все вообще) переопределяли метод GetHashCode. Во-первых, он может работать не очень быстро, во-вторых, чтобы избежать непонимания того, почему хеш-коды разных объектов равны, как во втором случае примера.

    Если не переопределить метод GetHashCode можно получить большой удар по производительности при использование значимого типа в качестве ключа в хеш-таблице.

    Как работает GetHashCode у строкового типа


    Класс String переопределяет метод GetHashCode. Его реализация в.NET 4.5 выглядит так:

    GetHashCode X64
    public override unsafe int GetHashCode()
        {
          if (HashHelpers.s_UseRandomizedStringHashing)
            return string.InternalMarvin32HashString(this, this.Length, 0L);
          fixed (char* chPtr1 = this)
          {
            int num1 = 5381;
            int num2 = num1;
            char* chPtr2 = chPtr1;
            int num3;
            while ((num3 = (int) *chPtr2) != 0)
            {
              num1 = (num1 << 5) + num1 ^ num3;
              int num4 = (int) chPtr2[1];
              if (num4 != 0)
              {
                num2 = (num2 << 5) + num2 ^ num4;
                chPtr2 += 2;
              }
              else
                break;
            }
            return num1 + num2 * 1566083941;
          }
        }
    


    Это код для 64 разрядной машины, но если взглянем на общий код с директивами

    GetHashCode
    public int GetHashCode()
      {
        #if FEATURE_RANDOMIZED_STRING_HASHING
         if(HashHelpers.s_UseRandomizedStringHashing)
          { 
           return InternalMarvin32HashString(this, this.Length, 0);
          } 
        #endif // FEATURE_RANDOMIZED_STRING_HASHING
         unsafe
          {
           fixed (char* src = this)
            {
             #if WIN32
              int hash1 = (5381<<16) + 5381; 
             #else
              int hash1 = 5381;
             #endif
              int hash2 = hash1;
             #if WIN32
              // 32 bit machines. 
              int* pint = (int *)src;
              int len = this.Length; 
              while (len > 2) 
               {
                 hash1 = ((hash1 << 5) + hash1 + (hash1 >> 27)) ^ pint[0]; 
                 hash2 = ((hash2 << 5) + hash2 + (hash2 >> 27)) ^ pint[1];
                 pint += 2;
                 len  -= 4;
               } 
                 if (len > 0) 
                  { 
                    hash1 = ((hash1 << 5) + hash1 + (hash1 >> 27)) ^ pint[0];
                  } 
              #else
               int c;
               char* s = src;
                 while ((c = s[0]) != 0)
                  {
                    hash1 = ((hash1 << 5) + hash1) ^ c;
                    c = s[1];
                    if (c == 0)
                      break;
                    hash2 = ((hash2 << 5) + hash2) ^ c;
                      s += 2;
                  }
               #endif
                  return hash1 + (hash2 * 1566083941);
                    }
                }
            }
    


    то заметим, что имеются отличия в зависимости от того какая машина 32 или 64 разрядная.

    Следует сказать, что реализация данного метода меняется с каждым выходом .NET. Об этом писал Эрик Липперт. Он предупреждал, чтобы наш код ни в коем случае не сохранял хеши, которые сгенерированы стандартным путем в базе данных или на диске, поскольку они, скорее всего, поменяют реализацию в следующем выпуски .NET. Так оно и происходило на протяжения последних 4 выпусков .NET.

    Реализация хеширования у строкового типа не подразумевает кэширования результата. То есть каждый раз при вызове метода GetHashCode мы будем заново вычислять хеш-код для строки. По словам Эрика Липперта, это сделано чтобы сэкономить память, лишние 4 байта для каждого объекта строкового типа того не стоят. Учитывая, что реализация очень быстрая, думаю это правильное решение.

    Если вы заметили, в реализации метода GetHashCode появился код, которого раньше не было:

    if (HashHelpers.s_UseRandomizedStringHashing)
       return string.InternalMarvin32HashString(this, this.Length, 0L);
    

    Оказывается в .NET 4.5 появилась возможность вычислять хеш-код для строк для каждого домена. Таким образом, установив значение атрибута в 1 можно добиться, чтобы хеш-код вычислялся на основе домена, в котором вызывается метод. Таким образом, одинаковые строки в разных доменах будут иметь разные хеш-коды. Метод, который генерирует этот хеш-код, является секретным и его реализация не раскрывается.

    Как работает GetHashCode у делегатов


    Прежде чем переходить к рассмотрению реализации метода GetHashCode у делегатов поговорим о том, как они реализованы.

    Каждый делегат наследуется от класса MulticastDelegate, который в свою очередь наследуется от класса Delegate. Эта иерархия сложилась исторически, поскольку можно было бы обойтись одним классом MulticastDelegate.

    Реализация метода GetHashCode в классе Delegate выглядит так

    public override int GetHashCode()
    {
      return this.GetType().GetHashCode();
    }
    

    то есть фактически возвращается хеш-код типа делегата. Получается, делегаты одного типа содержащие разные методы для вызова всегда возвращают один и тот же хеш-код.

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

    Реализация метода в классе MulticastDelegate выглядит так

    public override sealed int GetHashCode()
        {
          if (this.IsUnmanagedFunctionPtr())
            return ValueType.GetHashCodeOfPtr(this._methodPtr) ^ ValueType.GetHashCodeOfPtr(this._methodPtrAux);
    
          object[] objArray = this._invocationList as object[];
          if (objArray == null)
            return base.GetHashCode();
    
          int num = 0;
          for (int index = 0; index < (int) this._invocationCount; ++index)
            num = num * 33 + objArray[index].GetHashCode();
          return num;
        }
    

    Как известно, делегат хранит свои методы в списке _invocationList только в том случае если их более одного.

    Если делегат содержит только один метод, то в коде выше objArray = null и соответственно хеш-код делегата будет равен хеш-коду типа делегата.

    object[] objArray = this._invocationList as object[];
     if (objArray == null)
       return base.GetHashCode();
    

    Для прояснения ситуации рассмотрим следующий код

    Func<int> f1 = () => 1;
    Func<int> f2 = () => 2;
    

    хеш-коды данных делегатов равны хеш-коду типа Func<int>, то есть равны между собой.

    Func<int> f1 = () => 1;
    Func<int> f2 = () => 2;
    
    f1 += () => 3;
    f2 += () => 4;
    

    В данном случае хеш-коды делегатов так же совпадают хоть и методы разные. В этом случае для вычисления хеш-кода используется следующий код

    int num = 0;
    for (int index = 0; index < (int) this._invocationCount; ++index)
      num = num * 33 + objArray[index].GetHashCode();
    return num;
    

    И последний случай

    Func<int> f1 = () => 1;
    Func<int> f2 = () => 2;
    
    f1 += () => 3;
    f1 += () => 5;
                
    f2 += () => 4;
    

    Хеш-коды будут отличаться, из-за того, что количество методов у данных делегатов не равно (каждый метод оказывает влияние на результирующий хеш-код).

    Как работает GetHashCode у анонимных типов


    Как известно, анонимные типы — это новая фича в языке C# 3.0. Причем, это именно фича языка, так называемый синтаксический сахар поскольку CLR о них ничего не знает.

    Метод GetHashCode у них переопределен таким образом, что использует каждое поле. Используя такую реализацию, два анонимных типа возвращают одинаковый хеш-код в том и только в том случае если их все поля равны. Такая реализация делает анонимные типы хорошо подходящими для ключей в хеш-таблицах.

    var newType = new { Name = "Timur", Age = 20, IsMale = true };
    

    Для такого анонимного типа будет сгенерирован следующий код:

    public override int GetHashCode()
      {
        return -1521134295 * (-1521134295 * (-1521134295 * -974875401 + EqualityComparer<string>.Default.GetHashCode(this.Name)) + EqualityComparer<int >.Default.GetHashCode(this.Age)) + EqualityComparer<bool>.Default.GetHashCode(this.IsMale);
      }
    

    На заметку

    Учитывая, что метод GetHashCode переопределен метод Equals, так же должен быть переопределен соответствующим образом.

    var newType = new  { Name = "Timur", Age = 20, IsMale = true };
    var newType1 = new { Name = "Timur", Age = 20, IsMale = true };
    
    if (newType.Equals(newType1))
      Console.WriteLine("method Equals return true");
    else
      Console.WriteLine("method Equals return false");
    
    if (newType == newType1)
      Console.WriteLine("operator == return true");
    else
      Console.WriteLine("operator == return false");
    

    На консоль будет выведено следующее:

    method Equals return true
    operator == return false

    Все дело в том, что анонимные типы переопределяют метод Equals таким образом, что он проверяет все поля как это сделано у ValueType (только без рефлексии), но не переопределяет оператор равенства. Таким образом, метод Equals сравнивает по значению, в то время как оператор равенства сравнивает по ссылкам.

    Для чего надо было переопределять методы Equals и GetHashCode?
    Учитывая, что анонимные типы были созданы для упрощения работы с LINQ, ответ становится понятным. Анонимные типы удобно использовать в качестве хеш-ключей в операциях группировки (group) и соединения (join) в LINQ.

    На заметку

    Заключение


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

    Спасибо за прочтение! Надеюсь, статья оказалось полезной.

    Благодарность пользователю DreamWalker за любезное предоставление обновленных картинок к статье.
    Поделиться публикацией
    Комментарии 29
      0
      каждый поток имеет свой собственный генератор для хэш-кодов, так что мы не можем попасть в ситуацию, где два потока последовательно генерируют одинаковый хэш-код.
      Таки в коде по-английски написано иное: «… ситуацию, где два потока устойчиво генерируют одинаковые хэш-коды». Ещё точнее было бы сказать – ситуация, когда совпадут две последовательности хэш-кодов, генерируемые двумя разными потоками (не обязательно в одно и то же время).

      А однократное совпадение хэш-кодов в двух потоках, очевидно, возможно. Причём эти два события могут произойти и «последовательно» (с точки зрения физического времени).
        +1
        CLR выбирает первое поле структуры, на основание которого и создает хеш-код. Это поле по возможности должно быть неизменяемым, например, иметь тип string, иначе при его изменении хеш-код будет так же меняться, и мы не сможем уже найти нашу структуру в хеш-таблице, если она использовалась в качестве ключа. Получается, если первое поле структуры будет изменяемым, то это ломает стандартную логику метода GetHashCode.
        Когда изменяем содержимое структуры, её хэш-код как правило должен измениться, неправда ли.

        Абзац в коде по-видимому утверждает, что нельзя пользоваться каким-либо полем из объекта‑типа (объекта типа System.Type), поскольку поле может оказаться изменяемым. И тогда хэш-значение изменялось бы из-за каких-то процессов в объекте‑типе, а не из-за изменения содержимого структуры.

        структуры должны быть неизменяемыми.
        Поржал
          0
          >>Когда изменяем содержимое структуры, её хэш-код как правило должен измениться, неправда ли.
          Так в том то и дело, что хэш не изменится при изменении остальных полей.
            0
            Это конечно плохо. Но по-моему автор здесь хочет сказать нечто обратное: что первое поле (а лучше все поля) в структуре должно быть объявлено как readonly. Чтобы хэш-код структуры не мог измениться. Якобы изменяемая структура может иметь проблемы с хэш-таблицами.
              +1
              Автор ничего не говорил о полях только для чтения (readonly). Я сказал, чтобы по возможности первое поле имело неизменяемый тип.
                –2
                Коллега, что такое неизменяемый тип? Тип, в котором все поля объявлены как readonly (а также тип System.String) или что?
                  +2
                  Тип DateTime неизменяем это не значит, что его поля помечены ключевым словом readonly. Если поле помечено ключевым словом readonly это не значит, что нельзя поменять его свойства, это значит просто ссылку на него нельзя поменять.
                  Неизменяемый тип в моем понимание это тип который не предоставляет возможности менять свои свойства как DateTime, например.
                    –5
                    class Program
                    {
                        struct Test
                        {
                            public DateTime  Field;
                        }
                    
                        static void Main()
                        {
                            Test v = new Test(){ Field = DateTime.Now};
                    
                            Console.WriteLine( "{0}", v.GetHashCode());  // Одно значение
                    
                            v.Field = DateTime.Today;
                    
                            Console.WriteLine( "{0}", v.GetHashCode());  // Другое значение
                        }
                    }

                    Неизменяемый тип не помог.
                      +4
                      Почитайте про immutable структуры
                        0
                        Да, неизменяемая структура – известный приём. Но в этой ветке речь о другом.

                        В своей статье timyrik20 сказал, что, если структуру используем в качестве ключа, то хэш‑код структуры должен быть неизменяемым. Это, очевидно, не так. Вот ниже пояснение.

                        Кроме того, в пылу полемики timyrik20 сказал совсем странное: для неизменяемости хэш‑кода нужно, чтоб тип первого поля в структуре был неизменяемым, но объявлять поле как readonly не требуется.

                        Поэтому я и попросил его пояснить, что вообще такое неизменяемый тип в его понимании.

                        Пример кода демонстрирует, что хэш-код структуры изменяем, хотя тип поля таков, как предлагал timyrik20.
                          0
                          В общем случае хэш-код как раз должен быть неизменяемым после инициализации ключа, т. к. реализации таблиц могут быть всякие. В частном же — опять у себя увидел неточность, спасибо — почти всегда все хорошо для стандартных коллекций. А вот оно почти:
                          void Main()
                          {    
                          	var key1 = new Key{
                                                       RefField = new Reference {InnerField = 5},
                                                       ValueField = 3
                                        };
                          	SetKey(key1);
                          	"Before change".Dump();
                          	ShowSetKeyHashCode();
                          	key1.ValueField = 3;
                          	"After value field change".Dump();
                          	ShowSetKeyHashCode();
                          	key1.RefField.InnerField = 8;
                          	"After reference field change".Dump();
                          	ShowSetKeyHashCode();	
                          }
                          
                          private Key _setKey;
                          
                          void SetKey(Key key)
                          {
                             _setKey = key;
                          }
                          
                          void ShowSetKeyHashCode()
                          {
                             ShowKeyHashCode(_setKey);
                          }
                          
                          void ShowKeyHashCode(Key key)
                          {
                             string.Format("Val:{0}, ref: {1}, hash: {2}",key.ValueField,key.RefField.InnerField,key.GetHashCode()).Dump();   
                          }
                          
                          class Reference
                          {
                             public int InnerField;
                             public override int GetHashCode()
                             {
                                return InnerField;
                             }
                          }
                          
                          struct Key
                          {
                             public Reference RefField;
                             public int ValueField; 
                          }

                          Мы инициализируем у структуры Key поле RefField и отдаем эту структуру в качестве ключа. Несмотря на то, что в стандартных реализациях коллекций мы не сможем достучаться до непосредственно значения ключа типа Key (всегда будем получать копию), поменять значение поля Field у известного нам объекта типа Reference мы можем. Соответственно, сохраненный нами в коллекции ключ будет иметь не тот хэш-код, что при занесении в коллекцию, что приведет к невозможности корректного поиска этого ключа.
                          И это именно та ситуация, где поле типа Reference должно быть либо immutable (readonly не спасет), либо value-type.
                          В нашем случае спасает, например, если поменять поля в структуре Key местами. Попробуйте.
                            0
                            В общем случае хэш-код как раз должен быть неизменяемым после инициализации ключа, т. к. реализации таблиц могут быть всякие
                            Пожалуйста, обоснуйте как-нибудь. Какой такой должна быть хэш-таблица, чтобы стала проблемой изменяемая структура в качестве ключа?

                            у структуры Key поле RefField
                            Хорошо, пусть так. А как в этом случае мы относимся к такому коду:
                            Key key2 = key1;
                            key1.RefField.InnerField = 8;
                            

                            Вариант 1. Нельзя изменять содержимое Reference сразу в двух объектах типа Key. Код компилироваться не должен бы.

                            Тогда действительно тип Reference должен быть неизменяемым. Но это никак не связано с хэш-кодами. Неизменяемость Reference требуется и без применения хэш‑таблиц.

                            Вариант 2. Код приемлемый. Да, несколько Key ссылаются на один Reference и этот Reference изменяем (живёт какой‑то своей жизнью).

                            Но такой объект (типа Reference) не должен бы переопределять метод GetHashCode. Лучше использовать базовый GetHashCode.

                            И даже если переопределяет, выход есть: переопределить Key.GetHashCode, так чтобы он вовсе не использовал Reference или использовал только его неизменяемые поля, а если таковых нет, то добавить, например, неизменяемое поле Reference.Id.
                              0
                              Какой такой должна быть хэш-таблица, чтобы стала проблемой изменяемая структура в качестве ключа?

                              Например, предоставляющей исходный массив этих ключей (не спрашивайте зачем, случае разные бывают).
                              Вариант 1.

                              Я не очень понял, зачем эти варианты. Речь идет о минимализации возможностей прострелить себе ногу. С точки зрения .NET ситуация со структурами, ссылающимися на классы, а тем более реализация своего хэш-кода для класса — вполне возможные вещи.
                              И чтобы другие разработчики, не знакомые с тонкостями реализации и не знающие, что «нельзя переопределять у этого класса хэш-код, а то в другом месте коллекция упадет», не стреляли по ногам, предлагается политика, позволяющая обезопаситься в этом и других случаях.
                              Легко ответить на вопросы, зачем переопределять хэш-код и зачем передавать структуру как ключ, но на вопрос зачем передавать как ключ изменяемую структуру — гораздо сложнее.
                                0
                                Например, предоставляющей исходный массив этих ключей
                                Тогда появляется возможность присвоить значение целиком элементу массива. Неизменяемость типа ключа не спасает.

                                предлагается политика, позволяющая обезопаситься
                                А вот есть политика лучше: структура должна переопределить GetHashCode. Тем более что умолчательный GetHashCode неказист – чреват плохим распределением хэш-кодов. А написать переопределение просто (ниже).

                                на вопрос зачем передавать как ключ изменяемую структуру — гораздо сложнее.
                                Без проблем.

                                Векторные изображения. Отрезок в составе изображения:
                                struct Segment
                                {
                                    Image  OwningImage;  // Ссылочный тип.
                                    int  X1, Y1;
                                    int  X2, Y2;
                                
                                    ... // Конструктор копирования.
                                }
                                

                                Хотим отрезок seg2 такой же как seg1, но первый конец сдвинуть на 10 точек.
                                Segment seg2 = new Segment( seg1){ X1 = seg1.X1 + 10,};
                                

                                А если сделать структуру неизменяемой, придётся так:
                                Segment seg2 = new Segment( seg1.OwningImage, seg1.X1 + 10, seg1.Y1, seg1.X2, seg1.Y2);
                                
                                Читабельность хуже плюс шанс ошибиться в порядке аргументов. Либо добавлять вспомогательный метод CloneWithMovedEdge1.
                                  0
                                  Поправка: пропустил public в определениях полей в структуре Segment.
                                    –1
                                    Тогда появляется возможность присвоить значение целиком элементу массива. Неизменяемость типа ключа не спасает.

                                    Вы меня упорно пытаетесь убедить в том, что я не утверждаю, а именно в том, что подход к изменямости решает все проблемы.
                                    Нет, она решает определенное количество неявных и известных проблем за счет явных и недвусмысленных объявлений, поэтому вероятность случайной и непредсказуемой без знания всего кода ошибки снижается.

                                    Касаемо примера — он, конечно, весьма химерический, но он пример вреда обычной измеямой структуры, но я говорил о неизменяемости хэш-кода ключа, а не о изменямости структуры.
                                    А вот есть политика лучше: структура должна переопределить GetHashCode.

                                    И хэш определить и неизменяемой сделать.
                                    Хэш могут потом и поменять, включив по ошибке потенциально изменяемое поле.

                                    Вопрос не в том, зачем изменять структуру (хотя и в этом случае сразу вопрос — а почему не класс?), а зачем передавать изменяемую структуру как ключ.
                                    Либо добавлять вспомогательный метод CloneWithMovedEdge1.

                                    Либо делать для удобного редактирования класс, а для привязки его к таблице — неизменяемый структурный ключ этого отрезка.
              0
              Имеется в виду, что если мы используем хэш-код по прямому назначению — т.е. для оптимизации поиска, то изменение объекта, который мы ищем, может привести к невозможности его повторного поиска — сохраненный алгоритмом хэш автоматически не поменяется (в стандартных реализациях). Соответственно, если уж мы хотим менять объект, то менять его надо так, чтобы хэш оставался неизменным, а именно (в данном случае) все, кроме первого поля.

              Хотя ситуация с изменением объекта после его помещения в хэш таблицу сама по себе не очень хорошая.

              И это, вместе с остальным, является аргументом, почему структуры, которые чаще всего используют как ключи, надо стараться делать неизменяемыми. Об этом «остальном» можно почитать тут: stackoverflow.com/questions/441309/why-are-mutable-structs-evil. Ну и у Липперта в блоге.
                0
                Хотя ситуация с изменением объекта после его помещения в хэш таблицу...
                Пожалуйста, поподробнее про это изменение после помещения. Как такое вообще могло бы выглядеть? Пример кода бы.
                  –2
                  Например так
                  using System;
                  using System.Collections.Generic;
                  
                  namespace HashTest
                  {
                      public struct MutableStruct
                      {
                          private static readonly Random _rnd = new Random();
                  
                          public readonly int Id;
                          public string Title;
                  
                          public MutableStruct(string title)
                          {
                              Id = _rnd.Next();
                              Title = title;
                          }
                      }
                  
                      class Program
                      {
                          static void Main(string[] args)
                          {
                              var tree = new Dictionary<MutableStruct, object>();
                              var key = new MutableStruct("Nice title");
                  
                              tree[key] = new object();
                              
                              Console.WriteLine("Struct is in tree: " + tree.ContainsKey(key)); // True
                  
                              key.Title = "Even better title";
                  
                              Console.WriteLine("Struct is in tree: " + tree.ContainsKey(key)); // False
                  
                              Console.ReadLine();
                          }
                      }
                  }
                  
                  

                    +2
                    Поскольку MutableStruct — это value-тип, то при использовании его в качестве ключа таблица получит свою отдельную копию. И изменение оригинальной структуры, как в вашем примере, на этой копии никаким образом не отразится.

                    Собственно, об этом и речь — изменить поля у value typed ключа в хеш-таблице можно только в том случае, если он явно предоставит API для такого изменения.
                      0
                      Да, я немножко смешал в кучу общий случай, с возможно ссылочным объектом и некоторой абстрактной хэш-таблицей. Для стандартных .NET коллекций такая проблема со структурами не возникнет — потому структуры и используют в качестве ключей.
                      Но комментарий разработчиков (и сам автор), как мне кажется, описывает именно общую возможную ситуацию с хэш-кодом структуры.
                        0
                        UPD: проблема может и возникнуть, см тут
                0
                Простите за глупый вопрос, а в практике как используют GetHashCode? Т.е. для чего он (кроме внутренней организации у обьектов) нужен?
                Вроде сравнение обьекта и без него есть Eval(). Т.е. не понятен смысл зачем его public сделали.
                  +1
                  Он используется например в Dictionary. То есть для любого кастомного типа ключей, если встроенный хэш не устраивает можно написать свой, более эффективный.
                  Ну и с другой стороны, если реализуется своя имплементация того же Dictionary или чего-то еще, где нужен хэш, то удобно знать, что его поддерживают все объекты.
                  0
                  разработчики CLR говорят, чтобы все пользовательские значимые типы данных (да и не только значимые, а все вообще) переопределяли метод GetHashCode.
                  А сами не переопределили для KeyValuePair, как мы теперь видим.
                  +1
                  Кстати, автоматически генерируемый Equals и GetHashCode для анонимных типов очень удобно использовать, определяя свои, если нужен value equality по всем или нескольким полям. Например:

                  struct Point {
                    public int X { get; private set; }
                    public int Y { get; private set; }
                    ...
                    public override int GetHashCode() {
                      return new { X, Y }.GetHashCode();
                    }
                  }
                  

                    0
                    Не согласен с расположением полей в объекте. Поля следует расположить как на картинкеimage
                      0
                      В условиях статьи особого значение не имело их расположение, поэтому я допустил эту вольность. А так MethodTablePointer располагается после SyncBlockIndex-a.

                    Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.

                    Самое читаемое