Pregunta ¿Cuál es el mejor algoritmo para un System.Object.GetHashCode reemplazado?


En la red System.Object.GetHashCode método se utiliza en muchos lugares, a través de las bibliotecas de clase base de .NET. Especialmente cuando se encuentran elementos en una colección rápidamente o para determinar la igualdad. ¿Existe un algoritmo / práctica recomendada estándar sobre cómo implementar el GetHashCode anular para mis clases personalizadas para no degradar el rendimiento?


1216
2017-11-04 20:53


origen


Respuestas:


Por lo general, voy con algo así como la implementación dada en Josh Bloch fabuloso  Java efectivo. Es rápido y crea un hash muy bueno que no es probable que cause colisiones. Elija dos números primos diferentes, p. 17 y 23, y hacer:

public override int GetHashCode()
{
    unchecked // Overflow is fine, just wrap
    {
        int hash = 17;
        // Suitable nullity checks etc, of course :)
        hash = hash * 23 + field1.GetHashCode();
        hash = hash * 23 + field2.GetHashCode();
        hash = hash * 23 + field3.GetHashCode();
        return hash;
    }
}

Como se señala en los comentarios, es posible que, en su lugar, sea mejor elegir un primo grande para multiplicar. Aparentemente 486187739 es bueno ... y aunque la mayoría de los ejemplos que he visto con números pequeños tienden a usar números primos, hay al menos algoritmos similares donde a menudo se usan números no primos. En el no-bastante-FNV Por ejemplo, más adelante, por ejemplo, he usado números que aparentemente funcionan bien, pero el valor inicial no es primo. (La constante de multiplicación es primordial sin embargo. No sé qué tan importante es eso.)

Esto es mejor que la práctica común de XORing hashcodes por dos razones principales. Supongamos que tenemos un tipo con dos int campos:

XorHash(x, x) == XorHash(y, y) == 0 for all x, y
XorHash(x, y) == XorHash(y, x) for all x, y

Por cierto, el algoritmo anterior es el utilizado actualmente por el compilador C # para tipos anónimos.

Esta página da bastantes opciones. Creo que para la mayoría de los casos, lo anterior es "lo suficientemente bueno" y es increíblemente fácil de recordar y acertar. los FNV alternativa es similarmente simple, pero utiliza diferentes constantes y XOR en lugar de ADD como una operación de combinación. Parece alguna cosa como el código siguiente, pero el algoritmo FNV normal opera en bytes individuales, por lo que sería necesario modificar para realizar una iteración por byte, en lugar de un valor hash de 32 bits. FNV también está diseñado para longitudes de datos variables, mientras que la forma en que lo estamos usando aquí es siempre para el mismo número de valores de campo. Los comentarios sobre esta respuesta sugieren que el código aquí en realidad no funciona tan bien (en el caso de muestra probado) como el enfoque de adición anterior.

// Note: Not quite FNV!
public override int GetHashCode()
{
    unchecked // Overflow is fine, just wrap
    {
        int hash = (int) 2166136261;
        // Suitable nullity checks etc, of course :)
        hash = (hash * 16777619) ^ field1.GetHashCode();
        hash = (hash * 16777619) ^ field2.GetHashCode();
        hash = (hash * 16777619) ^ field3.GetHashCode();
        return hash;
    }
}

Tenga en cuenta que una cosa a tener en cuenta es que, idealmente, debe evitar que cambie su estado sensible a la igualdad (y por lo tanto, el código hash) después de agregarlo a una colección que depende del código hash.

Según el documentación:

Puede anular GetHashCode para tipos de referencia inmutables. En general, para los tipos de referencia mutables, debe anular GetHashCode solo si:

  • Puede calcular el código hash de los campos que no son mutables; o
  • Puede asegurarse de que el código hash de un objeto mutable no cambie mientras el objeto está contenido en una colección que se basa en su código hash.

1357
2017-11-04 20:56



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

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

Esto funcionará para cualquier cantidad de propiedades. No usa boxeo ni recursos adicionales. Solo usa el algoritmo ya implementado en el marco para tipos anónimos.


302
2018-01-07 21:38



Aquí está mi ayudante hashcode.
Su ventaja es que utiliza argumentos de tipo genérico y, por lo tanto, no causará el boxeo:

public static class HashHelper
{
    public static int GetHashCode<T1, T2>(T1 arg1, T2 arg2)
    {
         unchecked
         {
             return 31 * arg1.GetHashCode() + arg2.GetHashCode();
         }
    }

    public static int GetHashCode<T1, T2, T3>(T1 arg1, T2 arg2, T3 arg3)
    {
        unchecked
        {
            int hash = arg1.GetHashCode();
            hash = 31 * hash + arg2.GetHashCode();
            return 31 * hash + arg3.GetHashCode();
        }
    }

    public static int GetHashCode<T1, T2, T3, T4>(T1 arg1, T2 arg2, T3 arg3, 
        T4 arg4)
    {
        unchecked
        {
            int hash = arg1.GetHashCode();
            hash = 31 * hash + arg2.GetHashCode();
            hash = 31 * hash + arg3.GetHashCode();
            return 31 * hash + arg4.GetHashCode();
        }
    }

    public static int GetHashCode<T>(T[] list)
    {
        unchecked
        {
            int hash = 0;
            foreach (var item in list)
            {
                hash = 31 * hash + item.GetHashCode();
            }
            return hash;
        }
    }

    public static int GetHashCode<T>(IEnumerable<T> list)
    {
        unchecked
        {
            int hash = 0;
            foreach (var item in list)
            {
                hash = 31 * hash + item.GetHashCode();
            }
            return hash;
        }
    }

    /// <summary>
    /// Gets a hashcode for a collection for that the order of items 
    /// does not matter.
    /// So {1, 2, 3} and {3, 2, 1} will get same hash code.
    /// </summary>
    public static int GetHashCodeForOrderNoMatterCollection<T>(
        IEnumerable<T> list)
    {
        unchecked
        {
            int hash = 0;
            int count = 0;
            foreach (var item in list)
            {
                hash += item.GetHashCode();
                count++;
            }
            return 31 * hash + count.GetHashCode();
        }
    }

    /// <summary>
    /// Alternative way to get a hashcode is to use a fluent 
    /// interface like this:<br />
    /// return 0.CombineHashCode(field1).CombineHashCode(field2).
    ///     CombineHashCode(field3);
    /// </summary>
    public static int CombineHashCode<T>(this int hashCode, T arg)
    {
        unchecked
        {
            return 31 * hashCode + arg.GetHashCode();   
        }
    }

También tiene un método de extensión para proporcionar una interfaz fluida, por lo que puede usarlo así:

public override int GetHashCode()
{
    return HashHelper.GetHashCode(Manufacturer, PartN, Quantity);
}

o así:

public override int GetHashCode()
{
    return 0.CombineHashCode(Manufacturer)
        .CombineHashCode(PartN)
        .CombineHashCode(Quantity);
}

94
2018-04-04 18:26



Tengo una clase Hashing en la biblioteca Helper que la uso para este propósito.

/// <summary> 
/// This is a simple hashing function from Robert Sedgwicks Hashing in C book.
/// Also, some simple optimizations to the algorithm in order to speed up
/// its hashing process have been added. from: www.partow.net
/// </summary>
/// <param name="input">array of objects, parameters combination that you need
/// to get a unique hash code for them</param>
/// <returns>Hash code</returns>
public static int RSHash(params object[] input)
{
    const int b = 378551;
    int a = 63689;
    int hash = 0;

    // If it overflows then just wrap around
    unchecked
    {
        for (int i = 0; i < input.Length; i++)
        {
            if (input[i] != null)
            {
                hash = hash * a + input[i].GetHashCode();
                a = a * b;
            }
        }
    }

    return hash;
}

Entonces, simplemente puedes usarlo como:

public override int GetHashCode()
{
    return Hashing.RSHash(_field1, _field2, _field3);
}

No evalué su rendimiento, por lo que cualquier comentario es bienvenido.


57
2018-02-23 11:46



Aquí está mi clase de ayuda usando La implementación de Jon Skeet.

public static class HashCode
{
    public const int Start = 17;

    public static int Hash<T>(this int hash, T obj)
    {
        var h = EqualityComparer<T>.Default.GetHashCode(obj);
        return unchecked((hash * 31) + h);
    }
}

Uso:

public override int GetHashCode()
{
    return HashCode.Start
        .Hash(_field1)
        .Hash(_field2)
        .Hash(_field3);
}

Si desea evitar escribir un método de extensión para System.Int32:

public struct HashCode
{
    private readonly int _value;

    public HashCode(int value) => _value = value;

    public static HashCode Start { get; } = new HashCode(17);

    public static implicit operator int(HashCode hash) => hash._value;

    public HashCode Hash<T>(T obj)
    {
        var h = EqualityComparer<T>.Default.GetHashCode(obj);
        return unchecked(new HashCode((_value * 31) + h));
    }

    public override int GetHashCode() => _value;
}

Sigue siendo genérico, todavía evita la asignación de montones y se usa exactamente de la misma manera:

public override int GetHashCode()
{
    // This time `HashCode.Start` is not an `Int32`, it's a `HashCode` instance.
    // And the result is implicitly converted to `Int32`.
    return HashCode.Start
        .Hash(_field1)
        .Hash(_field2)     
        .Hash(_field3);
}

Actualización después del comentario de Martin:

obj != null causó el boxeo, así que cambié al comparador predeterminado.

  • Ver esta respuesta con respecto al rendimiento predeterminado del comparador.
  • Ver esta pregunta para una discusión sobre los códigos hash de valores nulos.

Editar (mayo de 2018):

EqualityComparer<T>.Default getter es ahora un JIT intrínseco solicitud de extracción es mencionado por Stephen Toub en esta publicación en el blog.


49
2017-09-04 12:32



En la mayoría de los casos en que Equals () compara múltiples campos, realmente no importa si Hashash () hash en un campo o en muchos. Solo tienes que asegurarte de que el cálculo del hash es realmente barato (Sin asignaciones, por favor) y rápido (Sin cálculos pesados y ciertamente no hay conexiones de bases de datos) y proporciona una buena distribución.

El levantamiento de objetos pesados ​​debe ser parte del método Equals (); el hash debería ser una operación muy económica para poder llamar a Equals () en el menor número posible de elementos.

Y un último consejo: No confíe en que GetHashCode () se mantenga estable en múltiples ejecuciones de aplicaciones. Muchos tipos de .Net no garantizan que sus códigos hash permanezcan iguales después de un reinicio, por lo que solo debe usar el valor de GetHashCode () para estructuras de datos de memoria.


26
2018-02-23 11:55



Hasta hace poco mi respuesta hubiera sido muy similar a la de Jon Skeet aquí. Sin embargo, recientemente comencé un proyecto que utilizaba tablas hash de power-of-two, que son tablas hash donde el tamaño de la tabla interna es 8, 16, 32, etc. Hay una buena razón para favorecer los tamaños de números primos, pero hay son algunas ventajas para los tamaños de potencia de dos también.

Y es bastante desagradable. Entonces, después de un poco de experimentación e investigación, comencé a volver a mezclar mis hashes con lo siguiente:

public static int ReHash(int source)
{
  unchecked
  {
    ulong c = 0xDEADBEEFDEADBEEF + (ulong)source;
    ulong d = 0xE2ADBEEFDEADBEEF ^ c;
    ulong a = d += c = c << 15 | c >> -15;
    ulong b = a += d = d << 52 | d >> -52;
    c ^= b += a = a << 26 | a >> -26;
    d ^= c += b = b << 51 | b >> -51;
    a ^= d += c = c << 28 | c >> -28;
    b ^= a += d = d << 9 | d >> -9;
    c ^= b += a = a << 47 | a >> -47;
    d ^= c += b << 54 | b >> -54;
    a ^= d += c << 32 | c >> 32;
    a += d << 25 | d >> -25;
    return (int)(a >> 1);
  }
}

Y luego mi tabla de hash de poder de dos ya no masticaba.

Esto me molestó, porque lo anterior no debería funcionar. O más precisamente, no debería funcionar a menos que el original GetHashCode() era pobre de una manera muy particular.

Volver a mezclar un código hash no puede mejorar un gran código hash, porque el único efecto posible es que presentamos algunas colisiones más.

Volver a mezclar un código hash no puede mejorar un código hash terrible, porque el único efecto posible es que cambiemos, p. un gran número de colisiones en el valor 53 a un gran número de valor 18,3487,291.

Volver a mezclar un código hash solo puede mejorar un código hash que al menos sirvió para evitar colisiones absolutas en todo su rango (232 valores posibles) pero mal para evitar colisiones cuando se moduló para uso real en una tabla hash. Si bien el módulo más simple de una tabla de potencia de dos lo hizo más aparente, también estaba teniendo un efecto negativo con las tablas de números primos más comunes, que simplemente no era tan obvio (el trabajo adicional en la reconstrucción superaría el beneficio , pero el beneficio aún estaría allí).

Editar: También estaba usando el direccionamiento abierto, lo que también habría aumentado la sensibilidad a la colisión, tal vez más que el hecho de que era potencia de dos.

Y bueno, fue inquietante cuánto string.GetHashCode() implementaciones en .RED (o estudia aquí) se podría mejorar de esta manera (en el orden de las pruebas que se ejecutan alrededor de 20-30 veces más rápido debido a la menor cantidad de colisiones) y más inquietante cuánto podría mejorar mis propios códigos hash (mucho más que eso).

Todas las implementaciones de GetHashCode () que codifiqué en el pasado, y de hecho utilizadas como base de las respuestas en este sitio, fueron mucho peores de lo que hubiera sido. La mayoría de las veces fue "lo suficientemente bueno" para muchos de los usos, pero yo quería algo mejor.

Así que puse ese proyecto a un lado (de todos modos era un proyecto favorito) y comencé a buscar rápidamente cómo generar un código hash bueno y bien distribuido en .NET.

Al final me decidí a portar SpookyHash a la red. De hecho, el código anterior es una versión rápida de SpookyHash para producir una salida de 32 bits a partir de una entrada de 32 bits.

Ahora, SpookyHash no es una buena pieza de código rápida y fácil de recordar. Mi punto de inflexión es aún menor porque lo he alineado a mano para obtener una mejor velocidad *. Pero para eso sirve la reutilización de código.

Entonces puse ese proyecto a un lado, porque al igual que el proyecto original había producido la pregunta de cómo producir un mejor código hash, por lo que el proyecto produjo la pregunta de cómo producir una mejor memcpy .NET.

Luego volví y produje muchas sobrecargas para alimentar fácilmente a casi todos los tipos nativos (excepto decimal†) en un código hash.

Es rápido, por lo que Bob Jenkins merece la mayor parte del crédito porque su código original que porté es aún más rápido, especialmente en máquinas de 64 bits que el algoritmo está optimizado para ‡.

El código completo se puede ver en https://bitbucket.org/JonHanna/spookilysharp/src pero considere que el código anterior es una versión simplificada de este.

Sin embargo, como ya está escrito, uno puede usarlo más fácilmente:

public override int GetHashCode()
{
  var hash = new SpookyHash();
  hash.Update(field1);
  hash.Update(field2);
  hash.Update(field3);
  return hash.Final().GetHashCode();
}

También toma los valores iniciales, por lo que si necesita tratar con datos que no son de confianza y quiere protegerse contra los ataques Hash DoS, puede establecer una semilla en función del tiempo de actividad o similar, y los atacantes pueden hacer que los resultados sean impredecibles.

private static long hashSeed0 = Environment.TickCount;
private static long hashSeed1 = DateTime.Now.Ticks;
public override int GetHashCode()
{
  //produce different hashes ever time this application is restarted
  //but remain consistent in each run, so attackers have a harder time
  //DoSing the hash tables.
  var hash = new SpookyHash(hashSeed0, hashSeed1);
  hash.Update(field1);
  hash.Update(field2);
  hash.Update(field3);
  return hash.Final().GetHashCode();
}

* Una gran sorpresa en esto es que la mano-enlining un método de rotación que regresó (x << n) | (x >> -n) cosas mejoradas Hubiera estado seguro de que la trepidación habría indicado eso para mí, pero los perfiles mostraron lo contrario.

decimal no es nativo desde la perspectiva de .NET aunque es de C #. El problema con esto es que es propio GetHashCode() trata la precisión como significativa mientras que la suya Equals() no. Ambas son elecciones válidas, pero no mixtas. Al implementar su propia versión, debe elegir hacer una, o la otra, pero no sé cuál de ellas le gustaría.

‡ Por comparación. Si se usa en una cadena, SpookyHash en 64 bits es considerablemente más rápido que string.GetHashCode() en 32 bits, que es ligeramente más rápido que string.GetHashCode() en 64 bits, que es considerablemente más rápido que SpookyHash en 32 bits, aunque lo suficientemente rápido como para ser una opción razonable.


18
2018-01-14 14:15



Este es bueno:

/// <summary>
/// Helper class for generating hash codes suitable 
/// for use in hashing algorithms and data structures like a hash table. 
/// </summary>
public static class HashCodeHelper
{
    private static int GetHashCodeInternal(int key1, int key2)
    {
        unchecked
        {
           var num = 0x7e53a269;
           num = (-1521134295 * num) + key1;
           num += (num << 10);
           num ^= (num >> 6);

           num = ((-1521134295 * num) + key2);
           num += (num << 10);
           num ^= (num >> 6);

           return num;
        }
    }

    /// <summary>
    /// Returns a hash code for the specified objects
    /// </summary>
    /// <param name="arr">An array of objects used for generating the 
    /// hash code.</param>
    /// <returns>
    /// A hash code, suitable for use in hashing algorithms and data 
    /// structures like a hash table. 
    /// </returns>
    public static int GetHashCode(params object[] arr)
    {
        int hash = 0;
        foreach (var item in arr)
            hash = GetHashCodeInternal(hash, item.GetHashCode());
        return hash;
    }

    /// <summary>
    /// Returns a hash code for the specified objects
    /// </summary>
    /// <param name="obj1">The first object.</param>
    /// <param name="obj2">The second object.</param>
    /// <param name="obj3">The third object.</param>
    /// <param name="obj4">The fourth object.</param>
    /// <returns>
    /// A hash code, suitable for use in hashing algorithms and
    /// data structures like a hash table.
    /// </returns>
    public static int GetHashCode<T1, T2, T3, T4>(T1 obj1, T2 obj2, T3 obj3,
        T4 obj4)
    {
        return GetHashCode(obj1, GetHashCode(obj2, obj3, obj4));
    }

    /// <summary>
    /// Returns a hash code for the specified objects
    /// </summary>
    /// <param name="obj1">The first object.</param>
    /// <param name="obj2">The second object.</param>
    /// <param name="obj3">The third object.</param>
    /// <returns>
    /// A hash code, suitable for use in hashing algorithms and data 
    /// structures like a hash table. 
    /// </returns>
    public static int GetHashCode<T1, T2, T3>(T1 obj1, T2 obj2, T3 obj3)
    {
        return GetHashCode(obj1, GetHashCode(obj2, obj3));
    }

    /// <summary>
    /// Returns a hash code for the specified objects
    /// </summary>
    /// <param name="obj1">The first object.</param>
    /// <param name="obj2">The second object.</param>
    /// <returns>
    /// A hash code, suitable for use in hashing algorithms and data 
    /// structures like a hash table. 
    /// </returns>
    public static int GetHashCode<T1, T2>(T1 obj1, T2 obj2)
    {
        return GetHashCodeInternal(obj1.GetHashCode(), obj2.GetHashCode());
    }
}

Y aquí está cómo usarlo:

private struct Key
{
    private Type _type;
    private string _field;

    public Type Type { get { return _type; } }
    public string Field { get { return _field; } }

    public Key(Type type, string field)
    {
        _type = type;
        _field = field;
    }

    public override int GetHashCode()
    {
        return HashCodeHelper.GetHashCode(_field, _type);
    }

    public override bool Equals(object obj)
    {
        if (!(obj is Key))
            return false;
        var tf = (Key)obj;
        return tf._field.Equals(_field) && tf._type.Equals(_type);
    }
}

12
2017-10-07 10:51