列表上的哈希函数与列表中元素的顺序无关

本文关键字：列表 顺序 元素 哈希 函数 | 更新日期: 2023-09-27 18:15:13

我想要有一个给一组整数赋值的字典。

例如key为[1 2 3], value有一定的值。

问题是[3 2 1]需要在我的情况下被同样对待，所以哈希需要是相等的，如果我用哈希方法。

该集合将有2到10个项目。

项目的总和通常是固定的，所以我们不能根据Sum来创建哈希码，这是这里的第一个自然想法。

不是作业，实际上在我的代码中遇到了这个问题。

这个集合在c#中基本上是IEnumerable<int>，所以任何数据结构都可以很好地存储它们。

感谢任何帮助。性能在这里也很重要。

一个直接的想法:我们可以总结items^2，并且已经得到了一些更好的哈希，但我仍然想听到一些想法。

编辑:嗯真的很抱歉伙计们，每个人都建议排序，我没有想到我需要说实际上排序和哈希是我目前使用的解决方案，我正在考虑更快的替代方案。

列表上的哈希函数与列表中元素的顺序无关

基本上这里所有的方法都是同一个模板的实例化。映射x1，…，xn到f(x1) op…op f(xn)，其中op是某个集合x上的交换关联运算，f是从项到x的映射。这个模板已经用过几次，证明是好的。

  • 在[1,p - 1]中随机选取一个大素数p和一个随机残数b。令f(x) = bx mod p，令op为加法。我们本质上将一个集合解释为一个多项式，并使用Schwartz-Zippel引理来限定碰撞的概率(=一个非零多项式以b为根模p的概率)。

  • 设op为异或，设f为随机选择的表。这是Zobrist哈希，并通过直接的线性代数参数最小化碰撞的期望数量。

模幂运算很慢，所以不要使用它。至于Zobrist哈希，有300万项，表f可能不适合L2，尽管它确实设置了一次主存访问的上限。

我会把Zobrist哈希作为出发点，寻找一个行为像随机函数的便宜函数f。这本质上是一个非加密伪随机生成器的工作描述——我将尝试通过用x播种一个快速PRG并生成一个值来计算f。

编辑:如果集合的和相同，则不选择f为1次多项式(例如线性同余生成器的阶跃函数)

使用HashSet<T>和HashSet<T>.CreateSetComparer()，返回IEqualityComparer<HashSet<T>>

我认为本文中提到的内容肯定会有所帮助:

http://people.csail.mit.edu/devadas/pubs/mhashes.pdf

增量多集哈希函数及其在内存完整性检查中的应用

摘要:介绍了一种新的加密工具:多集哈希函数。与接受字符串作为输入的标准哈希函数不同，multiset哈希函数对多个集合(或多个集合)进行操作。它们将任意有限大小的多集映射到固定长度的字符串(哈希)。它们是增量的，因为当新成员被添加到multiset中时，哈希值可以按照变化的比例及时更新。这些函数可能是抗多集冲突的，因为很难找到产生相同哈希值的两个多集，或者仅仅是抗多集冲突的，因为很难找到产生相同哈希值的一个集和一个多集。

我认为你的平方的想法是正确的方向，但一个糟糕的功能选择。我会尝试一些更像PRNG函数的东西，或者只是乘以一个大素数，然后对所有结果值进行异或。

如果key中的值的范围恰好限于小正整数，则可以使用简单查找将每个值映射为素数，然后将它们相乘得到value。

用问题中的例子:

[1, 2, 3] maps to 2 x 3 x 5 = 30
[3, 2, 1] maps to 5 x 3 x 2 = 30

一种可能:对列表中的项进行排序，然后对其进行散列。

您可以对数字进行排序，并从预定的索引中选择一个样本，如果当前值的数字较少，则将其余部分保留为零。或者你可以用xor或者其他的

为什么不像

public int GetOrderIndependantHashCode(IEnumerable<int> source)
{
    return (source.Select(x => x*x).Sum()
            + source.Select(x => x*x*x).Sum()
            + source.Select(x => x*x*x*x).Sum()) & 0x7FFFFF;
}

创建您自己的实现IEnumerable<T>的类型。

覆盖GetHashCode。在其中，对您的集合进行排序，调用并返回ToArray().GetHashCode()。

相关文章：