Obtener hash de una lista de cadenas independientemente del orden

Hay varios enfoques diferentes aquí las dos categorías principales, cada uno típicamente con sus propios beneficios y desventajas, en términos de eficacia y rendimiento. Probablemente es mejor elegir el algoritmo más simple para cualquier aplicación y solo usar las variantes más complejas si es necesario para cualquier situación.

Tenga en cuenta que estos ejemplos utilizan EqualityComparer<T>.Default ya que se ocupará de los elementos null limpiamente. Usted podría hacer mejor que cero para null si se desea. Si T es constrained to struct it is also unnecessary. Puede ho la búsqueda EqualityComparer<T>.Default fuera de la función si así lo desea.

Operaciones conmutativas

Si usa operaciones en los hashcodes de las entradas individuales que son conmutativas entonces esto conducirá al mismo resultado final independientemente del orden.

Hay varias opciones obvias sobre los números:

XOR

public static int GetOrderIndependentHashCode<T>(IEnumerable<T> source)
{
    int hash = 0;
    foreach (T element in source)
    {
        hash = hash ^ EqualityComparer<T>.Default.GetHashCode(element);
    }
    return hash;
}

Un inconveniente de esto es que el hash para {"x", "x"} es el mismo que el hash para { "y", "y" }. Si eso no es un problema para su situación, sin embargo, es probablemente la solución más simple.

Adición

public static int GetOrderIndependentHashCode<T>(IEnumerable<T> source)
{
    int hash = 0;
    foreach (T element in source)
    {
        hash = unchecked (hash + 
            EqualityComparer<T>.Default.GetHashCode(element));
    }
    return hash;
}

El desbordamiento está bien aquí, de ahí el contexto explícito unchecked.

Todavía hay algunos casos desagradables (por ejemplo, {1, -1} y {2, -2}, pero es más probable que esté bien, particularmente con cadenas. En el caso de las listas que pueden contener tales números enteros, siempre se podría implementar una función de hash personalizada (tal vez uno que toma el índice de recurrencia de la valor específico como parámetro y devuelve un código hash único en consecuencia).

Aquí está un ejemplo de tal algoritmo que consigue alrededor del problema mencionado de una manera bastante eficiente. También tiene el beneficio de aumentar enormemente la distribución de los códigos hash generados (ver el artículo vinculado al final para alguna explicación). Un análisis matemático / estadístico de exactamente cómo este algoritmo produce "mejores" códigos hash sería bastante avanzado, pero probarlo a través de un una amplia gama de valores de entrada y el trazado de los resultados debe verificarlo lo suficientemente bien.

public static int GetOrderIndependentHashCode<T>(IEnumerable<T> source)
{
    int hash = 0;
    int curHash;
    int bitOffset = 0;
    // Stores number of occurences so far of each value.
    var valueCounts = new Dictionary<T, int>();

    foreach (T element in source)
    {
        curHash = EqualityComparer<T>.Default.GetHashCode(element);
        if (valueCounts.TryGetValue(element, out bitOffset))
            valueCounts[element] = bitOffset + 1;
        else
            valueCounts.Add(element, bitOffset);

        // The current hash code is shifted (with wrapping) one bit
        // further left on each successive recurrence of a certain
        // value to widen the distribution.
        // 37 is an arbitrary low prime number that helps the
        // algorithm to smooth out the distribution.
        hash = unchecked(hash + ((curHash << bitOffset) |
            (curHash >> (32 - bitOffset))) * 37);
    }

    return hash;
}

Multiplicación

Que tiene pocos beneficios si sobre la suma: números pequeños y una mezcla de números positivos y negativos pueden conducir a una mejor distribución de bits de hash. Como un negativo para compensar este " 1 " se convierte en una entrada inútil que no aporta nada y cualquier elemento cero resulta en un cero. Usted puede caso especial cero no causar este defecto importante.

public static int GetOrderIndependentHashCode<T>(IEnumerable<T> source)
{
    int hash = 17;
    foreach (T element in source)
    {
        int h = EqualityComparer<T>.Default.GetHashCode(element);
        if (h != 0)
            hash = unchecked (hash * h);
    }
    return hash;
}

Orden primero

El otro enfoque principal es hacer cumplir un orden primero, luego usar cualquier función de combinación de hash que desee. El orden en sí mismo es inmaterial siempre y cuando sea consistente.

public static int GetOrderIndependentHashCode<T>(IEnumerable<T> source)
{
    int hash = 0;
    foreach (T element in source.OrderBy(x => x, Comparer<T>.Default))
    {
        // f is any function/code you like returning int
        hash = f(hash, element);
    }
    return hash;
}

Esto tiene algunos beneficios significativos en que las operaciones de combinación posibles en f pueden tener propiedades de hash significativamente mejores (distribución de bits, por ejemplo), pero esto tiene un costo significativamente mayor. El orden es O(n log n) y la copia requerida de la colección es una memoria asignación que no se puede evitar dado el deseo de evitar modificar el original. GetHashCode normalmente, las implementaciones deben evitar por completo las asignaciones. Una posible implementación de f sería similar a la dada en el último ejemplo en la sección de Adición (por ejemplo, cualquier número constante de cambios de bits a la izquierda seguido de una multiplicación por un primo - incluso podría usar primos sucesivos en cada iteración sin costo adicional, ya que solo necesitan ser generados una vez).

Dicho esto, si fueras tratar con casos en los que se puede calcular y almacenar en caché el hash y amortizar el costo en muchas llamadas a GetHashCode este enfoque puede producir un comportamiento superior. También este último enfoque es aún más flexible, ya que puede evitar la necesidad de usar GetHashCode en los elementos si conoce su tipo y en su lugar usar operaciones por byte en ellos para obtener una distribución hash aún mejor. Es probable que ese enfoque sólo sea útil en los casos en que se determine que el desempeño es significativo. embotellamiento.

Finalmente, si quieres una visión general razonablemente completa y bastante no matemática del tema de los códigos hash y su efectividad en general, estas entradas de blog valdría la pena leer, en particular la Implementación de un algoritmo hash simple (pt II) post.