列表上的哈希函数独立于其中的项目顺序

我想要一个字典，为一组整数赋值。

例如， key是[1 2 3] ， value将具有特定值。

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

该套装将有2到10件物品。

项目总和通常是固定的，因此我们不能根据总和制作哈希码，这是第一个自然的想法。

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

这个集合基本上是C＃中的IEnumerable ，所以任何数据结构都可以存储它们。

任何帮助赞赏。 性能在这里也非常重要。

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

编辑：嗯真的很抱歉伙计们 ，每个人都建议订购，我没想到我需要说实际订购和散列是我使用的当前解决方案，我正在考虑更快的替代品。

Answer 1

基本上，这里的所有方法都是同一模板的实例化。 将x ₁ ，…，x _n映射到f（x ₁ ）op … op f（x _n ），其中op是某些集合X上的可交换关联运算，f是从项目到X的映射。此模板已被使用有几次certificate是好的方式。

• 在[1，p – 1]中选择随机大素数p和随机残基b。 设f（x）= b ^x mod p，并将op加法。 我们基本上将一个集合解释为多项式，并使用Schwartz-Zippel引理来约束碰撞的概率（=非零多项式将b作为根mod p的概率）。

• 让op为XOR，让f为随机选择的表。 这是Zobrist散列并通过简单的线性代数参数最小化期望碰撞的数量。

模幂运算很慢，所以不要使用它。 对于具有300万个项目的Zobrist散列，表f可能不适合L2，尽管它确实设置了一个主存储器访问的上限。

我会把Zobrist散列作为一个出发点，寻找一个行为类似于随机函数的廉价函数f。 这本质上是非加密伪随机生成器的工作描述 – 我会尝试通过用x播种快速PRG并生成一个值来计算f。

编辑：假设集合都具有相同的总和，不要选择f为1次多项式（例如，线性同余生成器的阶跃函数）。

Answer 2

使用HashSet和HashSet.CreateSetComparer() ，它返回IEqualityComparer> 。

Answer 3

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

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

增量Multiset Hash函数及其在内存完整性检查中的应用

摘要：我们引入了一种新的加密工具：多集哈希函数。 与将字符串作为输入的标准散列函数不同，多集散列函数在多集（或集）上运行。 它们将任意有限大小的多重集合映射到固定长度的字符串（散列）。 它们是渐进式的，当新成员添加到多集中时，哈希可以及时更新，与更改成比例。 这些函数可能是多重冲突抵抗的，因为它很难找到产生相同散列的两个多重集，或者只是设置冲突抵抗，因为它很难找到产生相同散列的集合和多集合。

Answer 4

我认为你的平方思想正朝着正确的方向发展，但function选择不佳。 我会尝试更像PRNG函数或只是乘以一个大素数，然后是所有结果值的XOR。

Answer 5

一种可能性：对列表中的项进行排序，然后对其进行哈希处理。

Answer 6

您可以对数字进行排序并从预定的索引中选择样本，如果当前值的数字较少，则将其余为零。 或者你可以和他们或其他什么相关。

Answer 7

为什么不喜欢

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

Answer 8

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

使用问题中的示例：

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

Answer 9

创建自己的类型，实现IEnumerable 。

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