4

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

例如key是[1 2 3]并且value将具有一定的价值。

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

该套装将有 2 到 10 个项目。

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

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

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

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

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

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

4

9 回答 9

5

基本上这里所有的方法都是同一个模板的实例化。将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 次多项式（例如，线性同余生成器的阶跃函数）。

于 2011-11-18T22:03:28.857 回答
2

使用HashSet<T>and HashSet<T>.CreateSetComparer()，它返回一个IEqualityComparer<HashSet<T>>.

于 2011-11-18T20:50:09.960 回答
2

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

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

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

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

于 2011-11-18T20:56:23.890 回答
1

我认为您的平方想法朝着正确的方向发展，但功能选择不佳。我会尝试更像 PRNG 函数的东西，或者只是乘以一个大素数，然后对所有结果值进行 XOR。

于 2011-11-18T20:59:31.237 回答
1

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

使用问题中的示例：

[1, 2, 3] maps to 2 x 3 x 5 = 30
[3, 2, 1] maps to 5 x 3 x 2 = 30
于 2017-03-24T21:29:51.093 回答
0

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

于 2011-11-18T20:48:43.990 回答
0

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

于 2011-11-18T20:50:32.473 回答
0

为什么不喜欢

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;
}
于 2011-11-18T21:43:18.930 回答
-1

创建您自己的实现IEnumerable<T>.

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

于 2011-11-18T20:48:37.963 回答