获取字符串列表的散列，而不考虑顺序
我想写一个函数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.我有一些想法：
- 我可以先对列表进行排序，然后将排序后的列表合并成一个长字符串，然后调用
GetHashCode()。但是排序是一个很慢的操作，我可以(通过调用string.GetHashCode())得到列表中每个单独字符串的哈希值，然后将所有哈希值相乘并调用 - 。例如：
"String1".GetHashCode() * "String2".GetHashCode * … MOD UInt32.MaxValue。但这会导致数字溢出。
有谁有什么想法吗？
提前感谢您的帮助。
回答 5
Stack Overflow用户
发布于 2009-03-21 21:52:17
这里有两个主要类别下的各种不同的方法，每种方法在有效性和性能方面通常都有自己的优点和缺点。对于任何应用程序，最好选择最简单的算法，只有在必要的情况下才使用更复杂的变体。
请注意，这些示例使用EqualityComparer<T>.Default，因为它将干净地处理空元素。如果需要，您可以对null执行比0更好的操作。如果T被约束为struct，那么它也是不必要的。如果需要，您可以将EqualityComparer<T>.Default查找提升到函数之外。
交换运算
如果您对单个条目的哈希码使用commutative操作，那么无论顺序如何，这都将导致相同的最终结果。
在数字上有几个明显的选项：
异或
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;
}Overflow在这里很好，因此是显式的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，而是对元素使用按字节操作，以产生更好的散列分布。这种方法可能只在性能被确定为严重瓶颈的情况下才有用。
最后，如果你想对散列代码的主题和它们的有效性有一个相当全面和相当非数学的概述，these blog posts是值得一读的，特别是实现一个简单的散列算法(pt II) post。
Stack Overflow用户
发布于 2009-03-21 23:20:19
对字符串列表进行排序的另一种方法是获取字符串的散列码，然后对散列码进行排序。(比较int比比较字符串的开销要小。)然后，您可以使用一种算法来合并散列代码(希望如此)，从而获得更好的分布。
示例：
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;
}Stack Overflow用户
发布于 2009-03-22 13:50:04
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 Functionhttps://stackoverflow.com/questions/670063
复制相似问题