Val*_*zub 4 c# algorithm hash-function
我想要一个为一组整数赋值的字典。
例如key是[1 2 3]并且value将具有一定的价值。
问题是[3 2 1]在我的情况下需要相同的处理，因此如果我采用哈希方法，哈希值必须相等。
该套装将有 2 到 10 个项目。
项目的总和通常是固定的，所以我们不能根据总和制作哈希码，这是这里的第一个自然想法。
不是家庭作业，实际上在我的代码中面临这个问题。
这个集合基本上是IEnumerable<int>在 C# 中，所以任何数据结构都可以存储它们。
任何帮助表示赞赏。性能在这里也很重要。
一个直接的想法：我们可以总结一下items^2，已经得到了一些更好的哈希，但我仍然想听听一些想法。
编辑：嗯，真的很抱歉各位，每个人都建议订购，我没想到我需要说实际订购和散列是我当前使用的解决方案，我正在考虑更快的替代方案。
基本上这里的所有方法都是相同模板的实例化。将 x 1 , …, x n映射到 f(x 1 ) op … op f(x n )，其中 op 是某个集合 X 上的可交换关联运算，f 是从项目到 X 的映射。这个模板已经被使用以证明是好的方式进行了几次。
在 [1, p - 1] 中选择一个随机的大素数 p 和一个随机残差 b。令 f(x) = b x mod p 并令 op 为加法。我们基本上将集合解释为多项式，并使用Schwartz-Zippel 引理来限制碰撞概率（= 非零多项式以 b 作为根 mod p 的概率）。
令 op 为 XOR，令 f 为随机选择的表。这是Zobrist 散列，并通过直接的线性代数参数最小化预期的冲突次数。
模幂运算很慢，所以不要使用它。至于 Zobrist 散列，有 300 万个项目，表 f 可能不适合 L2，尽管它确实设置了一次主内存访问的上限。
相反，我会将 Zobrist 散列作为出发点，并寻找一个行为类似于随机函数的廉价函数 f。这本质上是一个非加密伪随机生成器的工作描述——我会尝试通过用 x 播种一个快速 PRG 并生成一个值来计算 f。
编辑：假设集合都具有相同的总和，不要选择 f 为 1 次多项式（例如，线性同余生成器的阶跃函数）。