c# - funcion - Obteniendo hash de una lista de cadenas sin importar el orden

sha256 c# ejemplo

Question

Me gustaría escribir una función GetHashCodeOfList() que devuelve un código hash de una lista de cadenas, independientemente del orden. Dado que 2 listas con las mismas cadenas deben devolver el mismo código hash.

ArrayList list1 = new ArrayList()    
list1.Add("String1");
list1.Add("String2");
list1.Add("String3");    

ArrayList list2 = new ArrayList()    
list2.Add("String3");    
list2.Add("String2"); 
list2.Add("String1");

GetHashCodeOfList(list1) = GetHashCodeOfList(list2) //this should be equal.

Tuve algunas reflexiones:

1. Primero puedo ordenar la lista, luego combinar la lista ordenada en 1 cadena larga y luego llamar a GetHashCode() . Sin embargo, la clasificación es una operación lenta.

2. Puedo obtener el hash de cada cadena individual (llamando a string.GetHashCode() ) en la lista, luego multiplicando todos los hashes y llamando a Mod UInt32.MaxValue . Por ejemplo: "String1".GetHashCode() * "String2".GetHashCode * … MOD UInt32.MaxValue . Pero esto da como resultado un desbordamiento de números.

Alguien tiene alguna opinión?

Gracias de antemano por tu ayuda.

Answer 1

Hay varios enfoques diferentes aquí en las dos categorías principales, cada uno por lo general con sus propios beneficios y desventajas, en términos de eficacia y rendimiento. Probablemente sea 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 tratará con elementos nulos limpiamente. Podría hacer mejor que cero para nulo si así lo desea. Si T está restringido a struct, también es innecesario. Puede levantar la búsqueda EqualityComparer<T>.Default de la función si así lo desea.

Operaciones conmutativas

Si usa operaciones en los códigos de hash de las entradas individuales que son commutative , esto dará lugar al mismo resultado final independientemente del orden.

Hay varias opciones obvias en 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;
}

Una desventaja de eso es que el hash para {"x", "x"} es lo mismo que el hash para {"y", "y"}. Si eso no es un problema para su situación, 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, especialmente con cadenas. En el caso de las listas que pueden contener tales enteros, siempre se puede implementar una función hash personalizada (tal vez una que toma el índice de recurrencia del valor específico como parámetro y devuelve un código hash único en consecuencia).

Aquí hay un ejemplo de dicho algoritmo que evita el problema mencionado de una manera bastante eficiente. También tiene el beneficio de aumentar en gran medida la distribución de los códigos hash generados (consulte el artículo vinculado al final para obtener alguna explicación). Un análisis matemático / estadístico de cómo exactamente este algoritmo produce códigos hash "mejores" sería bastante avanzado, pero al probarlo a través de una amplia gama de valores de entrada y al trazar los resultados, debería 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 se suma: números pequeños y una combinación de números positivos y negativos que pueden conducir a una mejor distribución de bits hash. Como negativo para compensar, este "1" se convierte en una entrada inútil que no aporta nada y cualquier elemento cero da como resultado un cero. Puede cero caso especial para no causar este gran defecto.

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 central es imponer en primer lugar algunos pedidos, luego utilizar cualquier función de combinación de hash que desee. El orden en sí mismo es inmaterial siempre que 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 el sentido de que las operaciones de combinación posibles en f pueden tener propiedades hash significativamente mejores (distribución de bits, por ejemplo), pero esto tiene un costo significativamente mayor. El género es O(n log n) y la copia requerida de la colección es una asignación de memoria que no puede evitarse dado el deseo de evitar modificar el original. GetHashCode implementaciones de GetHashCode normalmente deberían evitar asignaciones por completo. Una implementación posible 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 bit seguidos de una multiplicación por un primo; incluso podría usar primos sucesivos en cada iteración sin costo adicional, ya que solo necesitan generarse una vez).

Dicho esto, si tuviera que lidiar con casos en los que pudiera calcular y guardar en caché el hash y amortizar el costo en muchas llamadas a GetHashCode este enfoque puede generar un comportamiento superior. Además, el último enfoque es aún más flexible, ya que puede evitar la necesidad de utilizar GetHashCode en los elementos si conoce su tipo y en su lugar utiliza operaciones por bytes para obtener una distribución de hash aún mejor. Tal enfoque probablemente solo sea útil en los casos en que el desempeño se identifique como un cuello de botella significativo.

Finalmente, si desea una visión general razonablemente exhaustiva y no matemática del tema de los códigos hash y su efectividad en general, estas publicaciones de blog valdrían la pena, en particular, la publicación Implementing the hash algorithm (pt II) post.

Answer 2

Una alternativa para ordenar las listas de cadenas sería obtener los códigos hash de las cadenas y luego ordenar los códigos hash. (La comparación de las notas es menos costosa que la comparación de las cadenas.) Luego puede usar un algoritmo para fusionar los códigos hash que (con suerte) dan una mejor distribución.

Ejemplo:

GetHashCodeOfList<T>(IEnumerable<T> list) {
   List<int> codes = new List<int>();
   foreach (T item in list) {
      codes.Add(item.GetHashCode());
   }
   codes.Sort();
   int hash = 0;
   foreach (int code in codes) {
      unchecked {
         hash *= 251; // multiply by a prime number
         hash += code; // add next hash code
      }
   }
   return hash;
}

Answer 3

    Dim list1 As ArrayList = New ArrayList()
    list1.Add("0")
    list1.Add("String1")
    list1.Add("String2")
    list1.Add("String3")
    list1.Add("abcdefghijklmnopqrstuvwxyz")

    Dim list2 As ArrayList = New ArrayList()
    list2.Add("0")
    list2.Add("String3")
    list2.Add("abcdefghijklmnopqrstuvwxyz")
    list2.Add("String2")
    list2.Add("String1")
    If GetHashCodeOfList(list1) = GetHashCodeOfList(list2) Then
        Stop
    Else
        Stop
    End If
    For x As Integer = list1.Count - 1 To 0 Step -1
        list1.RemoveAt(list1.Count - 1)
        list2.RemoveAt(list2.Count - 1)
        Debug.WriteLine(GetHashCodeOfList(list1).ToString)
        Debug.WriteLine(GetHashCodeOfList(list2).ToString)
        If list1.Count = 2 Then Stop
    Next


Private Function GetHashCodeOfList(ByVal aList As ArrayList) As UInt32
    Const mask As UInt16 = 32767, hashPrime As Integer = Integer.MaxValue
    Dim retval As UInt32
    Dim ch() As Char = New Char() {}
    For idx As Integer = 0 To aList.Count - 1
        ch = DirectCast(aList(idx), String).ToCharArray
        For idCH As Integer = 0 To ch.Length - 1
            retval = (retval And mask) + (Convert.ToUInt16(ch(idCH)) And mask)
        Next
    Next
    If retval > 0 Then retval = Convert.ToUInt32(hashPrime / retval) ''Else ????
    Return retval
End Function