¿Cuál es el papel de GetHashCode en IEqualityComparer <T> en .NET?

142

Estoy tratando de entender el papel del método GetHashCode de la interfaz IEqualityComparer.

El siguiente ejemplo está tomado de MSDN:

using System;
using System.Collections.Generic;
class Example {
    static void Main() {
        try {

            BoxEqualityComparer boxEqC = new BoxEqualityComparer();

            Dictionary<Box, String> boxes = new Dictionary<Box,
                                                string>(boxEqC);

            Box redBox = new Box(4, 3, 4);
            Box blueBox = new Box(4, 3, 4);

            boxes.Add(redBox, "red");
            boxes.Add(blueBox, "blue");

            Console.WriteLine(redBox.GetHashCode());
            Console.WriteLine(blueBox.GetHashCode());
        }
        catch (ArgumentException argEx) {

            Console.WriteLine(argEx.Message);
        }
    }
}

public class Box {
    public Box(int h, int l, int w) {
        this.Height = h;
        this.Length = l;
        this.Width = w;
    }
    public int Height { get; set; }
    public int Length { get; set; }
    public int Width { get; set; }
}

class BoxEqualityComparer : IEqualityComparer<Box> {

    public bool Equals(Box b1, Box b2) {
        if (b1.Height == b2.Height & b1.Length == b2.Length
                            & b1.Width == b2.Width) {
            return true;
        }
        else {
            return false;
        }
    }

    public int GetHashCode(Box bx) {
        int hCode = bx.Height ^ bx.Length ^ bx.Width;
        return hCode.GetHashCode();
    }
}

¿No debería ser suficiente la implementación del método Equals para comparar dos objetos Box? Ahí es donde le decimos al marco la regla utilizada para comparar los objetos. ¿Por qué se necesita el GetHashCode?

Gracias.

Lucian

Lucian
fuente
Lea: en.wikipedia.org/wiki/Hash_table y luego vea si comprende mejor el propósito de GetHashCode.
gastador
1
Vea esta excelente respuesta: stackoverflow.com/a/3719802/136967
Mikhail el

Respuestas:

201

Un poco de historia primero...

Cada objeto en .NET tiene un método Equals y un método GetHashCode.

El método Equals se usa para comparar un objeto con otro objeto, para ver si los dos objetos son equivalentes.

El método GetHashCode genera una representación entera de 32 bits del objeto. Dado que no hay límite para la cantidad de información que puede contener un objeto, varios códigos hash son compartidos por varios objetos, por lo que el código hash no es necesariamente único.

Un diccionario es una estructura de datos realmente genial que intercambia una mayor huella de memoria a cambio de (más o menos) costos constantes para las operaciones Agregar / Eliminar / Obtener. Sin embargo, es una mala elección para repetir. Internamente, un diccionario contiene una serie de cubos, donde se pueden almacenar valores. Cuando agrega una clave y un valor a un diccionario, se llama al método GetHashCode en la clave. El código hash devuelto se utiliza para determinar el índice del depósito en el que se debe almacenar el par Clave / Valor.

Cuando desee acceder al Valor, vuelva a pasar la Clave. El método GetHashCode se llama en la clave y se encuentra el depósito que contiene el valor.

Cuando se pasa un IEqualityComparer al constructor de un diccionario, se utilizan los métodos IEqualityComparer.Equals e IEqualityComparer.GetHashCode en lugar de los métodos en los objetos Key.

Ahora, para explicar por qué ambos métodos son necesarios, considere este ejemplo:

BoxEqualityComparer boxEqC = new BoxEqualityComparer(); 

Dictionary<Box, String> boxes = new Dictionary<Box, string>(boxEqC); 

Box redBox = new Box(100, 100, 25);
Box blueBox = new Box(1000, 1000, 25);

boxes.Add(redBox, "red"); 
boxes.Add(blueBox, "blue"); 

Usando el método BoxEqualityComparer.GetHashCode en su ejemplo, ambos cuadros tienen el mismo código hash - 100 ^ 100 ^ 25 = 1000 ^ 1000 ^ 25 = 25 - aunque claramente no son el mismo objeto. La razón por la que son el mismo código hash en este caso es porque está utilizando el operador ^ (bitwise exclusive-OR), por lo que 100 ^ 100 se cancela dejando cero, al igual que 1000 ^ 1000. Cuando dos objetos diferentes tienen la misma clave, lo llamamos colisión.

Cuando agregamos dos pares clave / valor con el mismo código hash a un diccionario, ambos se almacenan en el mismo depósito. Entonces, cuando queremos recuperar un valor, se llama al método GetHashCode en nuestra clave para ubicar el depósito. Dado que hay más de un valor en el depósito, el diccionario itera sobre todos los pares Clave / Valor en el depósito que llama al método Equals en las Teclas para encontrar el correcto.

