Equals, == y GetHashCode en C# (y 2)

(la primera parte puede leerse aquí)El método GetHashCode es un método peculiar cuando no se conoce. La primera vez que lo vi pensé que representaba un identificador único de cada instancia y que me serviría para reconocer si dos instancias eran la misma (me llegué a plantear si era la dirección en memoria donde se almacenaba el objeto!). Pero una visita a la Wikipedia saca a de la duda:

Hash functions are primarily used to generate fixed-length output data that acts as a shortened reference to the original data. This is useful when the output data is too cumbersome to use in its entirety.

Aunque la resumo aquí, es recomendable leer la documentación oficial en MSDN. Desde el punto de vista práctico hay que señalar el párrafo incial:

A hash code is a numeric value that is used to insert and identify an object in a hash-based collection such as the Dictionary<TKey, TValue> class, the Hashtable class, or a type derived from the DictionaryBase class

Esto significa que nuestro código Hash se usará en los diccionarios y otras colecciones similares. También se usa internamente en operadores LINQ por motivos de eficiencia. Centrándonos en su uso en un diccionario, por ejemplo, éste se compone de varios ‘bucket’. Cuando añadimos una clave, se solicita el valor hash llamando a GetHashCode. Si no existe el bucket para dicho valor, se crea y se almacena en él el par clave-valor. Si varias claves devuelven el mismo hash se produce lo que se denomina ‘colisión’ y se resuelve almacenando en el mismo bucket varios pares.

En el momento que se solicita un valor a partir de una clave basta con calcular el hash de la clave solicitada, localizar el bucket de dicho hash y (esto es importante) comparar la clave solicitada con la(s) clave(s) almacenadas en el bucket. Dado que la igualdad es diferente según la programemos y que depende de si se trata de una tipo por referencia o por valor, el resultado de la búsqueda puede variar. De ahí que la documentación de Dictionary<>  aconseje:

Dictionary<TKey, TValue> requires an equality implementation to determine whether keys are equal. You can specify an implementation of the IEqualityComparer generic interface by using a constructor that accepts a comparer parameter; if you do not specify an implementation, the default generic equality comparer EqualityComparer.Default is used. If type TKey implements the System.IEquatable generic interface, the default equality comparer uses that implementation.

photo credit: mikecogh via photopin cc

photo credit: mikecogh via photopin cc

Por lo tanto, si dos objetos son iguales, su función hash debería devolver el mismo valor. Lo contrario no es cierto: si dos objetos devuelven el mismo valor hash, ello no implica que sean iguales. Además, el método GetHashCode deberá devolver el mismo valor. Dado que su valor depende del estado del objeto, cuando cambia el estado también cambia el valor hash. Esto último tiene efectos colaterales que debemos tener en cuenta.

En el ejemplo una estructura tiene un hascode que depende directamente del valor de su única propiedad. Si agregamos una clave con hash =9 y luego buscamos mediante otra instancia con el mismo hash el diccionario nos indicará que la clave ya está presente en el diccionario. Sin embargo, si cambiamos el hash de la clave inicial ya presente en el diccionario y luego buscamos mediante otra instancia con la misma nueva clave, nos dirá que no existe.

void Main()
{
	Dictionary<FooClass, object> Dict = new Dictionary<FooClass, object>();
	FooClass fooInstance = new FooClass(9);
	Dict.Add (fooInstance, null);
	Console.WriteLine("Primera búsqueda, la clave se encontró?: " + Dict.ContainsKey(fooInstance));
	Console.WriteLine("Buscamos un key con el mismo hashcode que el existente, la clave se encontró?: " +Dict.ContainsKey(new FooClass(9)));
	fooInstance.Id=10;
	Console.WriteLine("Cambianos el hashcode, la clave se encontró?: " +Dict.ContainsKey(fooInstance));
}

public struct FooClass {
	int _Id;
	public FooClass (int id) {
		_Id=id;
	}
	public int Id {
		set {
			_Id=value;
		}
		get{
			return _Id;
		}
	}
	public override int GetHashCode() {
		return _Id;
	}
}
// Resultado:
// Primera búsqueda, la clave se encontró?: True
// Buscamos un key con el mismo hashcode que el existente, la clave se encontró?: True
// Cambianos el hashcode, la clave se encontró?: False

Si en vez de una estructura FooClass fuese una clase la segunda respuesta sería False, proque aunque tienen el mismo hash al comparar mediante la igualdad se haría por referencia y claramente FooClass(9) != FooClass(9)

