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

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

Примечание, которое эти примеры используют EqualityComparer<T>.Default, так как это будет иметь дело с пустыми элементами чисто. Вы могли добиться большего успеха, чем нуль для пустого указателя при желании. Если T ограничивается к структуре, это является также ненужным. Можно поднять 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 реализации должны обычно избегать выделений полностью. Одна возможная реализация [1 111] была бы подобна данному в последнем примере под разделом Addition (например, любое постоянное количество сдвигов разряда, оставленных сопровождаемыми умножением началом - Вы могли даже использовать последовательные начала на каждом повторении без дополнительной платы, так как они только должны быть сгенерированными однажды).

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

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