hashcode c#

¿Por qué C#no implementa GetHashCode para colecciones?

Question

Estoy portando algo de Java a C #. En Java, el hashcode de hashcode de una ArrayList depende de los elementos que ArrayList . En C # siempre obtengo el mismo código hash de una List ...

¿Por qué es esto?

Para algunos de mis objetos, el código hash necesita ser diferente porque los objetos en su propiedad de lista hacen que los objetos no sean iguales. Esperaría que un código hash sea siempre único para el estado del objeto y solo iguale a otro código hash cuando el objeto sea igual. ¿Me equivoco?

Answer 1

Por qué es demasiado filosófico Cree un método auxiliar (puede ser un método de extensión) y calcule el código hash como desee. Pueden ser hashcodes de elementos XOR

Answer 2

Sí, estás equivocado. Tanto en Java como en C #, ser igual implica tener el mismo código hash, pero el inverso no es (necesariamente) verdadero.

Ver GetHashCode para más información.

Answer 3

Solo estás parcialmente equivocado. Definitivamente estás equivocado cuando piensas que hashcodes iguales significa objetos iguales, pero los objetos iguales deben tener códigos hash iguales, lo que significa que si los hashcodes difieren, también lo hacen los objetos.

Answer 4

Para funcionar correctamente, los códigos hash deben ser inmutables: el código hash de un objeto nunca debe cambiar.

Si el código hash de un objeto cambia, cualquier diccionario que contenga el objeto dejará de funcionar.

Como las colecciones no son inmutables, no pueden implementar GetHashCode .
En su lugar, heredan el GetHashCode predeterminado, que devuelve un valor (con suerte) único para cada instancia de un objeto. (Por lo general, basado en una dirección de memoria)

Answer 5

Las razones principales son el rendimiento y la naturaleza humana : las personas tienden a pensar en los hash como algo rápido, pero normalmente requieren atravesar todos los elementos de un objeto al menos una vez.

Ejemplo: si utiliza una cadena como clave en una tabla hash cada consulta tiene una complejidad O (| s |) - use 2 veces cadenas más largas y le costará al menos el doble. Imagine que era un árbol completo (solo una lista de listas) - oops :-)

Si el cálculo de hash completo y profundo fuera una operación estándar en una colección, un enorme porcentaje de programadores simplemente lo usaría inconscientemente y luego culparían al framework y a la máquina virtual por ser lentos. Para algo tan costoso como el cruce completo, es crucial que el programador tenga que estar al tanto de la complejidad. Lo único que se debe lograr es asegurarse de que tiene que escribir el suyo. También es un buen elemento de disuasión :-)

Otra razón es la actualización de tácticas . Cálculo y actualización de un hash sobre la marcha vs hacer el cálculo completo cada vez requiere una llamada de juicio dependiendo del caso concreto en la mano.

La inmutabilidad es solo una salida académica : las personas hacen hashes como una forma de detectar un cambio más rápido (hash de archivos, por ejemplo) y también usan hashes para estructuras complejas que cambian todo el tiempo. Hash tiene muchos más usos entre los 101 básicos. La clave es nuevamente que lo que se debe usar para un hash de un objeto complejo tiene que ser una llamada de juicio caso por caso.

Usar la dirección del objeto (en realidad, un identificador para que no cambie después del GC) como un hash es en realidad el caso en que el valor del hash sigue siendo el mismo para el objeto mutable arbitrario :-) La razón por la que C # lo hace es que es barato y nuevamente empuja a las personas para calcular el suyo

Answer 6

Los códigos de hash deben depender de la definición de igualdad utilizada, de modo que si A == B entonces A.GetHashCode() == B.GetHashCode() (pero no necesariamente el inverso; A.GetHashCode() == B.GetHashCode() hace no implica A == B ).

De forma predeterminada, la definición de igualdad de un tipo de valor se basa en su valor, y de un tipo de referencia se basa en su identidad (es decir, de forma predeterminada, una instancia de un tipo de referencia es igual a sí misma), de ahí el código hash predeterminado para un tipo de valor es tal que depende de los valores de los campos que contiene * y para los tipos de referencia depende de la identidad. De hecho, dado que idealmente queremos que los códigos hash para objetos no iguales sean diferentes, particularmente en los bits de bajo orden (lo más probable es que afecte el valor de un re-hashing), generalmente queremos dos objetos equivalentes pero no iguales para tener diferentes hashes.

Como un objeto permanecerá igual a sí mismo, también debe quedar claro que esta implementación predeterminada de GetHashCode() seguirá teniendo el mismo valor, incluso cuando el objeto esté mutado (la identidad no cambia incluso para un objeto mutable).

Ahora, en algunos casos, los tipos de referencia (o tipos de valores) redefinen la igualdad. Un ejemplo de esto es una cadena, donde por ejemplo "ABC" == "AB" + "C" . Aunque hay dos ejemplos diferentes de cadenas comparadas, se consideran iguales. En este caso, se debe anular GetHashCode() para que el valor se relacione con el estado en el que se define la igualdad (en este caso, la secuencia de caracteres contenida).

Si bien es más común hacer esto con tipos que también son inmutables, por una variedad de razones, GetHashCode() no depende de la inmutabilidad . Más bien, GetHashCode() debe permanecer constante frente a la mutabilidad: cambie un valor que usemos para determinar el hash, y el hash debe cambiar en consecuencia. Sin embargo, tenga en cuenta que esto es un problema si utilizamos este objeto mutable como clave en una estructura que utiliza el hash, ya que mutar el objeto cambia la posición en la que debería almacenarse, sin moverlo a esa posición (también es cierto para cualquier otro caso en el que la posición de un objeto dentro de una colección dependa de su valor; por ejemplo, si ordenamos una lista y luego muteamos uno de los elementos de la lista, la lista ya no se clasifica). Sin embargo, esto no significa que solo debemos usar objetos inmutables en diccionarios y hashsets. Más bien significa que no debemos mutar un objeto que se encuentra en tal estructura, y hacerlo inmutable es una forma clara de garantizar esto.

