Главная
Блог разработчиков phpBB
 
+ 17 предустановленных модов
+ SEO-оптимизация форума
+ авторизация через соц. сети
+ защита от спама

Откуда растут руки у GetHashCode

Anna | 18.06.2014 | нет комментариев

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

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

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

У всякого объекта ссылочного типа есть так называемый заголовок (Header), тот, что состоит из 2-х полей: указатель на тип которым является данный объект (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;
}

Таким образом, всякий поток имеет свой личный генератор для хэш-кодов, так что мы не можем попасть в обстановку, где дlts, 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 для ваших пользовательских типов, тем самым подстраивая их к определенной вашей обстановки.

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

Источник: programmingmaster.ru

Оставить комментарий
Форум phpBB, русская поддержка форума phpBB
Рейтинг@Mail.ru 2008 - 2017 © BB3x.ru - русская поддержка форума phpBB