¿Cuál es el mejor algoritmo para anular GetHashCode?

En .NET, el GetHashCodemétodo se utiliza en muchos lugares de las bibliotecas de clases base de .NET. Implementarlo correctamente es especialmente importante para encontrar elementos rápidamente en una colección o al determinar la igualdad.

¿Existe un algoritmo estándar o una mejor práctica sobre cómo implementarlo GetHashCodeen mis clases personalizadas para no degradar el rendimiento?

Nov 05 '08 03:11 bitbonk

ValueTuple: actualización para C# 7

Como menciona @cactuaroid en los comentarios, se puede usar una tupla de valor. Esto ahorra algunas pulsaciones de teclas y, lo que es más importante, se ejecuta exclusivamente en la pila (sin basura):

(PropA, PropB, PropC, PropD).GetHashCode();

(Nota: la técnica original que utiliza tipos anónimos parece crear un objeto en el montón, es decir, basura, ya que los tipos anónimos se implementan como clases, aunque el compilador podría optimizar esto. Sería interesante comparar estas opciones, pero la La opción tupla debería ser superior.)

Tipo anónimo (respuesta original)

Microsoft ya proporciona un buen generador genérico de HashCode: simplemente copie los valores de su propiedad/campo a un tipo anónimo y haga un hash:

new { PropA, PropB, PropC, PropD }.GetHashCode();

Esto funcionará para cualquier número de propiedades. No utiliza boxeo. Simplemente utiliza el algoritmo ya implementado en el marco para tipos anónimos.

Jan 07 '2011 21:01 Rick Love

UsandoSystem.HashCode

Si está utilizando .NET Standard 2.1 o superior, puede utilizar la estructura System.HashCode . En marcos anteriores, está disponible en el Microsoft.Bcl.HashCodepaquete. Hay dos métodos para usarlo:

HashCode.Combinar

El Combinemétodo se puede utilizar para crear un código hash, con hasta ocho objetos.

public override int GetHashCode() => HashCode.Combine(this.object1, this.object2);

HashCode.Agregar

El Addmétodo le ayuda a lidiar con colecciones:

public override int GetHashCode()
{
    var hashCode = new HashCode();
    hashCode.Add(this.object1);
    foreach (var item in this.collection)
    {
        hashCode.Add(item);
    }
    return hashCode.ToHashCode();
}

ObtenerHashCode es fácil

Una alternativa a System.HashCodeesto es súper fácil de usar y al mismo tiempo rápida. Puede leer la publicación completa del blog ' GetHashCode Made Easy ' para obtener más detalles y comentarios.

Ejemplo de uso

public class SuperHero
{
    public int Age { get; set; }
    public string Name { get; set; }
    public List<string> Powers { get; set; }

    public override int GetHashCode() =>
        HashCode.Of(this.Name).And(this.Age).AndEach(this.Powers);
}

Implementación

public struct HashCode : IEquatable<HashCode>
{
    private const int EmptyCollectionPrimeNumber = 19;
    private readonly int value;

    private HashCode(int value) => this.value = value;

    public static implicit operator int(HashCode hashCode) => hashCode.value;

    public static bool operator ==(HashCode left, HashCode right) => left.Equals(right);

    public static bool operator !=(HashCode left, HashCode right) => !(left == right);

    public static HashCode Of<T>(T item) => new HashCode(GetHashCode(item));

    public static HashCode OfEach<T>(IEnumerable<T> items) =>
        items == null ? new HashCode(0) : new HashCode(GetHashCode(items, 0));

    public HashCode And<T>(T item) => 
        new HashCode(CombineHashCodes(this.value, GetHashCode(item)));

    public HashCode AndEach<T>(IEnumerable<T> items)
    {
        if (items == null)
        {
            return new HashCode(this.value);
        }

        return new HashCode(GetHashCode(items, this.value));
    }

    public bool Equals(HashCode other) => this.value.Equals(other.value);

    public override bool Equals(object obj)
    {
        if (obj is HashCode)
        {
            return this.Equals((HashCode)obj);
        }

        return false;
    }

    public override int GetHashCode() => this.value.GetHashCode();

    private static int CombineHashCodes(int h1, int h2)
    {
        unchecked
        {
            // Code copied from System.Tuple a good way to combine hashes.
            return ((h1 << 5) + h1) ^ h2;
        }
    }

    private static int GetHashCode<T>(T item) => item?.GetHashCode() ?? 0;

    private static int GetHashCode<T>(IEnumerable<T> items, int startHashCode)
    {
        var temp = startHashCode;

        var enumerator = items.GetEnumerator();
        if (enumerator.MoveNext())
        {
            temp = CombineHashCodes(temp, GetHashCode(enumerator.Current));

            while (enumerator.MoveNext())
            {
                temp = CombineHashCodes(temp, GetHashCode(enumerator.Current));
            }
        }
        else
        {
            temp = CombineHashCodes(temp, EmptyCollectionPrimeNumber);
        }

        return temp;
    }
}

¿Qué hace que un buen algoritmo?

Actuación

El algoritmo que calcula un código hash debe ser rápido. Un algoritmo simple suele ser más rápido. Uno que no asigne memoria adicional también reducirá la necesidad de recolección de basura, lo que a su vez también mejorará el rendimiento.

Específicamente en las funciones hash de C#, a menudo se utiliza la uncheckedpalabra clave que detiene la comprobación de desbordamiento para mejorar el rendimiento.

determinista

El algoritmo hash debe ser determinista , es decir, dada la misma entrada, siempre debe producir la misma salida.

Reducir colisiones

The algorithm that calculates a hash code needs to keep hash collisions to a minumum. A hash collision is a situation that occurs when two calls to GetHashCode on two different objects produce identical hash codes. Note that collisions are allowed (some have the misconceptions that they are not) but they should be kept to a minimum.

A lot of hash functions contain magic numbers like 17 or 23. These are special prime numbers which due to their mathematical properties help to reduce hash collisions as compared to using non-prime numbers.

Hash Uniformity

A good hash function should map the expected inputs as evenly as possible over its output range i.e. it should output a wide range of hashes based on its inputs that are evenly spread. It should have hash uniformity.

Prevent's DoS

In .NET Core each time you restart an application you will get different hash codes. This is a security feature to prevent Denial of Service attacks (DoS). For .NET Framework you should enable this feature by adding the following App.config file:

<?xml version ="1.0"?>  
<configuration>  
   <runtime>  
      <UseRandomizedStringHashAlgorithm enabled="1" />  
   </runtime>  
</configuration>

Because of this feature, hash codes should never be used outside of the application domain in which they were created, they should never be used as key fields in a collection and they should never be persisted.

Read more about this here.

Cryptographically Secure?

The algorithm does not have to be a Cryptographic hash function. Meaning it does not have to satisfy the following conditions:

• It is infeasible to generate a message that yields a given hash value.
• It is infeasible to find two different messages with the same hash value.
• A small change to a message should change the hash value so extensively that the new hash value appears uncorrelated with the old hash value (avalanche effect).

Jun 11 '2019 08:06 Muhammad Rehan Saeed