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

问题描述 投票：61回答：5

我想写一个函数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.

我有几点想法：

  1. 我可以先对列表进行排序，然后将排序后的列表合并为1个长字符串，然后调用GetHashCode()。然而，排序是一个缓慢的操作。
  2. 我可以在列表中获取每个字符串的哈希值（通过调用string.GetHashCode()），然后乘以所有哈希值并调用Mod UInt32.MaxValue。例如："String1".GetHashCode() * "String2".GetHashCode * … MOD UInt32.MaxValue。但这会导致数字溢出。

有人有想法吗？

在此先感谢您的帮助。

c# .net vb.net string hash
5个回答
73
投票

在这两种主要类别中存在各种不同的方法，在效果和性能方面各自通常具有其自身的利弊。对于任何应用程序，最好选择最简单的算法，并且只在必要时才使用更复杂的变量。

请注意，这些示例使用EqualityComparer<T>.Default，因为它将干净地处理null元素。如果需要，你可以为null做零。如果T被约束为struct，那么也是不必要的。如果需要，您可以从函数中提升EqualityComparer<T>.Default查找。

交换操作

如果对commutative的各个条目的哈希码使用操作，那么无论顺序如何，这都将导致相同的最终结果。

数字上有几个明显的选项：

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”}的散列相同。如果这对您的情况不是问题，那么它可能是最简单的解决方案。

Addition

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

Multiplication

除了增加的好处之外几乎没有：小数字和正数和负数的混合它们可能导致更好的哈希比特分布。作为抵消的负值，这个“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的一个可能的实现类似于在Addition部分的最后一个例子中给出的（例如，任何恒定数量的位移，然后乘以素数 - 你甚至可以在每次迭代时使用连续的素数而无需额外的成本，因为它们只需要生成一次）。

也就是说，如果您正在处理可以计算和缓存哈希的情况，并通过许多调用GetHashCode来分摊成本，这种方法可能会产生优越的行为。后一种方法也更加灵活，因为如果它知道它们的类型，它可以避免在元素上使用GetHashCode，而是使用每个字节操作来产生更好的散列分布。这种方法可能仅在性能被确定为重大瓶颈的情况下才有用。

最后，如果您想要对哈希码的主题及其有效性进行相当全面且相当非数学的概述，那么these blog posts将值得一读，特别是实现一个简单的哈希算法（第二版）帖子。

21
投票

排序字符串列表的另一种方法是获取字符串的哈希码，然后对哈希码进行排序。 （比较整数比比较字符串要便宜。）然后，您可以使用算法来合并（希望）提供更好分布的哈希码。

例：

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;
}
0
投票
    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
0
投票

代码少得多但可能性能不如其他答案好：

public static int GetOrderIndependentHashCode<T>(this IEnumerable<T> source)    
    => source == null ? 0 : HashSet<T>.CreateSetComparer().GetHashCode(new HashSet<T>(source));
0
投票

这是一种混合方法。它结合了三个可交换操作（XOR，加法和乘法），将每个操作应用于32位数的不同范围。每个操作的位范围是可调的。

public static int GetOrderIndependentHashCode<T>(IEnumerable<T> source)
{
    var comparer = EqualityComparer<T>.Default;
    const int XOR_BITS = 10;
    const int ADD_BITS = 11;
    const int MUL_BITS = 11;
    Debug.Assert(XOR_BITS + ADD_BITS + MUL_BITS == 32);
    int xor_total = 0;
    int add_total = 0;
    int mul_total = 17;
    unchecked
    {
        foreach (T element in source)
        {
            var hashcode = comparer.GetHashCode(element);
            int xor_part = hashcode >> (32 - XOR_BITS);
            int add_part = hashcode << XOR_BITS >> (32 - ADD_BITS);
            int mul_part = hashcode << (32 - MUL_BITS) >> (32 - MUL_BITS);
            xor_total = xor_total ^ xor_part;
            add_total = add_total + add_part;
            if (mul_part != 0) mul_total = mul_total * mul_part;
        }
        xor_total = xor_total % (1 << XOR_BITS); // Compact
        add_total = add_total % (1 << ADD_BITS); // Compact
        mul_total = mul_total - 17; // Subtract initial value
        mul_total = mul_total % (1 << MUL_BITS); // Compact
        int result = (xor_total << (32 - XOR_BITS)) + (add_total << XOR_BITS) + mul_total;
        return result;
    }
}

性能几乎与简单的XOR方法相同，因为每个元素对GetHashCode的调用都支配着CPU的需求。

最新问题
© www.soinside.com 2019 - 2024. All rights reserved.