Подтвердить что ты не робот

Получение хэша списка строк независимо от порядка

Я хотел бы написать функцию GetHashCodeOfList(), которая возвращает хеш-код списка строк независимо от порядка. Учитывая, что 2 списка с одинаковыми строками должны возвращать один и тот же хэш-код.

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.

У меня было несколько мыслей:

  • Я могу сначала отсортировать список, а затем объединить отсортированный список в 1 длинную строку, а затем вызвать GetHashCode(). Однако сортировка - медленная операция.

  • Я могу получить хэш каждой отдельной строки (вызывая string.GetHashCode()) в списке, затем умножая все хэши и вызывая Mod UInt32.MaxValue. Например: "String1".GetHashCode() * "String2".GetHashCode * … MOD UInt32.MaxValue. Но это приводит к переполнению числа.

Есть ли у кого-нибудь мысли?

Заранее благодарим за помощь.

4b9b3361

ОТВЕТЫ

Ответ 1

Здесь существуют различные подходы к двум основным категориям, каждая из которых, как правило, имеет свои преимущества и недостатки с точки зрения эффективности и производительности. Вероятно, лучше выбрать самый простой алгоритм для любого приложения и использовать только более сложные варианты, если это необходимо для любой ситуации.

Обратите внимание, что в этих примерах используется EqualityComparer<T>.Default поскольку он будет чисто работать с нулевыми элементами. Вы можете сделать лучше, чем ноль для нуля, если хотите. Если T ограничен для структурирования, это также не нужно. При желании вы можете EqualityComparer<T>.Default поиск EqualityComparer<T>.Default из функции.

Коммутативные Операции

Если вы используете операции с хеш-кодами отдельных записей, которые являются коммутативными, то это приведет к одному и тому же конечному результату независимо от порядка.

Есть несколько очевидных вариантов чисел:

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;
}

Недостатком этого является то, что хеш для {"x", "x"} такой же, как хеш для {"y", "y"}. Если это не проблема для вашей ситуации, возможно, это самое простое решение.

прибавление

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;
}

Переполнение здесь хорошо, отсюда явный unchecked контекст.

Есть еще несколько неприятных случаев (например, {1, -1} и {2, -2}, но с большей вероятностью все будет хорошо, особенно со строками. В случае списков, которые могут содержать такие целые числа, вы всегда можете реализовать пользовательскую функцию хеширования (возможно, такую, которая принимает индекс повторения определенного значения в качестве параметра и, соответственно, возвращает уникальный хэш-код).

Вот пример такого алгоритма, который довольно эффективно справляется с вышеупомянутой проблемой. Он также имеет преимущество, заключающееся в значительном увеличении распространения сгенерированных хеш-кодов (см. Статью, приведенную в конце для некоторых пояснений). Математический/статистический анализ того, как именно этот алгоритм генерирует "лучшие" хеш-коды, был бы довольно продвинутым, но тестирование его в широком диапазоне входных значений и построение графиков результатов должно подтвердить это достаточно хорошо.

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;
}

умножение

Который имеет мало преимуществ по сравнению с сложением: небольшие числа и сочетание положительных и отрицательных чисел могут привести к лучшему распределению хэш-битов. В качестве отрицательного значения для смещения эта "1" становится бесполезной записью, ничего не вносящей, и любой нулевой элемент приводит к нулю. Вы можете установить нулевой специальный случай, чтобы не вызывать этого серьезного недостатка.

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;
}

Заказ первым

Другой основной подход заключается в том, чтобы сначала навести порядок, а затем использовать любую функцию хеширования, которая вам нравится. Сам порядок не имеет значения, если он последовательный.

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;
}

Это имеет некоторые существенные преимущества в том, что операции объединения, возможные в f могут иметь значительно лучшие свойства хеширования (например, распределение битов), но это происходит при значительно более высокой стоимости. Сортировка O(n log n) а требуемая копия коллекции - это выделение памяти, которое вы не можете избежать, если хотите избежать изменения оригинала. Реализации GetHashCode должны обычно полностью избегать выделения. Одна из возможных реализаций f была бы аналогична приведенной в последнем примере в разделе "Добавление" (например, любое оставшееся число битовых сдвигов влево с последующим умножением на простое число - вы могли бы даже использовать последовательные простые числа на каждой итерации без дополнительных затрат, так как они должны быть сгенерированы только один раз).

Тем не менее, если вы имели дело со случаями, когда вы можете вычислить и кэшировать хэш и амортизировать стоимость многих вызовов GetHashCode такой подход может привести к превосходному поведению. Кроме того, последний подход является еще более гибким, поскольку он позволяет избежать необходимости использовать GetHashCode для элементов, если он знает их тип, и вместо этого использовать операции с байтами для них, чтобы обеспечить еще лучшее распределение хеша. Такой подход, вероятно, будет полезен только в тех случаях, когда производительность была определена как существенное узкое место.

Наконец, если вы хотите получить достаточно полный и довольно нематематический обзор предмета хэш-кодов и их эффективности в целом, эти посты в блоге были бы полезны для чтения, в частности пост "Реализация простого алгоритма хеширования (pt II)".

Ответ 2

Альтернативой сортировке списков строк будет получение хэш-кодов строк, а затем сортировка хэш-кодов. (Сравнение ints менее дорогое, чем сравнение строк.) Затем вы можете использовать алгоритм для объединения хеш-кодов, которые (надеюсь) дают лучшее распределение.

Пример:

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;
}

Ответ 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

Ответ 4

Гораздо меньше кода, но, возможно, производительность не так хороша, как другие ответы:

public static int GetOrderIndependentHashCode<T>(this IEnumerable<T> source)    
    => source == null ? 0 : HashSet<T>.CreateSetComparer().GetHashCode(new HashSet<T>(source));

Ответ 5

Вот гибридный подход. Он объединяет три коммутативные операции (XOR, сложение и умножение), применяя каждую в разных диапазонах 32-битного числа. Диапазон битов каждой операции регулируется.

public static int GetOrderIndependentHashCode<T>(IEnumerable<T> source)
{
    var comparer = EqualityComparer<T>.Default;
    const int XOR_BITS = 10;
    const int ADD_BITS = 11;
    const int MUL_BITS = 11;
    Debug.Assert(XOR_BITS + ADD_BITS + MUL_BITS == 32);
    int xor_total = 0;
    int add_total = 0;
    int mul_total = 17;
    unchecked
    {
        foreach (T element in source)
        {
            var hashcode = comparer.GetHashCode(element);
            int xor_part = hashcode >> (32 - XOR_BITS);
            int add_part = hashcode << XOR_BITS >> (32 - ADD_BITS);
            int mul_part = hashcode << (32 - MUL_BITS) >> (32 - MUL_BITS);
            xor_total = xor_total ^ xor_part;
            add_total = add_total + add_part;
            if (mul_part != 0) mul_total = mul_total * mul_part;
        }
        xor_total = xor_total % (1 << XOR_BITS); // Compact
        add_total = add_total % (1 << ADD_BITS); // Compact
        mul_total = mul_total - 17; // Subtract initial value
        mul_total = mul_total % (1 << MUL_BITS); // Compact
        int result = (xor_total << (32 - XOR_BITS)) + (add_total << XOR_BITS) + mul_total;
        return result;
    }
}

Производительность практически идентична простому методу XOR, потому что вызов GetHashCode каждого элемента доминирует над нагрузкой на процессор.