无论顺序如何，获取字符串列表的哈希

无论顺序如何，获取字符串列表的哈希

在以下两个主要类别中，存在各种不同的方法，就有效性和性能而言，每种方法通常都有各自的优点和缺点。对于任何应用程序，最好选择最简单的算法，并且在任何情况下都仅在需要时才使用更复杂的变体。

请注意，这些示例使用了，

EqualityComparer<T>.Default

因为这将干净地处理null元素。如果需要，对于空值，您可以做得比零更好。如果将T约束为结构，则也没有必要。如果需要，可以将

EqualityComparer<T>.Default

查找从函数中取消。

交换运算

如果对可交换的单个条目的哈希码使用运算，则无论顺序如何，这将导致相同的最终结果。

有几种明显的数字选项：

异或

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 pre 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/pre you like returning int        hash = f(hash, element);    }    return hash;}

这具有一些显着的优点，因为可能的合并 *** 作

f

可以具有明显更好的哈希属性（例如，位的分布），但是这样做的成本要高得多。排序是，

O(n logn)

并且集合的必需副本是内存分配，如果您希望避免修改原始数据，则无法避免。

GetHashCode

实现通常应完全避免分配。的一种可能的实现方式

f

将与上一个示例在“加法”部分下的最后一个示例中给出的实现类似（例如，保留任意恒定的位数，然后再乘以质数）-您甚至可以在每次迭代中使用连续质数而无需额外费用，因为它们只需要生成一次）。

就是说，如果您要处理的情况是可以计算和缓存哈希，并在多次调用

GetHashCode

此方法的情况下分摊费用，则可能会产生出众的行为。同样，后一种方法更加灵活，因为

GetHashCode

如果它知道元素的类型，就可以避免使用on元素，而是对它们使用每字节 *** 作以获得更好的哈希分布。仅在性能被确定为重大瓶颈的情况下，这种方法才可能有用。

最后，如果您希望对散列码的主题及其总体效果进行合理的全面且非数学的概述，那么这些博客文章将是值得阅读的，尤其是《 实现简单的散列算法（pt II）》一文 。