2010-11-22 15 views
9

¿Está bien para llamar GetHashCode como un método para probar la igualdad desde el interior de los Iguales anulan?Uso GetHashCode para probar la igualdad de los iguales anular

Por ejemplo, ¿es este código aceptable?

public class Class1 
{ 
    public string A 
    { 
    get; 
    set; 
    } 

    public string B 
    { 
    get; 
    set; 
    } 

    public override bool Equals(object obj) 
    { 
    Class1 other = obj as Class1; 
    return other != null && other.GetHashCode() == this.GetHashCode(); 
    } 

    public override int GetHashCode() 
    { 
    int result = 0; 
    result = (result^397)^(A == null ? 0 : A.GetHashCode()); 
    result = (result^397)^(B == null ? 0 : B.GetHashCode()); 
    return result; 
    } 
} 
+2

Como desarrollador, te debes a ti mismo para entender completamente lo que los hashes son Usado para y cómo se relacionan con las tablas hash (según lo implementado por Dictionary y HashSet, entre otros). El artículo de wikipedia para hashtable es un buen comienzo: http://en.wikipedia.org/wiki/Hash_table – spender

+0

@spender: eso es exactamente lo que me ha explicado esta pregunta con más detalle de lo que originalmente entendí o podría recordar. – Armbrat

+2

No solo es incorrecta la comprobación de igualdad, el código es extraño. ¿Por qué multiplicas cero por 397? Puedo decirte en este momento, la respuesta va a ser cero, entonces, ¿por qué hacer que la máquina lo calcule? Por qué xor cero con un valor; esa es una operación de identidad. –

Respuesta

14

Los otros tienen razón; su operación de igualdad está rota. Para ilustrar:

public static void Main() 
{ 
    var c1 = new Class1() { A = "apahaa", B = null }; 
    var c2 = new Class1() { A = "abacaz", B = null }; 
    Console.WriteLine(c1.Equals(c2)); 
} 

Imagino desea que la salida de ese programa que es "falsa", pero con su definición de la igualdad es "verdad" en algunas implementaciones del CLR.

Recuerde, solo hay unos cuatro mil millones de posibles códigos hash. Hay mucho más de cuatro mil millones de posibles cadenas de seis letras, y por lo tanto, al menos dos de ellas tienen el mismo código hash. Les he mostrado a ustedes dos; hay infinitamente más.

En general, puede esperar que si hay n códigos hash posibles, entonces las probabilidades de obtener una colisión aumentan dramáticamente una vez que tenga la raíz cuadrada de n elementos en juego. Esta es la llamada "paradoja del cumpleaños". Para mi artículo sobre por qué no se debe confiar en códigos hash para la igualdad, ver:

http://blogs.msdn.com/b/ericlippert/archive/2010/03/22/socks-birthdays-and-hash-collisions.aspx

6

No, no es aceptable, porque es no

equality <=> hashcode equality.

Es simplemente

equality => hashcode equality.

o en la otra dirección:

hashcode inequality => inequality.

Citando http://msdn.microsoft.com/en-us/library/system.object.gethashcode.aspx:

Si dos objetos comparan como iguales, el método GetHashCode para cada objeto debe devolver el mismo valor. Sin embargo, si dos objetos no se pueden comparar como iguales, los métodos GetHashCode para los dos objetos no tienen que devolver valores diferentes.

1

No, esto no es una forma aceptable para comprobar la igualdad. Es muy posible que 2 valores no iguales tengan el mismo código hash. Esto haría que su implementación de Equals para volver true cuando debería devolver false

2

yo diría, a menos que desee para Equals a significar básicamente "tiene el mismo código hash como" para su tipo, entonces sin, debido a que dos las cadenas pueden ser diferentes pero comparten el mismo código hash. La probabilidad puede ser pequeña, pero no es cero.

1

Puede llamar GetHashCode para determinar si los artículos son no iguales, pero si dos objetos devuelven el mismo código hash, eso no significa que son iguales. Dos elementos pueden tener el mismo código hash pero no ser iguales.

