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

Question

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

例如key是[1 2 3]和 value会有一定的值(value)。

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

该集合将包含 2 到 10 个项目。

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

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

这套基本就是IEnumerable<int>在 C# 中，因此任何数据结构都可以存储它们。

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

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

编辑:嗯真的很抱歉大家，每个人都建议排序，但我没想到我需要说实际上排序和散列是我当前的解决方案使用并且我正在考虑更快的替代方案。

Answer 1

基本上这里所有的方法都是同一个模板的实例化。将 x₁, …, x_n 映射到 f(x₁) op … op f(x_n) ，其中 op 是某个集合 X 上的交换结合运算，f 是从项到 X 的映射。此模板已被多次使用，证明效果很好。

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

• 令 op 为 XOR，令 f 为随机选择的表。这是 Zobrist hashing并通过直接的线性代数论证最大限度地减少预期的碰撞次数。

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

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

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