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

Question

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

El ejemplo siguiente 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 el método es igual a la implementación sea suficiente para comparar dos objetos caja? Ahí es donde le decimos al marco de la regla utilizada para comparar los objetos. ¿Por qué es necesaria la GetHashCode?

Gracias.

Lucian

Answer 1

Un poco de historia primero ...

Cada objeto en .NET ha un método equals y un método GetHashCode.

El método equals se utiliza 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. Puesto que no hay límite a la cantidad de información que un objeto puede contener, ciertos códigos hash son compartidos por varios objetos - por lo que el código hash no es necesariamente única.

Un diccionario es un muy enfriar estructura de datos que se negocia un mayor consumo de memoria a cambio de (más o menos) los costos constantes para añadir / quitar / Get operaciones. Es una mala elección para una iteración sin embargo. Internamente, un diccionario contiene una matriz de cubos, donde se pueden guardar valores. Cuando se agrega una clave y un valor a un diccionario, el método GetHashCode se llama en la tecla. El código hash devuelto se utiliza para determinar el índice de la cubeta en la que el par clave / valor debe ser almacenado.

Cuando se desea acceder al valor, se pasa en la tecla de nuevo. El método GetHashCode se llama en la tecla, y el cubo que contiene el valor se encuentra.

Cuando un IEqualityComparer se pasa en el constructor de un diccionario, los IEqualityComparer.Equals y métodos IEqualityComparer.GetHashCode se utilizan en lugar de los métodos en los objetos clave.

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

Utilizando el método BoxEqualityComparer.GetHashCode en su ejemplo, tanto de estas cajas tienen el mismo código hash - 100 ^ 100 ^ 25 = 1000 ^ 1000 ^ 25 = 25 - a pesar de que claramente no son el mismo objeto. La razón de que son el mismo código hash en este caso es porque está utilizando el operador ^ (O exclusivo bit a bit) para 100 ^ 100 anula dejando cero, al igual que 1000 ^ 1000. Cuando dos objetos diferentes tienen la misma clave, llamamos a que una colisión.

Cuando añadimos dos pares clave / valor con el mismo código hash de un diccionario, ambos están almacenados en el mismo cubo. Así que cuando queremos recuperar un valor, el método GetHashCode se llama en nuestra clave para localizar el cubo. Dado que hay más de un valor en el cubo, se repite el diccionario más de todos los pares clave / valor en el cubo de llamar al método Equals en las claves para encontrar la correcta.

En el ejemplo que usted envió, las dos cajas son equivalentes, por lo que los iguales devuelve el método verdadera. En este caso, el diccionario tiene dos llaves idénticas, por lo que se produce una excepción.

TLDR

Así que en resumen, el método GetHashCode se utiliza para generar una dirección donde se almacena el objeto. Así que 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 la igualdad, pero no se puede utilizar para asignar un objeto en un espacio de direcciones.

Espero que ayude

Answer 2

GetHashCode se utiliza en el diccionario de colections y crea hash para almacenar objetos en ella. Aquí es un buen artículo por qué y cómo el uso IEqualtyComparer y GetHashCode http: //dotnetperls.com/iequalitycomparer

Answer 3

Si bien sería posible para un Dictionary<TKey,TValue> tenga su GetValue y métodos similares llamar Equals en cada clave almacenada solo para ver si coincide con el que se busca, eso sería muy lento. En cambio, al igual que muchas colecciones basado en hash, que se basa en GetHashCode excluir rápidamente la mayoría de los valores no coincidentes de la consideración. Si llama GetHashCode en un elemento que se busca rendimientos de 42, y una colección cuenta con 53,917 elementos, pero llamar GetHashCode en 53.914 de los artículos cedido un valor distinto de 42, entonces sólo 3 artículos tendrán que ser comparado con los que se buscan. El otro 53 914 puede ser ignorado con seguridad.

La razón un GetHashCode se incluye en una IEqualityComparer<T> es permitir la posibilidad de que un diccionario del consumidor podría querer considerar como objetos iguales que normalmente no considerarían entre sí como iguales. El ejemplo más común sería una persona que llama que quiere utilizar cadenas como claves, pero las comparaciones entre mayúsculas y minúsculas uso. Con el fin de hacer que funcione de manera eficiente, el diccionario tendrá que tener algún tipo de función hash que produzca el mismo valor para "Fox" y "FOX", pero esperemos que ceder algo más de "caja" o "cebra". Dado que el método GetHashCode integrado en String no funciona de esa manera, el diccionario se necesita para obtener un procedimiento de este tipo desde otro lugar, y IEqualityComparer<T> es el lugar más lógico ya que la necesidad de un código de este tipo de hash sería muy fuertemente asociada con un Equals método que considera "Fox" y "FOX" idénticos entre sí, pero no a "caja" o "cebra".