Каждый разработчик должен знать! Хеш-коды объектов в CLR на C#

Многие начинающие разработчики и даже достаточно опытные, "погружаясь в платформу .Net" забывают про базовые понятия которые нужно знать и запомнить навсегда. Знаем мы, что такое делегаты, деревья выражений, вариантность и прочее. Но вот про методы Equals() и GetHashCode(), вроде и читали, но не особо запомнили.

В данном цикле статей я попытаюсь описать наиболее базовые вещи и понятия (особенно те о которых часто спрашивают на форумах MSDN), про которые часто забываем. Бывает нужно это не часто, ведь мы в основном используем уже написанный код библиотек, но знать об этом и помнить нужно. Основные правила касательно хеш-кодов объектов, которые надо запомнить:

  • Создаёшь тип и переопределяешь метод Equals() не забудь и про метод GetHashCode().
  • Не забывай про эти методы, если код их будет интенсивно использовать. Например, в качестве ключей коллекций.
  • Базовые реализации этих методов для ссылочных и значимых типов работают медленно, особенно для последних.

Это самые основные на мой взгляд, хотя есть ещё много нюансов. Чтобы не быть голословным рассмотрим на примере. На форумах был вопрос по этому поводу, вот код.

namespace ConsoleApplication
{
  public class TestClass
  {
    public int TestField1;
    public int TestField2;
    public override int GetHashCode()
    {
      return TestField1 ^ TestField2;
    }
  }
  public struct TestStruct
  {
    public int TestField1;
    public int TestField2;
    public override int GetHashCode()
    {
      return TestField1 ^ TestField2;
    }
  }
  class Program
  {
    static void GCTextDump()
    {
      GC.Collect();
      Console.WriteLine(String.Format("{0}-{1}-{2}",
        GC.CollectionCount(0),
        GC.CollectionCount(1),
        GC.CollectionCount(2)));
    }
    static void Main(string[] args)
    {
      TestClass TestObject1 = new TestClass();
      Dictionary<TestClass, int> TestClassDict = new Dictionary<TestClass, int>();
      TestClassDict.Add(TestObject1, 1);

      TestStruct TestObject2 = new TestStruct();
      Dictionary<TestStruct, int> TestStructDict = new Dictionary<TestStruct, int>();
      TestStructDict.Add(TestObject2, 1);

      int a;
      int time = Environment.TickCount;
      for (int i = 0; i < 1000000; i++)
        a = TestClassDict[TestObject1];
      time = Environment.TickCount - time;
      Console.WriteLine("ElapseTime" + time.ToString());
      GCTextDump();

      time = Environment.TickCount;
      for (int i = 0; i < 1000000; i++)
        a = TestStructDict[TestObject2];
      time = Environment.TickCount - time;
      Console.WriteLine("ElapseTime" + time.ToString());
      GCTextDump();

      Console.ReadKey();
    }
  }
}
Вопрос следующий: почему разница времени извлечения ключей для значимых типов больше чем два раза (если запустить этот код, можно увидеть, что это именно так)? Думаю ответ на это вопрос уже ясен. И разные мифы про ссылочные и значимые типы тут не совсем уместны. Уберём лишнее, немножечко подправим код и будем экспериментировать.

#define EQUALS
#define GETHASHCODE

using System;
using System.Collections.Generic;

namespace ObjectHashCode
{
    class Program
    {
        static void Main(string[] args)
        {
          TestClass testObject1 = new TestClass();
          Dictionary<TestClass, int> TestClassDict = new Dictionary<TestClass, int>();
          TestClassDict.Add(testObject1, 1);

          TestStruct testObject2 = new TestStruct();
          Dictionary<TestStruct, int> TestStructDict = new Dictionary<TestStruct, int>();
          TestStructDict.Add(testObject2, 1);

          int value;

          System.Diagnostics.Stopwatch sw = new System.Diagnostics.Stopwatch();
          sw.Start();
          for (int i = 0; i < 1000000; i++)
            value = TestClassDict[testObject1];
          sw.Stop();
          Console.WriteLine("ElapseTime " + sw.Elapsed.Milliseconds);
          sw.Reset();

          sw.Start();
          for (int i = 0; i < 1000000; i++)
            value = TestStructDict[testObject2];
          sw.Stop();
          Console.WriteLine("ElapseTime " + sw.Elapsed.Milliseconds);
        }
    }
    public class TestClass
    {
      public int TestField1;
      public int TestField2;

#if GETHASHCODE
      public override int GetHashCode()
      {
        return TestField1 ^ TestField2;
      }
#endif
#if EQUALS
      public override bool Equals(object obj)
      {
        return (TestField1 == ((TestClass)obj).TestField1) 
          && (TestField2 == ((TestClass)obj).TestField2);
      }
#endif
    }
    public struct TestStruct
    {
      public int TestField1;
      public int TestField2;
#if GETHASHCODE
      public override int GetHashCode()
      {
        return TestField1 ^ TestField2;
      }
#endif
#if EQUALS
      public override bool Equals(object obj)
      {
        return (TestField1 == ((TestStruct)obj).TestField1) 
          && (TestField2 == ((TestStruct)obj).TestField2);
      }
#endif
    }
}
Код без переопределения обеих методов.

Переопределяем метод Equals( ). Для значимых типов результат несколько улучшился.

Переопределяем метод GetHashCode( ). Результат стал лучше, чем в предыдущем случае.

Переопределяем оба метода, и видим что для значимых типов результа улучшился почти в три раза.

Отсюда вывод, что в данном случае на производительность влияет не упаковка и распаковка (хотя в некоторой степени это имеет значение), а вычисление хеш-кодов.

q1
28.01.2013 12:34
Действительно, в варианте Equals и GetHashCode типа ValueType используется механизм отражения (относитительно очень долгий), отсюда такие задержки