c# - studio - Object.GetHashCode
hash string c# (3)
Mi pregunta puede duplicar la implementación predeterminada para Object.GetHashCode () pero lo pregunto nuevamente porque no entendí la respuesta aceptada a esa.
Para empezar, tengo tres preguntas sobre la respuesta aceptada a la pregunta anterior , que cita algunos documentos de la siguiente manera:
"Sin embargo, dado que este índice se puede reutilizar después de que el objeto se reclame durante la recolección de basura, es posible obtener el mismo código hash para dos objetos diferentes".
¿Es esto cierto? Me parece que dos objetos no tendrán el mismo código hash, porque el código de un objeto no se reutiliza hasta que el objeto se recolecta como basura (es decir, ya no existe).
"Además, dos objetos que representan el mismo valor tienen el mismo código hash solo si son exactamente el mismo objeto".
¿Es esto un problema? Por ejemplo, quiero asociar algunos datos con cada una de las instancias de nodo en un árbol DOM. Para hacer esto, los ''nodos'' deben tener una identidad o un código hash, de modo que pueda usarlos como claves en un diccionario de datos. ¿No es un código hash el que identifica si es "exactamente el mismo objeto", es decir, "igualdad de referencia en lugar de" igualdad de valor ", lo que quiero?
"Esta implementación no es particularmente útil para el hashing; por lo tanto, las clases derivadas deben reemplazar a GetHashCode"
¿Es esto cierto? Si no es bueno para el hash, entonces ¿para qué sirve para algo, y por qué incluso se define como un método de Objeto?
Mi última pregunta (y quizás la más importante para mí) es: si debo inventar / anular una implementación de GetHashCode () para un tipo arbitrario que tenga una semántica de "igualdad de referencia", la siguiente es una implementación razonable y buena:
class SomeType
{
//create a new value for each instance
static int s_allocated = 0;
//value associated with this instance
int m_allocated;
//more instance data
... plus other data members ...
//constructor
SomeType()
{
allocated = ++s_allocated;
}
//override GetHashCode
public override int GetHashCode()
{
return m_allocated;
}
}
Editar
Para tu información lo probé, usando el siguiente código:
class TestGetHash
{
//default implementation
class First
{
int m_x;
}
//my implementation
class Second
{
static int s_allocated = 0;
int m_allocated;
int m_x;
public Second()
{
m_allocated = ++s_allocated;
}
public override int GetHashCode()
{
return m_allocated;
}
}
//stupid worst-case implementation
class Third
{
int m_x;
public override int GetHashCode()
{
return 0;
}
}
internal static void test()
{
testT<First>(100, 1000);
testT<First>(1000, 100);
testT<Second>(100, 1000);
testT<Second>(1000, 100);
testT<Third>(100, 100);
testT<Third>(1000, 10);
}
static void testT<T>(int objects, int iterations)
where T : new()
{
System.Diagnostics.Stopwatch stopWatch =
System.Diagnostics.Stopwatch.StartNew();
for (int i = 0; i < iterations; ++i)
{
Dictionary<T, object> dictionary = new Dictionary<T, object>();
for (int j = 0; j < objects; ++j)
{
T t = new T();
dictionary.Add(t, null);
}
for (int k = 0; k < 100; ++k)
{
foreach (T t in dictionary.Keys)
{
object o = dictionary[t];
}
}
}
stopWatch.Stop();
string stopwatchMessage = string.Format(
"Stopwatch: {0} type, {1} objects, {2} iterations, {3} msec",
typeof(T).Name, objects, iterations,
stopWatch.ElapsedMilliseconds);
System.Console.WriteLine(stopwatchMessage);
}
}
En mi máquina los resultados / resultados son los siguientes:
First type, 100 objects, 1000 iterations, 2072 msec
First type, 1000 objects, 100 iterations, 2098 msec
Second type, 100 objects, 1000 iterations, 1300 msec
Second type, 1000 objects, 100 iterations, 1319 msec
Third type, 100 objects, 100 iterations, 1487 msec
Third type, 1000 objects, 10 iterations, 13754 msec
Mi implementación toma la mitad del tiempo de la implementación predeterminada (pero mi tipo es más grande por el tamaño de mi miembro de datos m_allocated).
Mi implementación y la implementación predeterminada se escalan linealmente.
En comparación y como una comprobación de cordura, la implementación estúpida comienza mal y se empeora.
En realidad, no es necesario modificar nada en una clase que solo requiere igualdad de referencia .
Además, formalmente, esa no es una buena implementación ya que tiene una distribución deficiente. Una función hash debe tener una distribución razonable, ya que mejora la distribución del grupo hash, e indirectamente, el rendimiento en colecciones que utilizan tablas hash. Como dije, esa es una respuesta formal , una de las pautas al diseñar una función hash.
La propiedad más importante que debe tener una implementación de código hash es esta:
Si dos objetos se comparan como iguales, entonces deben tener códigos hash idénticos.
Si tiene una clase en la que las instancias de la clase se comparan por igualdad de referencia, entonces no necesita anular GetHashCode; la implementación predeterminada garantiza que dos objetos que son la misma referencia tienen el mismo código hash. (Está llamando al mismo método dos veces en el mismo objeto, por lo que, por supuesto, el resultado es el mismo).
Si ha escrito una clase que implementa su propia igualdad que es diferente de la igualdad de referencia, se LE REQUIERE que invalide GetHashCode de manera que dos objetos que se comparan como iguales tengan códigos hash iguales.
Ahora, puedes hacerlo simplemente devolviendo cero cada vez. Esa sería una pésima función hash, pero sería legal.
Otras propiedades de las buenas funciones de hash son:
GetHashCode nunca debe lanzar una excepción
Los objetos mutables que comparan la igualdad en su estado mutable, y por lo tanto el hash en su estado mutable, son peligrosamente propensos a los errores. Puede poner un objeto en una tabla hash, mutarlo y no poder volver a sacarlo. Trate de nunca juntar o comparar la igualdad en un estado mutable.
GetHashCode debería ser extremadamente rápido: recuerde, el propósito de un buen algoritmo hash es mejorar el rendimiento de las búsquedas. Si el hash es lento, entonces las búsquedas no se pueden hacer rápido.
Los objetos que no se comparan como iguales deben tener códigos hash diferentes, bien distribuidos en todo el rango de un entero de 32 bits.
Pregunta:
¿Es esto cierto? Me parece que dos objetos no tendrán el mismo código hash, porque el código de un objeto no se reutiliza hasta que el objeto se recolecta como basura (es decir, ya no existe).
Dos objetos pueden compartir el mismo código hash, si se genera de forma predeterminada en la implementación de GetHashCode, porque:
- El resultado predeterminado de GetHashCode no debe cambiarse durante la vida útil del objeto , y la implementación predeterminada lo garantiza. Si pudiera cambiar, tipos como Hashtable no podrían manejar esta implementación. Esto se debe a que se espera que el código hash predeterminado sea un código hash de identificador único de instancia (incluso aunque no exista tal identificador :)).
- El rango de valores de GetHashCode es rango de entero (2 ^ 32).
Conclusión: es suficiente para asignar 2 ^ 32 objetos con referencias fuertes (debe ser fácil en Win64) para alcanzar el límite.
Finalmente, hay una declaración explícita en la referencia object.GetHashCode en MSDN : La implementación predeterminada del método GetHashCode no garantiza valores de retorno únicos para diferentes objetos. Además, .NET Framework no garantiza la implementación predeterminada del método GetHashCode, y el valor que devuelve será el mismo entre las diferentes versiones de .NET Framework. En consecuencia, la implementación predeterminada de este método no debe utilizarse como un identificador de objeto único para fines de hashing.