¿Esta función hash colisionará inusualmente con frecuencia?

Question

que tenían el siguiente código para generar un hash de un objeto:

public int GetHashCode(MyType obj) 
{ 
    return (obj.Prop1.GetHashCode() + obj.Prop2.GetHashCode() + obj.Prop3.GetHashCode()).GetHashCode(); 
} 

es decir, Agrego todos los códigos hash de propiedades y luego tomo el hash de esto.

En revisión, un compañero de trabajo sugirió que esto colisionaría con demasiada frecuencia. No estoy seguro de que esto es verdad porque:

1. Dado que los códigos hash se eligen con la misma frecuencia entre los números positivos y negativos y se envuelven alrededor, no creo que haya ninguna información adicional que obtenemos acerca de la probabilidad de la suma de estos números en oposición a los números
2. En la medida en que su suma no es aleatoria, los códigos hash están diseñados para hacer que los números que están "muy juntos" se vuelvan "muy separados", por lo que alimentan de forma no uniforme -el valor distribuido en la función no debería ser un problema

¿Quién es correcto?

Está en C#, en caso de que la respuesta sea específica del idioma.

Answer 1

Sí.

Solo suponga que Prop1, Prop2 etc. son del tipo int. Por lo general, solo se utiliza el rango inferior de enteros. Su enfoque suma colisionará más a menudo de lo necesario.

El HasCode de 7 es 7, lo que tiene mucho sentido cuando hash int por sí mismo. Pero con su código, las tuplas <7, 3>, <3, 7> y <8, 2> tendrán el mismo Hash. Lo mismo con XOR simple en lugar de Addition.

El enfoque común es añadir algunos números (prime) y desplazamiento:

public int GetHashCode(MyType obj) 
{ 
    int hash = 0; 
    unchecked 
    {   
    hash += 19 * obj.Prop1.GetHashCode(); 
    hash += 31 * obj.Prop2.GetHashCode(); 
    hash += 37 * obj.Prop3.GetHashCode(); 
    } 
    return hash; 
} 

Los números 19, 31, 37 no son demasiado crítico. Y si lo prefiere, puede usar O o XOR en lugar de +.

Answer 2

XORing sería mejor:

public int GetHashCode(MyType obj) 
{ 
    return obj.Prop1.GetHashCode()^
      obj.Prop2.GetHashCode()^
      obj.Prop3.GetHashCode(); 
} 

Answer 3

Se puede utilizar un generador de FNV HashCode modificado, una pregunta muy similar ha sido contestada (por mí) here