Как C# вычисляет хэш-код для объекта?

Question

Этот вопрос выходит из обсуждения на tuples.

Я начал думать о хэш-коде, который должен иметь кортеж. Что делать, если мы примем класс KeyValuePair как кортеж? Он не переопределяет метод GetHashCode(), поэтому, вероятно, он не будет знать хэш-коды его «детей» ... Итак, время выполнения вызовет Object.GetHashCode(), который не знает о реальная структура объекта.

Тогда мы можем сделать два экземпляра некоторого ссылочного типа, которые на самом деле равны, из-за перегруженных GetHashCode() и Equals(). И используйте их как «дети» в кортежах, чтобы «обмануть» словарь.

Но это не сработает! Время выполнения каким-то образом определяет структуру нашего кортежа и вызывает перегруженный GetHashCode нашего класса!

Как это работает? Что такое анализ, сделанный Object.GetHashCode()?

Может ли это повлиять на производительность в некотором плохом сценарии, когда мы используем сложные клавиши? (Вероятно, невозможно сценарий ... но все же)

Рассмотрим этот код в качестве примера:

namespace csharp_tricks 
{ 
    class Program 
    { 
     class MyClass 
     { 
      int keyValue; 
      int someInfo; 

      public MyClass(int key, int info) 
      { 
       keyValue = key; 
       someInfo = info; 
      } 

      public override bool Equals(object obj) 
      { 
       MyClass other = obj as MyClass; 
       if (other == null) return false; 

       return keyValue.Equals(other.keyValue); 
      } 

      public override int GetHashCode() 
      { 
       return keyValue.GetHashCode(); 
      } 
     } 

     static void Main(string[] args) 
     { 
      Dictionary<object, object> dict = new Dictionary<object, object>(); 

      dict.Add(new KeyValuePair<MyClass,object>(new MyClass(1, 1), 1), 1); 

      //here we get the exception -- an item with the same key was already added 
      //but how did it figure out the hash code? 
      dict.Add(new KeyValuePair<MyClass,object>(new MyClass(1, 2), 1), 1); 

      return; 
     } 
    } 
} 

Update Я думаю, я нашел объяснение этому, как указано ниже в моем ответе. Основными результатами этого являются:

• Будьте осторожны с ключами и их хэш-кодов :-)
• Для сложных словарных ключей необходимо переопределить Equals() и GetHashCode() правильно.

Answer 1

Кажется, что у меня есть ключ сейчас.

Я думал, что KeyValuePair является ссылочным типом, но это не так, это структура. И поэтому он использует метод ValueType.GetHashCode(). MSDN для него говорит: «Для вычисления возвращаемого значения используется одно или несколько полей производного типа.

Если вы возьмете настоящий ссылочный тип как «кортеж-провайдер», вы обманете словарь (или себя ...).

using System.Collections.Generic; 

namespace csharp_tricks 
{ 
    class Program 
    { 
     class MyClass 
     { 
      int keyValue; 
      int someInfo; 

      public MyClass(int key, int info) 
      { 
       keyValue = key; 
       someInfo = info; 
      } 

      public override bool Equals(object obj) 
      { 
       MyClass other = obj as MyClass; 
       if (other == null) return false; 

       return keyValue.Equals(other.keyValue); 
      } 

      public override int GetHashCode() 
      { 
       return keyValue.GetHashCode(); 
      } 
     } 

     class Pair<T, R> 
     { 
      public T First { get; set; } 
      public R Second { get; set; } 
     } 

     static void Main(string[] args) 
     { 
      var dict = new Dictionary<Pair<int, MyClass>, object>(); 

      dict.Add(new Pair<int, MyClass>() { First = 1, Second = new MyClass(1, 2) }, 1); 

      //this is a pair of the same values as previous! but... no exception this time... 
      dict.Add(new Pair<int, MyClass>() { First = 1, Second = new MyClass(1, 3) }, 1); 

      return; 
     } 
    } 
} 

Answer 2

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

Это полностью из памяти того, что я кратко прочитал, поэтому возьмите его за то, что пожелаете.

Редактировать: Книга была Внутри C# от MS Press. Один с пилой на обложке. Автор потратил много времени, объясняя, как все было реализовано в CLR, как перевод языка на MSIL и т. Д. ЭСТ. Если вы можете найти книгу, это неплохо читается.

Edit: Сформировать ссылку, если она выглядит как

Object.GetHashCode() использует внутреннее поле в классе System.Object для генерации хэш-значения. Каждому создаваемому объекту присваивается уникальный ключ объекта, который хранится как целое число, когда создается . Эти ключи начинаются с 1 и увеличиваются каждый раз, когда создается новый объект .

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

Answer 3

Это отличная статья на GetHashCode от эффективной C#: http://www.awprofessional.com/content/images/0321245660/items/wagner_item10.pdf

Answer 4