Si es caro para comparar dos elementos, a continuación, puede comparar los códigos hash. Si no son iguales, entonces puedes fianza. De lo contrario (los códigos hash son iguales), debe hacer la comparación completa.

Por ejemplo:

public override bool Equals(object obj) 
    { 
    Class1 other = obj as Class1; 
    if (other == null || other.GetHashCode() != this.GetHashCode()) 
     return false; 
    // the hash codes are the same so you have to do a full object compare. 
    } 
+1

Con muchos objetos, esto tenderá a ser más lento que usar el construido en comparación. Si los objetos son iguales, terminas haciendo una comparación completa * y * un 'GetHashCode'. Si no son iguales, terminas haciendo una llamada a 'GetHashCode', que probablemente se lee en todo el objeto. 'Equals', por otro lado, probablemente solo lea lo suficiente del objeto para determinar que los objetos no son iguales. Dicho esto, en el caso de objetos complicados que son lentos para comparar, pero que tienen un método rápido de 'GetHashCode' (por ejemplo, porque se calcula de antemano), esta optimización ayudará mucho. – Brian

+0

@Brian, estoy de acuerdo en que rara vez es útil por las razones que usted dice. Tampoco creo que el 'preprogramado' GetHashCode' sea a menudo útil (ya que es muy poco utilizado, especialmente si está utilizando una implementación 'IEqualityComparer' en lugar del' GetHashCode' predeterminado). Sin embargo, vea mi respuesta para un caso donde el hecho de que el código hash se almacena de todos modos (por otras razones) puede hacer que el enfoque de Jim tenga sentido. –

1

Usted no podemos decir que sólo porque los códigos hash son iguales, entonces los objetos deben ser iguales.

La única vez que llamaría a GetHashCode dentro de Equals era si fuera mucho más barato calcular un valor hash para un objeto (digamos, porque lo almacena en caché) que para verificar la igualdad. En ese caso, podría decir if (this.GetHashCode() != other.GetHashCode()) return false; para que pueda verificar rápidamente que los objetos no sean iguales.

Entonces, ¿cuándo harías esto?Escribí un código que toma capturas de pantalla en intervalos periódicos e intenta encontrar cuánto tiempo ha pasado desde que cambió la pantalla. Como mis capturas de pantalla son de 8 MB y tienen relativamente pocos píxeles que cambian dentro del intervalo de captura de pantalla, es bastante costoso buscar en una lista de ellos para ver cuáles son iguales. Un valor hash es pequeño y solo debe computarse una vez por captura de pantalla, lo que facilita la eliminación de los que no son conocidos. De hecho, en mi aplicación decidí que tener hashes idénticos era lo suficientemente parecido como para que no me molestara en implementar la sobrecarga Equals, haciendo que el compilador C# me advirtiera que estaba sobrecargando GetHashCode sin sobrecargar Equals.

0

No es un caso en el que usan hashcodes como un acceso directo en las comparaciones de igualdad tiene sentido.

Considere el caso en el que está construyendo una tabla hash o hashset. De hecho, consideremos los hashsets (los hashtables lo extienden manteniendo también un valor, pero eso no es relevante).

Hay varios enfoques diferentes que uno puede tomar, pero en todos ellos tiene un pequeño número de ranuras en los que se pueden colocar los valores hash, y tomamos el enfoque abierto o cerrado (que solo por diversión, algunas personas usar la jerga opuesta para otros); si colisionamos en la misma ranura para dos objetos diferentes, podemos almacenarlos en la misma ranura (pero teniendo una lista vinculada o tal como se almacenan realmente los objetos) o volviendo a explorar para elegir una ranura diferente (hay varios estrategias para esto).

Ahora, con cualquier enfoque, nos alejamos de la complejidad O (1) que queremos con una tabla hash, y hacia una complejidad O (n). El riesgo de esto es inversamente proporcional al número de ranuras disponibles, por lo que después de un cierto tamaño cambiamos el tamaño de la tabla hash (incluso si todo fuera ideal, eventualmente tendríamos que hacer esto si la cantidad de elementos almacenados fuera mayor que la cantidad máquinas tragamonedas).

