6

我需要使用属于 k-wise 独立散列函数家族的散列函数。C、C++ 或 python 中任何库或工具包上的任何指针，它们可以生成一组 k-wise 独立散列函数，我可以从中选择一个函数。

背景：我正在尝试在此处实现此算法：http ://researcher.watson.ibm.com/researcher/files/us-dpwoodru/knw10b.pdf用于不同元素问题。

我看过这个线程：生成 k 成对独立哈希函数，其中提到使用 Murmur 哈希生成成对独立哈希函数。我想知道 k-wise 独立散列函数是否有类似的东西。如果没有可用的，我是否有可能构造这样一组 k-wise 独立散列函数。

提前致谢。

4

5 回答 5

10

最简单的 k 向独立散列函数（将正整数映射x < p到m桶之一）只是

H

其中p是一些大的随机素数（2 61 -1 将起作用）并且 a i是一些小于 的随机正整数p，a 0 > 0。

2-wise 独立哈希： h(x) = (ax + b) % p % m

再次，p是素数，，a > 0（a,b < p即a不能为零，但b可以是随机选择）

这些公式定义了哈希函数族。如果您在每次运行算法时从相应的族中随机选择一个哈希函数（即，如果您生成随机a的 和），它们（理论上）就会起作用。b

于 2016-11-12T17:13:25.263 回答
5

不存在“k 向独立散列函数”之类的东西。但是，有 k 方向独立的函数族。

提醒一下，如果从族中随机挑选 h 并且任意挑选 x_1 .. x_k 和 y_1 .. y_k ，则函数族是 k 向独立的，“对于所有 i，h(x_i) = y_i " 是 Y^-k，其中 Y 是从中选择 y_i 的共域的大小。

已知有一些函数族对于像 2、3、4 和 5 这样的小 k 是 k 方向独立的。对于任意 k，您可能需要使用多项式哈希。请注意，它有两种变体，其中一种甚至不是 2 独立的，因此在实现它时要小心。

多项式散列族可以使用 k 常数 a_0 到 a_{k-1} 从字段 F 散列到自身，并由 a_i x^i 之和定义，其中 x 是您要散列的键。通过让 F 为以素数 p 为模的整数，可以在您的计算机上实现域算术。这可能不方便，因为域和范围通常更好uint32_t之类的。在这种情况下，您可以使用字段 F_{2^32}，您可以使用 Z_2 上的多项式乘法，然后除以该字段中的不可约多项式。否则，您可以在 Z_p 中操作，其中 p 大于 2^32（或 64）并取多项式模 2^32 的结果，我认为。这将几乎是k-wise独立的，但有时这足以让分析通过。重新分析 KNW 算法以改变其哈希族并不容易。

要生成 k-wise 独立族的成员，请使用您最喜欢的随机数生成器随机选择函数。在多项式哈希的情况下，这意味着选择a上面提到的 s。/dev/random应该足够了。

您指向的论文“An Optimal Algorithm for the Distinct Elements Problem”是一篇不错的论文，已被多次引用。然而，它并不容易实现，而且它可能比 HyperLogLog 更慢甚至占用更多空间，这是由于 big-O 符号中的隐藏常量。许多论文已经注意到该算法的复杂性，甚至称其与 HyperLogLog 相比是不可行的。如果您想为不同元素的数量实现估计器，您可以从早期的算法开始。如果您的目标是教育，那么那里有很多复杂性。如果您的目标是实用性，那么您也希望远离 KNW，因为仅仅为了让 HyperLogLog 不太实用可能需要做很多工作。

作为另一条建议，如果您想了解和理解此算法或其他使用散列的随机算法，您可能应该忽略“仅使用 Murmur 散列”或“从 xxhash 中选择 k 值”的建议。Murmur/xx 在实践中可能没问题，但它们不是 k-wise 独立的族，并且此页面上的一些建议甚至在语义上都不是格式正确的。例如，“如果你需要 k 个不同的散列，只需重复使用相同的算法 k 次，使用 k 个不同的种子”与 k-wise 独立族无关。对于您要实现的此算法，您最终将应用散列函数任意次数。你不需要“需要 k 个不同的哈希”，你需要n通过首先从与 k 无关的散列系列中随机选取，然后将所选函数应用于作为此类算法输入的流键，生成不同的散列值。

于 2016-11-13T05:22:30.783 回答
2

这是众多解决方案之一，但您可以使用例如以下开源哈希算法： https ://github.com/Cyan4973/xxHash

然后，要生成不同的哈希，您只需提供不同的种子。

考虑主函数声明：

unsigned int XXH32 (const void* input, int len, unsigned int seed);

因此，如果您需要 k 个不同的哈希值，只需使用 k 个不同的种子重复使用相同的算法 k 次。

于 2013-04-29T20:45:06.910 回答
1

只需使用一个好的非加密哈希函数。这个建议可能会让我在理论计算机科学领域的同事中不受欢迎，但请考虑一下你的对手。

  1. 自然。是的，也许它会遇到导致哈希函数表现不佳的小数输入，但是还有很多其他方法可以解决 k-wise 独立哈希族无法解决的问题（例如，随机数选择散列函数的生成器做得不好，有错误等），所以无论如何你都需要进行端到端的测试。

  2. 无知的对手。这就是理论所假设的。不经意的对手无法查看您的随机位。要是他们在现实生活中这么好就好了！

  3. 不可忽视的对手。随机性是没有意义的。使用二叉树。

于 2013-04-29T21:25:15.390 回答
-1

我不是 100% 确定您所说的“k 向独立散列函数”是什么意思，但是您可以通过提出两个散列函数，然后使用它们的线性组合来获得 k 个不同的散列函数。

我的布隆过滤器模块中有一个示例：http : //stromberg.dnsalias.org/svn/bloom-filter/trunk/bloom_filter_mod.py 忽略 get_bitno_seed_rnd 函数，查看 hash1、hash2 和 get_bitno_lin_comb

于 2013-04-29T20:36:20.017 回答