列表上的哈希函数与其中项目的顺序无关

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

例如key is [1 2 3] and value会有一定的价值。

事情是这样的[3 2 1]在我的情况下需要进行相同的处理，因此如果我采用散列方法，散列需要相等。

该套装将包含 2 至 10 件物品。

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

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

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

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

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

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

Basically all of the approaches here are instantiations of the same template. Map x₁, …, x_n to f(x₁) op … op f(x_n), where op is a commutative associative operation on some set X, and f is a map from items to X. This template has been used a couple of times in ways that are provably good.

• Choose a random large prime p and a random residue b in [1, p - 1]. Let f(x) = b^x mod p and let op be addition. We essentially interpret a set as a polynomial and use the Schwartz–Zippel lemma to bound the probability of a collision (= the probability that a nonzero polynomial has b as a root mod p).

• 令 op 为 XOR，令 f 为随机选择的表。这是Zobrist 哈希并通过简单的线性代数论证最小化预期的碰撞次数。

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

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

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