De hecho, hay bastantes casos donde es deseable almacenar objetos mutables en tales estructuras, y mientras no los mutemos durante este tiempo, esto está bien. Dado que no tenemos la garantía de que la inmutabilidad trae, entonces queremos proporcionarlo de otra manera (por ejemplo, pasar un corto tiempo en la colección y ser accesible desde un solo hilo).

Por lo tanto, la inmutabilidad de los valores clave es uno de esos casos en los que algo es posible, pero en general es una idea. Sin embargo, para la persona que define el algoritmo de código hash, no les corresponde suponer que ese caso siempre será una mala idea (ni siquiera saben que la mutación ocurrió mientras el objeto estaba almacenado en dicha estructura); es para ellos implementar un hashcode definido en el estado actual del objeto, ya sea que lo llames en un punto dado sea bueno o no. Por lo tanto, por ejemplo, un código hash no se debe recordar en un objeto mutable a menos que la memorización se borre en cada mutación. (En general, es un desperdicio memorizar los hashes de todos modos, ya que las estructuras que golpean los mismos objetos hashcode repetidamente tendrán su propia memoria).

Ahora, en el caso que nos ocupa, ArrayList opera en el caso predeterminado de igualdad basada en la identidad, por ejemplo:

ArrayList a = new ArrayList();
ArrayList b = new ArrayList();
for(int i = 0; i != 10; ++i)
{
a.Add(i);
b.Add(i);
}
return a == b;//returns false

Ahora, esto es realmente algo bueno. ¿Por qué? Bueno, ¿cómo sabes en lo anterior que queremos considerar un igual a b? Podríamos, pero hay muchas buenas razones para no hacerlo en otros casos también.

Además, es mucho más fácil redefinir la igualdad de la basada en la identidad a la basada en el valor, que de la basada en el valor a la basada en la identidad. Finalmente, hay más de una definición de igualdad basada en valores para muchos objetos (el caso clásico son las diferentes vistas sobre lo que hace que una cadena sea igual), por lo que ni siquiera existe una definición única que funcione. Por ejemplo:

ArrayList c = new ArrayList();
for(short i = 0; i != 10; ++i)
{
c.Add(i);
}

Si consideramos a == b arriba, ¿deberíamos considerar a == c aslo? La respuesta depende de lo que nos importa en la definición de igualdad que estamos usando, por lo que el marco no podría saber cuál es la respuesta correcta para todos los casos, ya que todos los casos no concuerdan.

Ahora, si nos importa la igualdad basada en el valor en un caso dado, tenemos dos opciones muy sencillas. El primero es subclasificar y anular la igualdad:

public class ValueEqualList : ArrayList, IEquatable<ValueEqualList>
{
/*.. most methods left out ..*/
public Equals(ValueEqualList other)//optional but a good idea almost always when we redefine equality
{
if(other == null)
return false;
if(ReferenceEquals(this, other))//identity still entails equality, so this is a good shortcut
return true;
if(Count != other.Count)
return false;
for(int i = 0; i != Count; ++i)
if(this[i] != other[i])
return false;
return true;
}
public override bool Equals(object other)
{
return Equals(other as ValueEqualList);
}
public override int GetHashCode()
{
int res = 0x2D2816FE;
foreach(var item in this)
{
res = res * 31 + (item == null ? 0 : item.GetHashCode());
}
return res;
}
}

Esto supone que siempre querremos tratar tales listas de esta manera. También podemos implementar un IEqualityComparer para un caso dado:

public class ArrayListEqComp : IEqualityComparer<ArrayList>
{//we might also implement the non-generic IEqualityComparer, omitted for brevity
public bool Equals(ArrayList x, ArrayList y)
{
if(ReferenceEquals(x, y))
return true;
if(x == null || y == null || x.Count != y.Count)
return false;
for(int i = 0; i != x.Count; ++i)
if(x[i] != y[i])
return false;
return true;
}
public int GetHashCode(ArrayList obj)
{
int res = 0x2D2816FE;
foreach(var item in obj)
{
res = res * 31 + (item == null ? 0 : item.GetHashCode());
}
return res;
}
}

En resumen:

1. La definición de igualdad predeterminada de un tipo de referencia depende de la identidad sola.
2. La mayoría de las veces, queremos eso.
3. Cuando la persona que define la clase decide que esto no es lo que se quiere, pueden anular este comportamiento.
4. Cuando la persona que usa la clase quiere una definición diferente de igualdad otra vez, puede usar IEqualityComparer<T> y IEqualityComparer para que sus diccionarios, hashmaps, hashsets, etc. usen su concepto de igualdad.
5. Es desastroso mutar un objeto mientras es la clave de una estructura basada en hash. La inmutabilidad se puede utilizar para garantizar que esto no ocurra, pero no es obligatorio, ni siempre es deseable.

Con todo, el marco nos brinda buenos incumplimientos y posibilidades detalladas de anulación.

* Hay un error en el caso de un decimal dentro de una estructura, porque hay un atajo usado en algunos casos con estuches cuando es seguro y no en otras ocasiones, pero mientras que una estructura que contiene un decimal es un caso cuando el short- el corte no es seguro, se identifica incorrectamente como un caso en el que es seguro.

Answer 7

No es posible que un código hash sea único en todas las variaciones de la mayoría de las clases no triviales. En C #, el concepto de igualdad de listas no es el mismo que en Java (ver aquí ), por lo que la implementación del código hash tampoco es la misma: refleja la igualdad de la lista C #.