不pipe顺序如何获取string列表的哈希

我想写一个函数GetHashCodeOfList() ，它返回一个string列表的散列码，不pipe顺序如何。 给定2个具有相同string的列表应该返回相同的散列码。

 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. 我可以首先对列表进行sorting，然后将sorting后的列表合并为一个长string，然后调用GetHashCode() 。 但是sorting是一个缓慢的操作。

2. 我可以得到每个单个string的哈希值（通过调用string.GetHashCode() ）在列表中，然后乘以所有散列并调用Mod UInt32.MaxValue 。 例如： "String1".GetHashCode() * "String2".GetHashCode * … MOD UInt32.MaxValue 。 但是这会导致数字溢出。

有没有人有任何想法？

在此先感谢您的帮助。

Answer 1

这里有两种不同的方法，一种在效率和性能方面通常各有利弊。 对于任何应用而言，最好select最简单的algorithm，并且在任何情况下只使用更复杂的变体。

请注意，这些示例使用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”}的散列相同。 如果这对您的情况不是问题，那可能是最简单的解决scheme。

加成

 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}），但是更可能是正常的，特别是对于string。对于可能包含这样的整数的列表，自定义哈希函数（可能是将特定值的重复索引作为参数并相应地返回唯一的哈希码）。

这是一个以相当有效的方式解决上述问题的algorithm的例子。 它还具有大大增加生成的哈希码的分布的优点（参见最后链接的文章以作解释）。 对algorithm如何产生“更好”的散列码的math/统计分析将是相当先进的，但是在大范围的input值上testing它并绘制结果应该足够好地进行validation。

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

乘法

如果除了加法之外的好处很less：小数字和正数和负数的组合可能导致散列位的更好分布。 作为抵消这个“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; } 

先订购

另一个核心方法是先执行一些sorting，然后使用你喜欢的任何散列组合函数。 只要它是一致的，sorting本身是无关紧要的。

 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可能的组合操作可以具有明显更好的散列属性（例如位的分布），但是这带来了显着更高的成本。 sorting是O(n log n)和集合的需要副本是内存分配，你不能避免考虑到避免修改原来的愿望。 GetHashCode实现通常应该完全避免分配。 f一个可能的实现类似于在添加部分的最后一个例子中给出的（例如任何常数位移，然后乘以一个素数 – 甚至可以在每次迭代中使用连续的素数而不需要额外的成本，因为他们只需要生成一次）。

也就是说，如果你正在处理的情况下，你可以计算和caching的散列和分摊成本的GetHashCode很多调用这种方法可能会产生优越的行为。 后一种方法更加灵活，因为它可以避免在元素上使用GetHashCode （如果知道它们的types），而是使用每个字节操作来产生更好的散列分布。 这种方法很可能只在性能被认为是一个重大瓶颈的情况下才能使用。

最后，如果你想要一个相当全面和相当非math的哈希代码及其有效性的概述， 这些博客文章将是值得的阅读，特别是实施一个简单的哈希algorithm（第二期）后。

Answer 2

sortingstring列表的另一种方法是获取string的哈希码，然后对哈希码进行sorting。 （比较整数比比较string要便宜。）然后，您可以使用一种algorithm来合并散列码（希望），从而提供更好的分布。

例：

 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