Не переопределять GetHashCode() и Equals() на изменяемых классов, только переопределить его на неизменяемых классов или структур, иначе, если вы изменяете объект используемый в качестве ключа, хэш-таблица больше не будет функционировать должным образом (вы не сможете получить значение, связанное с ключом после изменения ключевого объекта)

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

Answer 5

Отметьте это post от Brad Abrams, а также комментарий Брайана Грункмайера для получения дополнительной информации о том, как object.GetHashCode работает. Кроме того, взгляните на первый комментарий к блогу Айанде post. Я не знаю, соответствуют ли текущие версии Рамочной программы этим правилам или же они действительно изменили ее, как предполагал Брэд.

Answer 6

так что, возможно, он не будет знать о хэш-кодах его «детей».

Ваш пример, кажется, доказать обратное :-) хэш-код для ключа MyClass и значение 1 одинакова для обоих KeyValuePair-х гг. Реализация KeyValuePair должна использовать как ее Key, так и Value для собственного хеш-кода

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

Рассмотрим более сложный случай:

public class HappyClass 
{ 


    enum TheUnit 
    { 
     Points, 
     Picas, 
     Inches 
    } 

    class MyDistanceClass 
    { 
     int distance; 
     TheUnit units; 

     public MyDistanceClass(int theDistance, TheUnit unit) 
     { 
      distance = theDistance; 

      units = unit; 
     } 
     public static int ConvertDistance(int oldDistance, TheUnit oldUnit, TheUnit newUnit) 
     { 
      // insert real unit conversion code here :-) 
      return oldDistance * 100; 
     } 

     /// <summary> 
     /// Figure out if we are equal distance, converting into the same units of measurement if we have to 
     /// </summary> 
     /// <param name="obj">the other guy</param> 
     /// <returns>true if we are the same distance</returns> 
     public override bool Equals(object obj) 
     { 
      MyDistanceClass other = obj as MyDistanceClass; 
      if (other == null) return false; 

      if (other.units != this.units) 
      { 
       int newDistance = MyDistanceClass.ConvertDistance(other.distance, other.units, this.units); 
       return distance.Equals(newDistance); 
      } 
      else 
      { 
       return distance.Equals(other.distance); 
      } 


     } 

     public override int GetHashCode() 
     { 
      // even if the distance is equal in spite of the different units, the objects are not 
      return distance.GetHashCode() * units.GetHashCode(); 
     } 
    } 
    static void Main(string[] args) 
    { 

     // these are the same distance... 72 points = 1 inch 
     MyDistanceClass distPoint = new MyDistanceClass(72, TheUnit.Points); 
     MyDistanceClass distInch = new MyDistanceClass(1, TheUnit.Inch); 

     Debug.Assert(distPoint.Equals(distInch), "these should be true!"); 
     Debug.Assert(distPoint.GetHashCode() != distInch.GetHashCode(), "But yet they are fundimentally different values"); 

     Dictionary<object, object> dict = new Dictionary<object, object>(); 

     dict.Add(new KeyValuePair<MyDistanceClass, object>(distPoint, 1), 1); 

     //this should not barf 
     dict.Add(new KeyValuePair<MyDistanceClass, object>(distInch, 1), 1); 

     return; 
    } 

} 

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

Answer 7

Вот правильные реализации хэша и равенства для четырехместного набора (содержит 4 элемента кортежа внутри). Этот код обеспечивает правильное использование этого конкретного кортежа в HashSets и словарях.

Подробнее об объекте (включая исходный код) here.

Примечание использование в непроверенной ключевого слова (чтобы избежать переполнения) и бросали NullReferenceException, если OBJ является недействительным (в соответствии с требованиями базового метода)

public override bool Equals(object obj) 
{ 
    if (ReferenceEquals(null, obj)) 
     throw new NullReferenceException("obj is null"); 
    if (ReferenceEquals(this, obj)) return true; 
    if (obj.GetType() != typeof (Quad<T1, T2, T3, T4>)) return false; 
    return Equals((Quad<T1, T2, T3, T4>) obj); 
} 

public bool Equals(Quad<T1, T2, T3, T4> obj) 
{ 
    if (ReferenceEquals(null, obj)) return false; 
    if (ReferenceEquals(this, obj)) return true; 
    return Equals(obj.Item1, Item1) 
     && Equals(obj.Item2, Item2) 
      && Equals(obj.Item3, Item3) 
       && Equals(obj.Item4, Item4); 
} 

public override int GetHashCode() 
{ 
    unchecked 
    { 
     int result = Item1.GetHashCode(); 
     result = (result*397)^Item2.GetHashCode(); 
     result = (result*397)^Item3.GetHashCode(); 
     result = (result*397)^Item4.GetHashCode(); 
     return result; 
    } 
} 
public static bool operator ==(Quad<T1, T2, T3, T4> left, Quad<T1, T2, T3, T4> right) 
{ 
    return Equals(left, right); 
} 


public static bool operator !=(Quad<T1, T2, T3, T4> left, Quad<T1, T2, T3, T4> right) 
{ 
    return !Equals(left, right); 
}