.net - vulnerability - object equals java

Crea un hashcode de dos números

Question

Intento crear una función rápida de código hash para una clase de números complejos (a + b) en C #.

He visto repetidamente el 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

¿Qué tal esto?

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

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

Answer 2

@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 . Entonces expandimos su respuesta:

1. Solo las propiedades y los campos públicos e inmutables deberían contribuir a un código hash de objetos. 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. los miembros nulos deben hash como una constante, como 0
3. El algoritmo de @JoSkeet es un ejemplo de libro de texto para aplicar la función de programación funcional de orden superior llamada 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

Cª#

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

Answer 3

Aquí hay un enfoque posible 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 lo hace la clase Complex de .NET 4.0.

Answer 4

Mi forma normal de crear un hashcode 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 simplemente ser a , y item2Hash podría simplemente ser b .

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

Obviamente, aún habrá colisiones, pero no se encontrará con los problemas desagradables normales de:

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

Si sabe más sobre cuáles son los valores reales de a y b , probablemente pueda hacerlo 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. (El desbordamiento está bien para este algoritmo).

Answer 5

Todo eso depende de lo que estás tratando de lograr. Si los hash están destinados a estructuras hash como Dictionary , entonces debe equilibrar la tasa de colisión y la 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 el 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 buscas hashes perfectos (de algunos intereses académicos / de investigación) que deberían funcionar incluso para números negativos, puedes ver esta solución (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

Una forma estándar es esta:

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

23 y 37 son coprime, pero también puedes usar otros números.