Una vez vista la utilidad de GetHashCode, veamos algunas características. Lo primero que hay que asumir es que es complicado escribir una funcion Hash que sea a la vez eficiente y cumpla las propiedades que se esperan de ella. Desde un punto de vista más concreto y centrándonos en su implementación en .NET:

  • Es importante que su ejecución sea rápida.
  • Para que el valor sea único y dependiente del estado, la función debería depende de al menos uno de los campos de instancia.
  • El código hash no debería calcularse usando valores de campos estáticos. (pueden ser cambiados por otras instancias sin nuestro conocimiento)
  • En clases que derivan de Object, el método puede delegar en Object.GetHasCode() sólamente si el Equals de la clase derivada se basa en la igualdad de referencias.
  • Para su uso sea eficiente, la funcion hash debería generar una distribución uniforme, incluso para objetos muy similares. Es decir, un pequeño cambio en el estado del objeto debería implicar un cambio grande en el resultado de la función Hash.
  • No debería lanzar excepciones.

Satisfacer todas estas características dista de ser trivial y estudiar las posibilidades excede la intención de este post. Un método que se suele emplear es usar la el operador XOR con todas los campos que definen el estado del objeto, aunque no es recomendable, sobre todo si hay mucha información redundante:

"a".GetHashCode() ^ "a".GetHashCode() == "b".GetHashCode() ^ "b".GetHashCode())

Un algoritmo mas conveniente es el mostrado en respuesta de StackOverflow:

public override int GetHashCode()
{
    unchecked // Overflow is fine, just wrap
    {
        int hash = 17;
        // Suitable nullity checks etc, of course 🙂
        hash = hash * 23 + field1.GetHashCode();
        hash = hash * 23 + field2.GetHashCode();
        hash = hash * 23 + field3.GetHashCode();
        return hash;
    }
}

Resharper, por ejemplo, genera un código similar al anterior donde mezcla ambos conceptos:

public override int GetHashCode() {
	unchecked {
		int hashCode = _Id;
		hashCode = (hashCode * 397) ^ (_Bar != null ? _Bar.GetHashCode() : 0);
		return hashCode;
	}
}

Aunque los algoritmos mencionados no varian con el tiempo, la documentación especifica claramente que no siempre es así y que puede variar con el tiempo, la versión del famework o el dominio donde fue generado, así que no se debe usar fuera de dichos ámbitos ni almacenar para su uso posterior.

¿Cómo se relacionan GetHashCode, Equals y ==?  Microsoft recomienda:

  • Sobreescribe Equals() si necesitas igualdad semántica en objectos
  • Sobreescribe Equals as implementar IComparable (planteate sobrecargar también ==, !=, <, >)
  • Sobreescribe Equals si implementas el operador == para mantenerlos sincronizados. En Visual Studio 2013 las reglas CA1815 y CA2224 avisan de la falta de dicha sincronización.
  • Al sobreescribir el método de instancia Equals (object) en una clase es buena idea implementar IEquatable
  • Las struct deberían sobreescribir Equals(object) para mejorar el desempeño
  • Implementar GetHashCode siempre que se implemement Equals. La configuración por defecto del compilador te avisará de cuando no lo haces mediante warnings CS0660  y CS0661
  • Si vas a usar un tipo por valor como clave de un diccionario o similar, deberías implementar GetHashCode por eficiencia.
  • Si la clase o o estructura va a ser usada como clave en un diccionario, haz que sea inmutable.

Lecturas suplementarias

Capítulo 11: Modelos de diseño comunes, Implementar el método Equals (.Net 2.0)

Implementar el método Equals (.Net 4)

Guidelines and rules for GetHashCode en Eric Lippert’s Blog

Algoritmos de cálculo de valores hash

Wagner, Bill. “Item 6 Y 7.” Effective C♯: 50 Specific Ways to Improve Your C♯.  2nd ed. Addison-Wesley, 2010

Anuncios
Tagged with: , ,
Publicado en Programacion

Deixa a túa opinión

Introduce tus datos o haz clic en un icono para iniciar sesión:

Logo de WordPress.com

Estás comentando usando tu cuenta de WordPress.com. Cerrar sesión / Cambiar )

Imagen de Twitter

Estás comentando usando tu cuenta de Twitter. Cerrar sesión / Cambiar )

Foto de Facebook

Estás comentando usando tu cuenta de Facebook. Cerrar sesión / Cambiar )

Google+ photo

Estás comentando usando tu cuenta de Google+. Cerrar sesión / Cambiar )

Conectando a %s

A %d blogueros les gusta esto: