c# - Buena modificación de GetHashCode() para la lista de objetos Foo que respetan el orden

hashcode c#

Question

EnumerableObject : IEnumerable<Foo>

envuelve una List<Foo>

Si EnumerableObject a.SequenceEquals( EnumerableObject b) , entonces son iguales.

Por lo tanto, un GetHashCode debe ser implementado. El problema es que cada elemento de la lista devolverá el mismo código hash para cualquier lista con todos y solo los mismos elementos, independientemente del orden. Esto está bien en términos de funcionamiento, pero dará lugar a muchas colisiones, lo que ralentizará la recuperación, etc.

¿Qué es un método GetHashCode bueno y rápido para listas de objetos que depende de la orden?

Answer 1

El método .GetHashCode() generalmente solo devuelve un hash basado en la referencia del objeto (dirección del puntero). Esto se debe a que el cálculo del código hash de cada elemento en una lista enumerable puede requerir mucho tiempo. En lugar de sobrescribir el comportamiento existente, prefiero usar un método de extensión y usarlo solo cuando el código hash deba determinarse de manera determinista:

public static class EnumerableExtensions
{
    public static int GetSequenceHashCode<TItem>(this IEnumerable<TItem> list)
    {
        if (list == null) return 0;
        const int seedValue = 0x2D2816FE;
        const int primeNumber = 397;
        return list.Aggregate(seedValue, (current, item) => (current * primeNumber) + (Equals(item, default(TItem)) ? 0 : item.GetHashCode()));
    }
}

Answer 2

En primer lugar, compruebe que necesita un código hash. ¿Va a colocar estas listas en una estructura de mapeo de hash (por ejemplo, diccionario, hashset, etc.)? Si no, olvídalo.

Ahora, asumiendo que quiere decir que EnumerableObject ya reemplaza a Equals(object) (y, por lo tanto, con suerte, también implementa IEquatable<EnumerableObject> ) por alguna razón, entonces esto es realmente necesario. Desea equilibrar la velocidad frente a la distribución de bits.

Un buen punto de inicio es un mult + add o un shift + xo como:

public override int GetHashCode()
{
    int res = 0x2D2816FE;
    foreach(var item in this)
    {
        res = res * 31 + (item == null ? 0 : item.GetHashCode());
    }
    return res;
}

(Esto supone que estás usando item.Equals () para tu comparación de igualdad de secuencia, si estás usando los equivalentes de IEqualityComparer, tendrás que llamar a su código hash).

Desde allí podemos optimizar.

Si los elementos nulos no están permitidos, elimine la comprobación de nulos (tenga cuidado, esto hará que el código se lance si alguna vez encuentra un nulo).

Si las listas muy grandes son comunes, necesitamos reducir el número examinado, mientras tratamos de no dar lugar a muchas colisiones. Compara las siguientes diferentes implementaciones:

public override int GetHashCode()
{
    int res = 0x2D2816FE;
    int max = Math.Min(Count, 16);
    for(int i = 0, i != max; ++i)
    {
        var item = this[i];
        res = res * 31 + (item == null ? 0 : item.GetHashCode());
    }
    return res;
}

public override int GetHashCode()
{
    int res = 0x2D2816FE;
    int min = Math.Max(-1, Count - 16);
    for(int i = Count -1, i != min; --i)
    {
        var item = this[i];
        res = res * 31 + (item == null ? 0 : item.GetHashCode());
    }
    return res;
}

public override int GetHashCode()
{
    int res = 0x2D2816FE;
    int step = Count / 16 + 1;
    for(int i = 0, i < Count; i += step)
    {
        var item = this[i];
        res = res * 31 + (item == null ? 0 : item.GetHashCode());
    }
    return res;
}

Cada uno de estos restringe el número total de elementos examinados, lo que acelera la ejecución pero conlleva riesgos de hashes de peor calidad. Cuál (si lo hay) es mejor depende de si las colecciones con el mismo inicio o el mismo final son más probables.

Cambiando el número 16 anterior se ajusta el saldo; más pequeño es más rápido pero más alto es mejor calidad de hash con menor riesgo de colisiones de hash.

Edit: Y ahora puedes usar mi implementación de SpookyHash v. 2 :

public override int GetHashCode()
{
  var hasher = new SpookyHash();//use methods with seeds if you need to prevent HashDos
  foreach(var item in this)
    hasher.Update(item.GetHashCode());//or relevant feeds of item, etc.
  return hasher.Final().GetHashCode();
}

Esto creará una distribución mucho mejor que mult + add o shift + xor, además de ser particularmente rápido (especialmente en procesos de 64 bits, ya que el algoritmo está optimizado para eso, aunque también funciona bien en 32 bits).

Answer 3

Lo haría de la misma manera que normalmente combino los códigos hash, con una suma y una multiplicación:

public override int GetHashCode()
{
    unchecked
    {
        int hash = 19;
        foreach (var foo in foos)
        {
            hash = hash * 31 + foo.GetHashCode();
        }
        return hash;
    }
}

(Tenga en cuenta que no debe agregar nada a la lista después de que esto se haya utilizado para la clave en una tabla hash de cualquier descripción, ya que el hash cambiará. Esto también supone que no hay entradas nulas; Hay que tener en cuenta eso.)