¿Cómo descubre C# el código hash de un objeto?
https://stackoverflow.com/questions/102690
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianPregunta
Esta pregunta surge de la discusión sobre tuplas.
Empecé a pensar en el código hash que debería tener una tupla.¿Qué pasa si aceptamos la clase KeyValuePair como una tupla?No anula el método GetHashCode(), por lo que probablemente no conocerá los códigos hash de sus "hijos"...Entonces, el tiempo de ejecución llamará a Object.GetHashCode(), que no conoce la estructura real del objeto.
Luego podemos crear dos instancias de algún tipo de referencia, que en realidad son iguales, debido a GetHashCode() y Equals() sobrecargados.Y utilizarlos como "hijos" 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 GetHashCode sobrecargado de nuestra clase!
¿Como funciona?¿Cuál es el análisis realizado por Object.GetHashCode()?
¿Puede afectar el rendimiento en algún mal escenario, cuando usamos algunas teclas complicadas?(probablemente, escenario imposible...pero aún)
Considere este código como 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;
}
}
}
Actualizar Creo que encontré una explicación para esto como se indica a continuación en mi respuesta.Los principales resultados del mismo son:
- Tenga cuidado con sus claves y sus códigos hash :-)
- Para claves de diccionario complicadas, debe anular Equals() y GetHashCode() correctamente.
Solución 4
Parece que ahora tengo una pista.
Pensé que KeyValuePair es un tipo de referencia, pero no lo es, es una estructura.Y por eso utiliza el método ValueType.GetHashCode().MSDN porque dice:"Se utilizan uno o más campos del tipo derivado para calcular el valor de retorno".
Si toma un tipo de referencia real como "proveedor de tuplas", engañará al diccionario (o a 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;
}
}
}
Otros consejos
No anule GetHashcode() y Equals() en clases mutables, solo anulelo 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 objetos, usan los objetos clave como identificadores, no es necesario que todas las claves que se usan para agregar entradas en una tabla hash devuelvan códigos hash diferentes, pero se recomienda que lo hagan, de lo contrario el rendimiento sufre mucho.
Aquí están las implementaciones adecuadas de Hash e igualdad para la tupla cuádruple (contiene 4 componentes de tupla en su interior).Este código garantiza el uso adecuado de esta tupla específica en HashSets y los diccionarios.
Más sobre el tema (incluido el código fuente) aquí.
Nota uso de la desenfrenado palabra clave (para evitar desbordamientos) y lanzar NullReferenceException si obj es nulo (como lo requiere 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);
}
Mira esto correo 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 el blog de Ayande. correo.No sé si las versiones actuales del Framework todavía siguen estas reglas o si realmente las han cambiado como insinuó Brad.
Ya no tengo la referencia del libro y tendré que encontrarla solo para confirmar, pero pensé que el hash base predeterminado simplemente agrupaba a todos los miembros de su objeto.Obtuvo acceso a ellos debido a la forma en que funcionaba CLR, por lo que no era algo que se pudiera escribir tan bien como ellos.
Esto es completamente de memoria de algo que leí brevemente, así que tómalo como quieras.
Editar: El libro fue Dentro de C# de MS Press.El que tiene la hoja de sierra en la tapa.El autor dedicó mucho tiempo a explicar cómo se implementaron las cosas en CLR, cómo se tradujo el idioma a MSIL, etc.etc.Si puedes encontrar el libro, no es una mala lectura.
Editar: Forme el enlace proporcionado, parece
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 entero, cuando se crea.Estas claves comienzan en 1 e incrementan cada vez que se crea un nuevo objeto de cualquier tipo.
Hmm, supongo que necesito escribir algunos de mis propios códigos hash, si espero usar objetos como claves hash.
por lo que probablemente no conocerá los códigos hash de sus "hijos".
Su ejemplo parece demostrar lo contrario :-) El código hash de la clave MyClass y el valor 1 es igual para ambos KeyValuePair's .La implementación KeyValuePair debe utilizar tanto su Key y Value por su propio código hash
Avanzando, la clase de diccionario quiere claves únicas.Utiliza el código hash proporcionado por cada clave para resolver las cosas.Recuerde que el tiempo de ejecución no está llamando. Object.GetHashCode(), pero está llamando a la implementación GetHashCode() proporcionada por la instancia que le proporciona.
Consideremos 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, querrás que dos objetos que están a la misma distancia devuelvan "verdadero" para Iguales, pero que devuelvan códigos hash diferentes.
