对整数序列进行哈希处理

Question

我需要处理数字序列，其中一个序列具有以下特性:

• 元素是整数
• 序列长度变化且不固定
• 整数具有上限
• 允许元素有多个重复出现
• 元素的顺序无关紧要

给定一个序列，我想知道这个序列是否已经出现过，也就是我想对序列进行哈希。例如：

[2, 3, 6, 2, 13]

并且。

[6, 3, 2, 13, 2]

这些序列应该具有相同的哈希值。

所使用的编程语言是C。

我知道我可以先对序列进行排序，然后将它们存储在一棵trie中，这绝对是一个选项。然而，为此目的选择什么样的哈希函数会比较合适呢？

- Guybrush

---

所以它们更像是集合而不是序列，对吗？因为顺序并不重要？ - harold

一个普通的异或操作可能是一个合理的起点。 - Hot Licks

整数可能具有预先未知的上限... 如果集合有限且每个集合的大小都是有限的，则可以更具体地说明“整数肯定有一个上限...”。虽然我不完全确定这个事实是否与这个问题相关。一个想法是将每个集合放入某种规范形式（例如，对其进行排序），并生成一个良好的哈希值（MD5、SHA *，取决于您期望拥有多少）以抵抗碰撞，并存储它。 - twalberg

hash = a[0] xor a[1] xor a[2] xor a[3] xor ... - Hot Licks

需要注意的重要事情是，无论顺序如何，您都希望获得相同的哈希值。这意味着您需要一个无序敏感哈希，或者在哈希之前将元素放置在规范顺序（即排序）中。无序敏感哈希可以使用加法（带溢出），XOR和一些杂项位操作技术。通常设计为不无序敏感的“预制”哈希算法，这意味着您必须在应用它们之前进行排序。 - Hot Licks

Answer 1

要求元素的顺序不重要，这让我立刻想到了Zobrist hashing。也就是说，你需要一个将整数映射为随机二进制串的函数f，然后你的哈希值就是序列中每个数字对应的二进制串的异或和。

当然，上面描述的基本Zobrist哈希并不满足你另一个要求：

• 允许元素多次出现

因为异或操作是自反的（即对于任何a，都有a XOR a = 0）。然而，只需用一些其他环操作替换XOR，这些操作不具有此属性（在普通的Zobrist哈希中，实际上被认为是理想的），例如n位加法，就可以产生你所需的哈希值：

unsigned int hash_multiset (int *seq, int n) {
    unsigned int h = 0;
    while (n--) h += f( *seq++ );
    return h;
}

这个函数的一个细节需要注意，如果你想截断它的输出，最好使用高位而不是低位。这是因为，如果序列[a]和[b]的哈希值的k个最低位发生冲突，那么[a，a]，[b，b]，[a，b]等序列的k个最低位也会发生冲突。对于k个最高位，情况并非如此，因为较低位可以传递到较高位，产生更多“随机”的输出。

有各种方法来实现函数f。对于有限范围的输入整数，可以简单地使用固定的随机比特串查找表。或者，如果事先不知道输入的范围，可以使用另一个（普通的）哈希表将整数映射到随机比特串，并且只需在运行时构建它。

最后，也可以不使用查找表来实现f，只需使用一个固定的函数，它“看起来足够随机”。对于这样的函数，一个很好的选择是使用简单快速的块密码，例如TEA或（在具有硬件支持的系统上）AES，并将输出截断到您所选的哈希长度。

- Ilmari Karonen

---

这看起来非常有趣，谢谢。n = 序列的长度吗？ - Guybrush

是的。C数组不会存储它们自己的长度，因此你需要以某种方式将其传递给函数。 - Ilmari Karonen

Answer 2

如何将所有数字和序列长度相乘，对一些相当大的数字取模？以下是一些Scala代码，展示了计算过程：

val l = List(6, 3, 2, 13, 2)
(l.reduce(_ * _) * l.length) % 10000

这将导致：4680。

显然，这并不能保证哈希值匹配时序列是唯一的。（它甚至可能不是一个很好的近似！）然而，如果哈希值不匹配，则可以保证序列不相同。

- Stig Brautaset

---

这个想法的整数模组件几乎可以保证，如果我有10000个或更多序列，那么我将会有错误的碰撞。 - twalberg

谢谢，那似乎是一个选项。 - Guybrush

Answer 3

不考虑性能，如果你想要一些易于审查和可靠的东西，我会选择：

var sample = new [] { 11, 55, 12, 3 };
String.Join(" ", sample.OrderBy(i => i)).GetHashCode()

如果你考虑的是一个集合而不是一个序列，你可能想要添加一个调用 .Distinct() 的操作。

- Frank Schwieterman