¿Cómo calcula C# el código hash de un objeto?

Question

Esta pregunta sale del debate en tuples.

Empecé a pensar en el código hash que debe tener una tupla. ¿Qué sucede si aceptamos la clase KeyValuePair como una tupla? No anula el método GetHashCode(), por lo que probablemente no tenga en cuenta los códigos hash de sus "hijos" ... Por lo tanto, el tiempo de ejecución llamará a Object.GetHashCode(), que no tiene conocimiento del estructura real del objeto

Luego podemos hacer dos instancias de algún tipo de referencia, que en realidad son iguales, debido a la sobrecarga GetHashCode() e Igual(). Y úselos como "niños" en tuplas para "engañar" al diccionario.

¡Pero no funciona! ¡El tiempo de ejecución de alguna manera descubre la estructura de nuestra tupla y llama al sobrecargado GetHashCode de nuestra clase!

¿Cómo funciona? ¿Cuál es el análisis realizado por Object.GetHashCode()?

¿Puede afectar el rendimiento en algunos escenarios malos, cuando usamos algunas teclas complicadas? (Probablemente, escenario imposible ... pero aún así)

consideran este código como un ejemplo:

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

actualización creo que he encontrado una explicación para esto como se indica a continuación en mi respuesta. Los principales resultados de la misma son:

• tener cuidado con sus claves y sus códigos hash :-)
• Para complicadas claves del diccionario debe invalidar Iguales() y GetHashCode() correctamente.

Answer 1

Parece que tengo una pista ahora.

Pensé que KeyValuePair es un tipo de referencia, pero no lo es, es una estructura. Y entonces usa el método ValueType.GetHashCode(). MSDN dice: "Uno o más campos del tipo derivado se usan para calcular el valor de retorno".

Si toma un tipo de referencia real como "proveedor de tuplas", engañará al diccionario (oa usted mismo ...).

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

Ya no tengo la referencia del libro, y tendré que encontrarlo solo para confirmarlo, pero pensé que el hash de base predeterminado solo había reunido todos los miembros de su objeto. Tuvieron acceso a ellos debido a la forma en que funcionaba el CLR, por lo que no era algo que pudieras escribir tan bien como lo hicieron.

Eso es completamente de memoria de algo que leo brevemente así que tómalo para lo que quieras.

Edit: El libro fue Inside C# de MS Press. El que tiene la hoja de Sierra en la tapa. El autor pasó mucho tiempo explicando cómo se implementaron las cosas en el CLR, cómo se tradujo el lenguaje a MSIL, etc. ect. Si puedes encontrar el libro, no es una mala lectura.

Editar: formar el enlace que parece que

Object.GetHashCode() utiliza un campo interno en la clase System.Object para generar el valor hash. A cada objeto creado se le asigna una clave de objeto única, almacenada como un entero, cuando se crea . Estas claves comienzan en 1 e incrementan cada vez que se crea un objeto nuevo de .

Hmm Supongo que necesito escribir algunos de mis propios códigos hash, si espero usar objetos como teclas hash.

Answer 3

Este es un excelente artículo sobre GetHashCode de efectivo de C#: http://www.awprofessional.com/content/images/0321245660/items/wagner_item10.pdf

Answer 4

No anule GetHashCode() y equals() en las clases mutables, sólo se anulará en clases o estructuras inmutables, de lo contrario si modifica un objeto utilizado como clave, la tabla hash ya no funcionará correctamente (no podrá recuperar el valor asociado a la clave después de modificar el objeto clave)

También las tablas hash no usan códigos hash para identificar los objetos que utilizar los objetos clave themselfes como identificadores, no es necesario que todas las claves que se utilizan para agregar entradas en una tabla hash devuelvan diferentes códigos hash, pero se recomienda que do, de lo contrario el rendimiento sufre mucho.

Answer 5

Consulte este post de Brad Abrams y también el comentario de Brian Grunkemeyer para obtener más información sobre cómo funciona object.GetHashCode. Además, eche un vistazo al primer comentario en el blog de Ayande post. No sé si las versiones actuales del Framework siguen estas reglas o si realmente lo han cambiado como Brad implicó.

Answer 6

así que probablemente no tenga en cuenta los códigos hash de sus "hijos".

Su ejemplo parece demostrar lo contrario :-) El código hash de la clave y el valor MyClass1 es el mismo para ambos KeyValuePair 's. La implementación de KeyValuePair debe usar tanto su Key como Value para su propio código hash

Al subir de categoría, la clase del diccionario quiere claves únicas. Está utilizando el hashcode proporcionado por cada tecla para resolver las cosas. Recuerde que el tiempo de ejecución no llama al Object.GetHashCode(), sino que llama a la implementación GetHashCode() proporcionada por la instancia que le proporcionó.

considerar un caso más complejo:

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

} 

Básicamente ... en el caso de mi ejemplo, que querrías dos objetos que se encuentran a la misma distancia para regresar "verdadero" de igual a igual, pero sin embargo, devuelve diferentes códigos hash.

Answer 7

Éstos son los hash y la igualdad de las implementaciones adecuadas para la tupla (Quad contiene 4 componentes de tupla en el interior). Este código garantiza el uso correcto de esta tupla específica en HashSets y los diccionarios.

Más sobre el tema (incluido el código fuente) here.

Nota uso del sin control palabra clave (para evitar desbordamientos) y NullReferenceException tirar si obj es nula (como se requiere por el método de base)

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); 
}