En el ejemplo que publicó, los dos cuadros son equivalentes, por lo que el método Equals devuelve verdadero. En este caso, el diccionario tiene dos claves idénticas, por lo que arroja una excepción.

TLDR

En resumen, el método GetHashCode se usa para generar una dirección donde se almacena el objeto. Entonces un diccionario no tiene que buscarlo. Simplemente calcula el código hash y salta a esa ubicación. El método Equals es una mejor prueba de igualdad, pero no se puede utilizar para asignar un objeto a un espacio de direcciones.

sheikhjabootie
fuente
44
Para aquellos que se preguntan cuál es el operador ^, este es el operador OR exclusivo bit a bit, consulte msdn.microsoft.com/en-us/library/zkacc7k1.aspx .
R. Schreurs
2
Solo para señalar esto explícitamente: ( msdn.microsoft.com/en-us/library/ms132155.aspx ) Notas para los implementadores Se requieren implementaciones para garantizar que si el método Equals devuelve verdadero para dos objetos x e y, entonces el valor devuelto por el método GetHashCode para x debe ser igual al valor devuelto por y.
Diego Frehner
2
@DiegoFrehner - Tienes toda la razón. Otra cosa que puede hacer tropezar a las personas es que el valor del método GetHashCode no debe variar si se modifica el objeto. Por lo tanto, los campos dentro del objeto del que depende GetHashCode deben ser de solo lectura (inmutables). Aquí hay una explicación: stackoverflow.com/a/4868940/469701
sheikhjabootie
1
@Acentric: el código hash de un objeto no debe cambiar a menos que esté mutado de una manera que afecte la igualdad. Si una clase puede ser mutada de tal manera que afecte la igualdad, el código debe evitar almacenar en un diccionario cualquier instancia que pueda estar expuesta a un código que la mute mientras está en el diccionario. Si el código que almacena el objeto cumple con esa regla, puede ser útil tener un código hash que refleje el estado mutable. Es una lástima que .NET no distinga mejor la igualdad y equivalencia de estado, ya que ambos son conceptos útiles.
supercat
3
@Acentric: incluso más allá de usar el código hash para el direccionamiento de la tabla hash, la idea fundamental detrás de un código hash es que el conocimiento de que dos objetos tienen códigos hash diferentes implica que son desiguales y no necesitan compararlos. Como corolario, saber que los códigos hash de muchos objetos no coinciden con el código hash de un objeto dado implica que ninguno de ellos es igual al objeto. Usar un código hash para direccionar es básicamente una forma de ignorar objetos que tienen diferentes códigos hash.
supercat
9

GetHashCode se usa en colecciones de Diccionario y crea hash para almacenar objetos en él. Aquí hay un buen artículo sobre por qué y cómo usar IEqualtyComparer y GetHashCode http://dotnetperls.com/iequalitycomparer

Ceniza
fuente
44
Más: si necesita comparar Equals sería suficiente, pero cuando necesita obtener un elemento del Diccionario, es más fácil hacerlo mediante hash, no utilizando Equals .
Ash el
5

Si bien es posible que una persona Dictionary<TKey,TValue>tenga sus GetValuemétodos y otros similares Equalsen cada clave almacenada para ver si coincide con la que se busca, sería muy lento. En cambio, como muchas colecciones basadas en hash, depende GetHashCodede excluir rápidamente la mayoría de los valores no coincidentes de la consideración. Si llamar GetHashCodea un artículo que se busca produce 42, y una colección tiene 53,917 artículos, pero llamar GetHashCodea 53,914 de los artículos arrojó un valor diferente a 42, entonces solo 3 artículos tendrán que compararse con los que se buscan. Los otros 53,914 pueden ser ignorados de manera segura.

La razón por la que GetHashCodese incluye a en a IEqualityComparer<T>es para permitir la posibilidad de que el consumidor de un diccionario quiera considerar objetos iguales que normalmente no se considerarían iguales. El ejemplo más común sería una persona que llama que quiere usar cadenas como teclas pero utiliza comparaciones que no distinguen entre mayúsculas y minúsculas. Para que ese trabajo funcione eficientemente, el diccionario necesitará tener alguna forma de función hash que produzca el mismo valor para "Fox" y "FOX", pero esperemos que produzca algo más para "box" o "zebra". Dado que el GetHashCodemétodo incorporado Stringno funciona de esa manera, el diccionario necesitará obtener dicho método de otro lugar, y un método que considere "Fox" y "FOX" idénticos entre sí,IEqualityComparer<T>Equals

Super gato
fuente
¡La respuesta correcta y directa a la pregunta! GetHashCode () tiene que complementar Equals () para los objetos en cuestión.
Sumith
@Sumith: muchas discusiones sobre hashing hablan de cubos, pero creo que es más útil pensar en la exclusión. Si las comparaciones son caras, el hashing podría ofrecer beneficios incluso cuando se usan colecciones que no están organizadas en cubos.
supercat