Volver a insertar los elementos en un cambio de tamaño dependerá obviamente de los códigos hash. Debido a esto, aunque raramente tiene sentido memorizar GetHashCode() en un objeto (simplemente no se llama con la frecuencia suficiente en la mayoría de los objetos), sin duda tiene sentido memorizarlo dentro de la tabla hash misma (o quizás, para memorizar un resultado, por ejemplo, si rehiciste hash con un hash de Wang/Jenkins para reducir el daño causado por malas implementaciones de GetHashCode()).

Ahora, cuando vamos a insertar nuestra lógica va a ser algo así como:

  1. Obtener código hash para el objeto.
  2. Obtener ranura para el objeto.
  3. Si la ranura está vacía, coloque el objeto en ella y vuelva.
  4. Si la ranura contiene el mismo objeto, hemos terminado para un hashset y tenemos la posición para reemplazar el valor de una hashtable. Haz esto y regresa.
  5. Pruebe la siguiente ranura de acuerdo con la estrategia de colisión, y regrese al ítem 3 (tal vez cambiando el tamaño si hacemos un bucle con demasiada frecuencia).

Entonces, en este caso tenemos que obtener el código hash antes de comparar para la igualdad. También tenemos el código hash para los objetos existentes ya precalculados para permitir el cambio de tamaño. La combinación de estos dos hechos significa que tiene sentido para poner en práctica nuestra comparación para el artículo 4 como:

private bool IsMatch(KeyType newItem, KeyType storedItem, int newHash, int oldHash) 
{ 
    return ReferenceEquals(newItem, storedItem) // fast, false negatives, no false positives (only applicable to reference types) 
    || 
    (
     newHash == oldHash // fast, false positives, no fast negatives 
     && 
     _cmp.Equals(newItem, storedItem) // slow for some types, but always correct result. 
    ); 
} 

Obviamente, la ventaja de esto depende de la complejidad de _cmp.Equals. Si nuestro tipo de clave fuera int, esto sería un desperdicio total. Si nuestro tipo de clave fuera string y estuviéramos usando comparaciones de igualdad normalizadas Unicode (por lo que no puede ni atajar en longitud), entonces el ahorro bien podría valer la pena.

En general, recordar los códigos hash no tiene sentido porque no se usan con la suficiente frecuencia como para ganar un rendimiento, pero almacenarlos en el hashset o hashtable en sí puede tener sentido.

0
  1. Es una implementación incorrecta, ya que otros han declarado por qué.

  2. Usted debe cortocircuitar la comprobación de igualdad usando GetHashCode como:

    if (other.GetHashCode() != this.GetHashCode() 
        return false; 
    

    en el Equals método sólo si estás seguro de que la aplicación subsiguiente iguales es mucho más caro que GetHashCode que no es gran mayoría de los casos.

  3. En esta implementación única que ha mostrado (que es el 99% de los casos) no solo está rota, también es mucho más lenta. Y la razón? Calcular el hash de sus propiedades es casi seguro que sea más lento que compararlas, por lo que ni siquiera está ganando en términos de rendimiento. La ventaja de implementar un correcto GetHashCode es cuando su clase puede ser el tipo de clave para las tablas hash, donde el hash se calcula solo una vez (y ese valor se usa para la comparación). En su caso, se llamará GetHashCode varias veces si está en una colección. Aunque GetHashCode en sí mismo debe ser rápido, no es más rápido que equivalenteEquals.

    Para referencia, ejecutar su Equals (una implementación adecuada, sacando la implementación basada en hash de corriente) y GetHashCode aquí

    var watch = Stopwatch.StartNew(); 
    for (int i = 0; i < 100000; i++) 
    { 
        action(); //Equals and GetHashCode called here to test for performance. 
    } 
    watch.Stop(); 
    Console.WriteLine(watch.Elapsed.TotalMilliseconds); 
    
Cuestiones relacionadas