c# - programacion - huella hash

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

Question

Esta pregunta surge de la discusión sobre las tuplas .

Empecé a pensar en el código hash que debe tener una tupla. ¿Qué pasa 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

Entonces podemos hacer dos instancias de algún tipo de referencia, que en realidad son iguales, debido a GetHashCode () sobrecargado 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!

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

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

Considere 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 esto son:

• Ten cuidado con tus claves y sus códigos hash :-)
• Para claves de diccionario complicadas, debe anular correctamente Equals () y GetHashCode ().

Answer 1

por lo que probablemente no tenga conocimiento de los códigos hash de sus "hijos".

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

Avanzando, 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 a Object.GetHashCode() , sino que llama a la implementación GetHashCode () proporcionada por la instancia que le proporcionó.

Considere 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, desearía que dos objetos que están a la misma distancia devuelvan "verdadero" para Equals, pero que devuelvan diferentes códigos hash.

Answer 2

Aquí están las implementaciones adecuadas de Hash y de igualdad para la tupla Quad (contiene 4 componentes de tupla dentro). 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) aquí .

Tenga en cuenta el uso de la palabra clave no seleccionada (para evitar desbordamientos) y el lanzamiento de NullReferenceException si obj es nulo (como lo exige el método 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);
}

Answer 3

Consulte esta publicación 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 la publicación de blog de Ayande. No sé si las versiones actuales del Framework siguen estas reglas o si realmente lo han cambiado como Brad implicó.

Answer 4

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

Answer 5

No anule GetHashcode () y Equals () en clases mutables, solo anule 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 que se modificó el objeto clave)

Además, las tablas hash no usan códigos hash para identificar los objetos que utilizan los objetos clave themselfes como identificadores, no es necesario que todas las claves que se utilizan para agregar entradas en una tabla hash devuelvan códigos hash diferentes, pero se recomienda que lo hagan, sino el rendimiento sufre mucho

Answer 6

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 7

Ya no tengo la referencia del libro, y tendré que encontrarlo solo para confirmarlo, pero pensé que el hash base predeterminado simplemente ha ordenado todos los miembros de tu 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 del recuerdo de algo que leí brevemente, así que tómalo por lo que desees.

Editar: 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: forma el enlace siempre que se vea como

Object.GetHashCode () usa 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 cualquier tipo.

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