获取k方向独立哈希函数
vvk*_*itk 5 algorithm hash hash-function
我需要使用一个散列函数，该函数属于一个由k个独立散列函数组成的家族。C，C ++或python中任何库或工具包上的任何指针都可以生成一组k个独立的哈希函数，我可以从中选择一个函数。
背景：我正在尝试在此处实现此算法：http : //researcher.watson.ibm.com/researcher/files/us-dpwoodru/knw10b.pdf用于“不同元素”问题。
我看过这个线程：生成k个成对独立的哈希函数，其中提到使用Murmur哈希来生成成对独立的哈希函数。我想知道k方向独立哈希函数是否有任何相似之处。如果没有可用的方法，那么我有可能构造这样的一组k方向独立的哈希函数。
提前致谢。
最简单的k方向独立哈希函数（将正整数映射x < p到m存储桶之一）只是
其中p是一些大的随机引（2 61 -1将工作）和我是小于某些随机正整数p，一个0 > 0。
2位独立哈希：
h(x) = (ax + b) % p % m
再次，p是素数，a > 0，a,b < p（即a不能为零，但b可以当这是一个随机选择）
这些公式定义了哈希函数系列。如果您每次运行算法时都从相应的族中随机选择一个散列函数（即，如果您生成random a的和），则它们将起作用（理论上）b。
不存在“k-wise独立哈希函数”这样的东西。然而，存在 k 级独立的函数族。
提醒一下，如果从函数族中随机选取 h，并且任意选取 x_1 .. x_k 和 y_1 .. y_k，则函数族是 k 方向独立的，“对于所有 i，h(x_i) = y_i”的概率" 是 Y^-k，其中 Y 是从中选择 y_i 的共域的大小。
有一些函数族对于较小的 k（例如 2、3、4 和 5）来说是 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），并获取多项式 mod 2^32 的结果，我认为。这只是几乎 k 方向独立，但有时这足以完成分析。重新分析 KNW 算法以更改其哈希族并不容易。
要生成 k 次独立族的成员，请使用您最喜欢的随机数生成器随机选择函数。在多项式散列的情况下，这意味着选择a上面引用的 s。/dev/random应该足够了。
您提到的论文“不同元素问题的最优算法”是一篇很好的论文，已被引用多次。然而，它实现起来并不容易，而且由于大 O 表示法中隐藏的常量，它可能比 HyperLogLog 更慢，甚至占用更多空间。许多论文都指出了该算法的复杂性，甚至称其与 HyperLogLog 相比不可行。如果您想实现不同元素数量的估计器，您可以从早期的算法开始。如果您的目标是教育，那么事情就会很复杂。如果您的目标是实用性，那么您也希望远离 KNW，因为仅仅为了制作一些比 HyperLogLog 不那么实用的东西可能需要大量工作。
作为另一条建议，如果您想了解和理解此算法或其他使用哈希的随机算法，您可能应该忽略“仅使用 Murmur 哈希”或“从 xxhash 中选择 k 值”的建议。Murmur/xx 在实践中可能没问题，但它们不是 k-wise 独立族，并且本页上的一些建议甚至在语义上也不是格式良好的。例如，“如果您需要 k 个不同的哈希值，只需使用 k 个不同的种子重复使用相同的算法 k 次”与 k-wise 独立族无关。对于您想要实现的算法，您最终将应用哈希函数任意次数。您不需要“需要 k 个不同的哈希值”，您需要通过首先从 k 个独立的哈希族中随机选取，然后将所选函数应用于作为此类算法的输入的流密钥来生成 n 个不同的哈希值。
这是众多解决方案之一，但您可以使用以下开源哈希算法： https: //github.com/Cyan4973/xxHash
然后，要生成不同的哈希值，您只需提供不同的种子即可。
考虑主函数声明：
unsigned int XXH32 (const void* input, int len, unsigned int seed);
因此，如果您需要 k 个不同的哈希值，只需使用 k 个不同的种子重复使用相同的算法 k 次即可。