c# - ¿Cómo funciona la implementación nativa de ValueType.GetHashCode?

struct

Question

TheKey dos estructuras de TheKey tipo k1 = {17,1375984} y k2 = {17,1593144}. Obviamente, los punteros en los segundos campos son diferentes. Pero ambos obtienen el mismo código hash = 346948941. Se espera que veas diferentes códigos hash. Vea el código a continuación.

struct TheKey
{
    public int id;
    public string Name;

    public TheKey(int id, string name)
    {
       this.id = id;
       Name = name;
   }
}

static void Main() {
    // assign two different strings to avoid interning
    var k1 = new TheKey(17, "abc");
    var k2 = new TheKey(17, new string(new[] { ''a'', ''b'', ''c'' }));

    Dump(k1); // prints the layout of a structure
    Dump(k2);

    Console.WriteLine("hash1={0}", k1.GetHashCode());
    Console.WriteLine("hash2={0}", k2.GetHashCode());
}

unsafe static void Dump<T>(T s) where T : struct
{
    byte[] b = new byte[8];
    fixed (byte* pb = &b[0])
    {
        IntPtr ptr = new IntPtr(pb);
        Marshal.StructureToPtr(s, ptr, true);

        int* p1 = (int*)(&pb[0]); // first 32 bits
        int* p2 = (int*)(&pb[4]);

        Console.WriteLine("{0}", *p1);
        Console.WriteLine("{0}", *p2);
    }
}

Salida:
17
1375984
17
1593144
hash1 = 346948941
hash2 = 346948941

Answer 1

Es mucho más complicado de lo que parece. Para empezar, dale al valor key2 una cadena completamente diferente. Observe cómo el código hash sigue siendo el mismo:

    var k1 = new TheKey(17, "abc");
    var k2 = new TheKey(17, "def");
    System.Diagnostics.Debug.Assert(k1.GetHashCode() == k2.GetHashCode());

Lo cual es bastante válido, el único requisito para un código hash es que el mismo valor produzca el mismo código hash. Los diferentes valores no tienen que producir diferentes códigos hash. Eso no es físicamente posible ya que un código hash .NET solo puede representar 4 mil millones de valores distintos.

Calcular el código hash para una estructura es un asunto complicado. Lo primero que hace el CLR es verificar si la estructura contiene referencias de tipo de referencia o si hay espacios entre los campos. Una referencia requiere un tratamiento especial porque el valor de referencia es aleatorio. Es un puntero cuyo valor cambia cuando el recolector de basura compacta el montón. Las lagunas en el diseño de la estructura se crean debido a la alineación. Una estructura con un byte y un int tiene un espacio de 3 bytes entre los dos campos.

Si ninguno es el caso, entonces todos los bits en el valor de la estructura son significativos. El CLR calcula rápidamente el hash por xor-ing los bits, 32 a la vez. Este es un hash "bueno", todos los campos en la estructura participan en el código hash.

Si la estructura tiene campos de un tipo de referencia o tiene espacios, entonces se necesita otro enfoque. El CLR itera los campos de la estructura y busca uno que sea utilizable para generar un hash. Una utilizable es un campo de un tipo de valor o una referencia de objeto que no es nulo. Tan pronto como encuentra uno, toma el hash de ese campo, lo xors con el puntero de la tabla de métodos y se cierra .

En otras palabras, solo un campo en la estructura participa en el cálculo del código hash. Cuál es tu caso, solo se usa el campo de identificación . Por eso, el valor del miembro de cadena no importa.

Este es un factoid oscuro que obviamente es importante tener en cuenta si alguna vez lo dejas al CLR para generar códigos hash para una estructura. De lejos, lo mejor es no hacer esto nunca. Si es necesario, asegúrese de ordenar los campos en la estructura para que el primer campo le proporcione el mejor código hash. En tu caso, simplemente cambia los campos de Id. Y Nombre .

Otro dato interesante, el código de cálculo hash ''bueno'' tiene un error. Utilizará el algoritmo rápido cuando la estructura contenga un System.Decimal. El problema es que los bits de un decimal no son representativos de su valor numérico. Prueba esto:

struct Test { public decimal value; }

static void Main() {
    var t1 = new Test() { value = 1.0m };
    var t2 = new Test() { value = 1.00m };
    if (t1.GetHashCode() != t2.GetHashCode())
        Console.WriteLine("gack!");
}

Answer 2

Los códigos hash se crean a partir del estado (valores dentro) de la estructura / objeto. No desde donde se guarda. Y de acuerdo con esto: ¿Por qué ValueType.GetHashCode () se implementa como es? , el comportamiento predeterminado de GetHashCode para los tipos de valor, que struct es, es devolver el hash en función de los valores. Y creo que ese es el comportamiento correcto, especialmente para las estructuras, que se supone que son imputables.

Answer 3

k1 y k2 contienen los mismos valores. ¿Por qué te sorprende que tengan el mismo código hash? Se contrae para devolver el mismo valor para dos objetos que se pueden comparar como iguales.