hash - 散列整数序列

Question

我必须处理数字序列，其中序列具有以下属性：

• 元素是整数，
• 序列的长度不同且不固定，
• 整数有一个上限，
• 允许多次出现元素，
• 元素的顺序无关紧要。

给定一个序列，我想知道这个序列是否已经发生，即我想对序列进行哈希处理。例如，

[2, 3, 6, 2, 13]

和

[6, 3, 2, 13, 2]

应该具有相同的哈希值。

使用的编程语言是 C。

我知道我可以先对序列进行排序，然后将它们存储在 trie 中，这绝对是一种选择。然而，为此目的合适的散列函数是什么？

Answer 1

要求

• 元素的顺序无关紧要

让我立刻想到了Zobrist hashing之类的东西。也就是说，您将有一个f将整数映射到随机位串的函数，并且您的哈希将只是与序列中的数字相对应的位串的 XOR。

当然，上面描述的基本 Zobrist 散列不能满足您的其他要求

• 允许多次出现元素

因为 XOR 操作是它自己的逆操作（即a XOR a = 0对于 any a）。然而，简单地将 XOR 替换为没有此属性的其他环操作（在正常的 Zobrist 散列中，这实际上被认为是可取的），例如n位加法，应该会产生您想要的散列：

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

（关于这个函数需要注意的一个小细节是，如果你想截断它的输出，使用高位比使用低位稍微好一点。这是因为，如果序列的哈希值的k个最低位发生冲突，那么 , 的k个最低位也是如此。对于k个最高位，这是不正确的，因为较低的位可以转移到较高的位，从而产生更多“随机”的输出。）[a][b][a, a][b, b][a, b]

有多种方法可以实现该功能f。对于有限范围的输入整数，您可以简单地使用随机位串的固定查找表。或者，如果您事先不知道输入的范围，您可以使用另一个（普通）哈希表将整数映射到随机位串，然后“即时”构建它。

最后，它也可以在f 没有查找表的情况下实现，只需使用“看起来足够随机”的固定函数即可。这种函数的一个不错的选择是使用简单而快速的分组密码，例如TEA或（在硬件支持的系统上）AES，输出截断为您喜欢的哈希长度。

Answer 2

将所有数字和序列的长度相乘，以某个相当大的数字为模，怎么样？下面是一些显示计算的 Scala 代码：

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

结果为：4680。

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