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

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

обратите внимание, что в этих примерах используется EqualityComparer<T>.Default так как это будет иметь дело с нулевыми элементами чисто. При желании вы можете сделать лучше, чем ноль для null. Если 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" становится бесполезной записью, ничего не вносящей, и любой нулевой элемент приводит к a нуль. Вы можете специальный случай ноль, чтобы не вызвать этот главный недостаток.

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) пост.