C # ¿Cómo seleccionar un Hashcode para una clase que viola el contrato de Equals?

Question

Tengo varias clases que, por ciertas razones, no siguen el contrato oficial Equals . En el GetHashCode () sobrescrito estas clases simplemente devuelven 0 para que puedan usarse en un Hashmap.

Algunas de estas clases implementan la misma interfaz y hay Hashmaps que usan esta interfaz como clave. Así que pensé que cada clase debería al menos devolver un valor diferente (pero aún constante) en GetHashCode () .

La pregunta es cómo seleccionar este valor. ¿Debo simplemente dejar que la primera clase devuelva 1, la siguiente clase 2 y así sucesivamente? ¿O debería intentar algo como

class SomeClass : SomeInterface {
    public overwrite int GetHashCode() {
        return "SomeClass".GetHashCode();
    }
}

¿entonces el hash se distribuye de manera más uniforme? (¿Tengo que guardar en caché el valor devuelto o el compilador de Microsoft puede optimizar esto?)

Actualización: No es posible devolver un código hash individual para cada objeto, porque Equals viola el contrato. Específicamente, me refiero a este problema .

Answer 1

Me encontré con este problema exacto al escribir una clase de vectores. Quería comparar vectores para la igualdad, pero las operaciones de flotación dan errores de redondeo, por lo que quería una igualdad aproximada. Para resumir, anular iguales es una mala idea a menos que su implementación sea simétrica, reflexiva y transitiva.

Otras clases van a asumir que igual tiene esas propiedades, y también lo harán las clases que usan esas clases, por lo que puede terminar en casos extraños. Por ejemplo, una lista puede imponer unicidad, pero termina con dos elementos que se evalúan como iguales a algún elemento B.

Una tabla hash es el ejemplo perfecto de comportamiento impredecible cuando se rompe la igualdad. Por ejemplo:

//Assume a == b, b == c, but a != c
var T = new Dictionary<YourType, int>()
T[a] = 0
T[c] = 1
return T[b] //0 or 1? who knows!

Otro ejemplo sería un Set:

//Assume a == b, b == c, but a != c
var T = new HashSet<YourType>()
T.Add(a)
T.Add(c)
if (T.contains(b)) then T.remove(b)
//surely T can't contain b anymore! I sure hope no one breaks the properties of equality!
if (T.contains(b)) then throw new Exception()

Sugiero usar otro método, con un nombre como ApproxEquals. También puede considerar anular el operador ==, porque no es virtual y, por lo tanto, no será utilizado accidentalmente por otras clases como podría ser Equals.

Si realmente no puede utilizar la igualdad de referencia para la tabla hash, no arruine el rendimiento de los casos en los que puede hacerlo. Agregue una interfaz IApproxEquals, impleméntela en su clase y agregue un método de extensión GetApprox al Diccionario que enumera las claves que buscan una aproximadamente igual y devuelve el valor asociado. También podría escribir un diccionario personalizado especialmente para vectores tridimensionales, o lo que necesite.

Answer 2

Si '' viola el contrato de Equals '', entonces no estoy seguro de que deba usarlo como clave.

Si algo está usando eso como clave, realmente necesitas acertar con el hashing ... no está muy claro cuál es la lógica Equals , pero dos valores que se consideran iguales debe tener el mismo código hash. No es necesario que dos valores con el mismo código hash sean iguales.

El uso de una cadena constante realmente no ayudará mucho: obtendrá los valores divididos de manera uniforme sobre los tipos, pero eso es todo ...

Answer 3

Tengo curiosidad sobre cuál sería el razonamiento para anular GetHashCode () y devolver un valor constante. ¿Por qué violar la idea de un hash en lugar de simplemente violar el "contrato"? y no anular la función GetHashCode () en absoluto y dejar la implementación predeterminada de Object ?

Editar

Si lo que ha hecho es que puede hacer que sus objetos coincidan en función de su contenido en lugar de su referencia, entonces lo que propone con diferentes clases simplemente usar diferentes constantes puede FUNCIONAR, pero es muy ineficiente. Lo que desea hacer es crear un algoritmo de hash que pueda tomar el contenido de su clase y producir un valor que equilibre la velocidad con una distribución uniforme (eso es el hashing 101).

Supongo que no estoy seguro de lo que estás buscando ... no hay un "bueno" esquema para elegir números constantes para este paradigma. Uno no es mejor que el otro. Intenta mejorar tus objetos para crear un hash real.

Answer 4

Cuando se producen colisiones hash, HashTable / Dictionary llama a Equals para encontrar la clave que está buscando. El uso de un código hash constante elimina las ventajas de velocidad de usar un hash en primer lugar: se convierte en una búsqueda lineal.

Estás diciendo que el método Equals no se ha implementado de acuerdo con el contrato. ¿Qué quieres decir exactamente con esto? Dependiendo del tipo de violación, HashTable o Dictionary simplemente serán lentos (búsqueda lineal) o no funcionarán en absoluto.