c# - ¿Cuál es el rol de GetHashCode en el IEqualityComparer<T> en.NET?

Question

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

El siguiente ejemplo se toma 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 la implementación del método Equals ser suficiente para comparar dos objetos Box? Ahí es donde le decimos al marco la regla utilizada para comparar los objetos. ¿Por qué es necesario GetHashCode?

Gracias.

Lucian

Answer 1

Si bien es posible que un Dictionary<TKey,TValue> tenga sus métodos GetValue y similares, llame a Equals en cada clave almacenada para ver si coincide con el que se busca, eso sería muy lento. En cambio, al igual que muchas colecciones basadas en hash, confía en GetHashCode para excluir rápidamente de la consideración la mayoría de los valores que no coinciden. Si se llama a GetHashCode en un artículo que se busca, se obtienen 42, y una colección tiene 53,917 artículos, pero al llamar a GetHashCode en 53,914 de los artículos arrojó un valor distinto a 42, entonces solo se tendrán que comparar 3 artículos con los que se buscan. Los otros 53,914 se pueden ignorar de forma segura.

La razón por la que se incluye un GetHashCode en un IEqualityComparer<T> es para permitir la posibilidad de que el consumidor de un diccionario desee considerar como 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 claves pero usa comparaciones que no distinguen entre mayúsculas y minúsculas. Para hacer que eso funcione de manera eficiente, el diccionario tendrá que tener alguna forma de función hash que produzca el mismo valor para "Fox" y "FOX", pero esperemos que ceda algo más para "caja" o "cebra". Dado que el método GetHashCode integrado en String no funciona de esa manera, el diccionario tendrá que obtener dicho método de otro lugar, e IEqualityComparer<T> es el lugar más lógico ya que la necesidad de dicho código hash estaría muy asociada. con un método Equals que considera "Fox" y "FOX" idénticos entre sí, pero no a "caja" o "cebra".

Answer 2

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 un objeto puede contener, ciertos códigos hash son compartidos por múltiples 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 operaciones de Agregar / Quitar / Obtener. Sin embargo, es una mala opción para iterar. Internamente, un diccionario contiene una matriz de depósitos, donde se pueden almacenar los 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 ingresar la clave. Se llama al método GetHashCode en la clave y se ubica 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 se debe a que está utilizando el operador ^ (operador bitwise exclusive-OR) por lo que 100 ^ 100 cancela dejando cero, al igual que 1000 ^ 1000. Cuando dos objetos diferentes tienen la misma clave, llamamos a eso una colisión.

Cuando agregamos dos pares Clave / Valor con el mismo código hash a un diccionario, ambos se almacenan en el mismo cubo. 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 llamando 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

Entonces, 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 hashcode y salta a esa ubicación. El método Equals es una mejor prueba de igualdad, pero no se puede usar para asignar un objeto a un espacio de direcciones.

Espero que ayude

Answer 3

GetHashCode se utiliza en recopilaciones de diccionario y crea hash para almacenar objetos en él. Este es un buen artículo sobre por qué y cómo usar IEqualtyComparer y GetHashCode http://dotnetperls.com/iequalitycomparer