Crear un hashcode de dos números

Question

Estoy tratando de crear una función rápida de hashcode para una clase de número complejo (a + b) en C#.

He visto repetidamente el método a.GetHashcode()^b.GetHashCode(). Pero esto dará el mismo código hash para (a,b) y (b,a).

¿Hay algún algoritmo estándar para hacer esto y hay alguna función en el marco .Net para ayudar?

Answer 1

Mi forma habitual de crear un código hash para un conjunto arbitrario de elementos hashable:

int hash = 23; 
hash = hash * 31 + item1Hash; 
hash = hash * 31 + item2Hash; 
hash = hash * 31 + item3Hash; 
hash = hash * 31 + item4Hash; 
hash = hash * 31 + item5Hash; 
// etc 

En su caso item1Hash podría ser sólo a y item2Hash podría ser sólo b.

Los valores de 23 y 31 son relativamente poco importantes, siempre y cuando sean primos (o al menos coprimidos).

Obviamente todavía habrá colisiones, pero que no se quede en los problemas desagradables normales de:

hash(a, a) == hash(b, b) 
hash(a, b) == hash(b, a) 

Si usted sabe más acerca de lo que los valores reales de a y b es probable que se pueda probablemente sea mejor, pero esta es una buena implementación inicial que es fácil de recordar e implementar. Tenga en cuenta que si hay alguna posibilidad de que construya el conjunto con "verificar derrame/subdesbordamiento aritmético", debe ponerlo todo en un bloque sin marcar. (Desbordamiento está muy bien para este algoritmo.)

Answer 2

Qué tal esto:

(a.GetHashcode() + b).GetHashcode() 

le da un código diferente para (a, b) y (b, a) además de que no es tan elegante.

Answer 3

Aquí hay un posible enfoque que tiene en cuenta el orden. (El segundo método se define como un método de extensión.)

public int GetHashCode() 
{ 
    return a.GetHashcode()^b.GetHashcode().RotateLeft(16); 
} 

public static uint RotateLeft(this uint value, int count) 
{ 
    return (value << count) | (value >> (32 - count)) 
} 

Sin duda, sería interesante ver cómo la clase de .NET 4.0 Complex lo hace.

Answer 4

Una forma estándar es la siguiente:

hashcode = 23 
hashcode = (hashcode * 37) + v1 
hashcode = (hashcode * 37) + v2 

23 y 37 son primos entre sí, pero se pueden utilizar otros números también.

Answer 5

Todo eso depende de lo que estés tratando de lograr. Si los hash son para estructuras hash como Dictionary, entonces tiene que tasa de colisión de balance y velocidad de hash. Para tener un hash perfecto sin colisión, será más lento. De manera similar, el algoritmo hash más rápido tendrá más colisiones relativamente. Encontrar el equilibrio perfecto es la clave aquí. También debe tener en cuenta qué tan grande puede ser su hachís efectivo, y si hash debe ser reversible! El enfoque de Noldorin le da un hash perfecto (no lea colisión) si sus partes reales e imaginarias de su número complejo son siempre positivas. Esto servirá incluso para números negativos si estás de acuerdo con las raras colisiones. Pero me preocupa el rango de valores que puede ofrecer, bastante grande para mi gusto.

Si busca los valores hash perfectos (por razones académicas o de investigación) que deberían funcionar incluso para números negativos, puede see this solution (y una serie de otras soluciones en el mismo hilo). En mis pruebas, es más rápido y utiliza el espacio mejor que cualquier otro que he visto.

Answer 6

@JonSkeet proporciona un algoritmo justo y general para calcular un código hash a partir de n códigos hash pero supone que ya sabe qué miembros de un objeto deben ser hash, sabe qué hacer con los miembros nulos y omite una implementación para n elementos arbitrarios. Así que ampliamos su respuesta:

1. Solo las propiedades y los campos públicos, inmutables deben contribuir al código hash de un objeto. Deberían ser públicos (o isomórficos para el público) ya que deberíamos poder contar con dos objetos con la misma superficie visible con el mismo código hash (haciendo alusión a la relación entre igualdad de objeto e igualdad de código hash), y deberían ser inmutables desde el código hash de un objeto nunca debe cambiar en su tiempo de vida (¡ya que puede terminar con un objeto en la ranura incorrecta de una tabla hash!).
2. miembros nulos deben almohadilla, como una constante, como 0
3. @ algoritmo de JonSkeet es un ejemplo de libro de texto para la aplicación de la función de la programación funcional de orden superior generalmente llamado fold (Aggregate en C# LINQ), donde 23 es nuestra semilla y <hash accumulator> * 31 + <current item hash> es nuestra función de plegado:

En F #

let computeHashCode items = 
    items 
    |> Seq.map (fun item -> if item = null then 0 else item.GetHashCode()) 
    |> Seq.fold (fun hash itemHash -> hash * 31 + itemHash) 23 

En C#

Func<IEnumerable<Object>, int> computeHashCode = items => 
    items 
    .Select(item => item == null ? 0 : item.GetHashCode()) 
    .Aggregate(23, (hash, itemHash) => hash * 31 + itemHash);