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

我想编写一个函数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个长字符串然后调用GetHashCode().然而,排序是一个缓慢的操作.

我可以在列表中获取每个字符串的哈希值(通过调用string.GetHashCode()),然后乘以所有哈希值并调用Mod UInt32.MaxValue.例如:"String1".GetHashCode() * "String2".GetHashCode * … MOD UInt32.MaxValue.但这会导致数字溢出.

有人有想法吗？

在此先感谢您的帮助.

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

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

交换操作

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

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

XOR

public static int GetOrderIndependentHashCode(IEnumerable source)
{
    int hash = 0;
    foreach (T element in source)
    {
        hash = hash ^ EqualityComparer.Default.GetHashCode(element);
    }
    return hash;
}

其中一个缺点是{"x","x"}的散列与{"y","y"}的散列相同.如果这对您的情况不是问题,那么它可能是最简单的解决方案.

加成

public static int GetOrderIndependentHashCode(IEnumerable source)
{
    int hash = 0;
    foreach (T element in source)
    {
        hash = unchecked (hash + 
            EqualityComparer.Default.GetHashCode(element));
    }
    return hash;
}

这里溢出很好,因此显式unchecked上下文.

仍然存在一些令人讨厌的情况(例如{1,-1}和{2,-2},但它更可能是正常的,特别是对于字符串.对于可能包含此类整数的列表,您可以始终实现自定义散列函数(可能是将特定值的重复索引作为参数并相应地返回唯一散列码的函数).

以下是以相当有效的方式解决上述问题的这种算法的示例.它还具有大大增加所生成的哈希码分布的好处(参见最后链接的文章以获得一些解释).对该算法如何产生"更好"的哈希码的数学/统计分析将是非常先进的,但是在大范围的输入值上测试它并绘制结果应该足够好地验证它.

public static int GetOrderIndependentHashCode(IEnumerable source)
{
    int hash = 0;
    int curHash;
    int bitOffset = 0;
    // Stores number of occurences so far of each value.
    var valueCounts = new Dictionary();

    foreach (T element in source)
    {
        curHash = EqualityComparer.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(IEnumerable source)
{
    int hash = 17;
    foreach (T element in source)
    {
        int h = EqualityComparer.Default.GetHashCode(element);
        if (h != 0)
            hash = unchecked (hash * h);
    }
    return hash;
}

先订购

另一个核心方法是首先强制执行某些排序,然后使用您喜欢的任何散列组合函数.只要它是一致的,排序本身并不重要.

public static int GetOrderIndependentHashCode(IEnumerable source)
{
    int hash = 0;
    foreach (T element in source.OrderBy(x => x, Comparer.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元素知道其类型时使用元素,而是对它们使用每字节操作以产生更好的散列分布.这种方法可能仅在性能被确定为重大瓶颈的情况下才有用.

最后,如果您想要对哈希码的主题及其有效性进行相当全面且相当非数学的概述,那么这些博客文章将值得一读,特别是实现一个简单的哈希算法(第二页)帖子.

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

例:

GetHashCodeOfList(IEnumerable list) {
   List codes = new List();
   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;
}