aki*_*iva 6 algorithm bloom-filter
据我了解，为了减少单个哈希冲突导致误报的布隆过滤器使用多个（k）哈希值。
使用 k 个数组（每个哈希算法一个）不是更有利吗？这样，如果同时存在许多输入键被算法 A 映射到相同的值并存储在同一个数组单元格中，然后另一个键被算法映射B 为相同值——这是一个有价值的信息，应该单独标记。我认为 k 个大小为 m/k 的数组应该比单个大小为 m 的数组给出更好的结果。我错了吗？
与你的直觉（和我的！）相反，你提出的数据结构实际上在查找时的误报率比布隆过滤器（假设完美的哈希函数）稍差，因为你已经消除了自冲突的可能性 - 即也就是说，您已经做到了，两个哈希函数在同一元素上运行永远不会返回相同的数组索引。这听起来像是一件好事，但实际上很糟糕，因为这意味着平均而言，您建议的数据结构（以下称为“Akiva 过滤器”）中将设置比 Bloom 中设置的更多位相同大小、哈希函数数量和元素数量的过滤器。
\n为了清楚地看出消除自碰撞有多么糟糕，让我们首先考虑极端（且不切实际）的情况：
\n假设我们想要检查其他值y是否是过滤器的成员。
\n如果我们的过滤器是布隆过滤器，那么当我们添加x时，我们有 25% 的机会遇到幸运的哈希冲突- 即h\xe2\x82\x81 ( x ) = h\xe2\x82\x82 ( x )所以过滤器只有 1 位设置。如果是这种情况，那么当我们查找y时出现误报的几率很低 - 只有 0.25 * 0.25 = 0.0625。另一方面，如果我们运气不好并且h\xe2\x82\x81 ( x ) \xe2\x89\xa0 h\xe2\x82\x82 ( x ) （即我们的布隆过滤器中的两个位被设置），那么我们的当我们查找y时出现误报的可能性是 0.5 * 0.5 = 0.25。因此，我们的总体误报概率为 0.25 * 0.0625 + 0.75 * 0.25 = 0.203125。
\n另一方面，如果我们的过滤器是 Akiva 过滤器，分成两个大小为m / k =2 的数组，那么在添加元素x后有 100% 的机会设置两个位 - 一个位于第一个子数组中第二个有一个。因此，当我们查找y时出现误报的几率恰好是 25%。
\n我们能否证明，无论m（数据结构中的位数）、k（哈希函数的数量）的值如何，Akiva 过滤器的误报率通常都比 Bloom 过滤器差和n（已添加到过滤器的元素数量）？是的; 为此，我们首先将每个数据结构的误报概率确定为m、k和n的表达式。
\n让我们从 Akiva 滤镜开始。我们查找我们正在查找的元素的k 个不同的子数组索引，并且每个索引都有一个（完全独立的） 1 - (1 - k / m ) \xe2\x81\xbf已经被设置的机会，所以我们的误报的总体几率为 (1 - (1 - k / m ) \xe2\x81\xbf ) \xe1\xb5\x8f。
\n接下来，我们考虑布隆过滤器。在这里我们可以推迟一些已发表的奖学金：
\n\n\n在布隆过滤器误报率的分析中，通常假设哈希函数是完美的，它们为每个对象生成独立且随机的索引值，因此误报率只是m、n和k的函数。\xe2\x80\x9cclassic\xe2\x80\x9d 布隆过滤器误报率分析如下。...从一个对象的映射中插入k位后未设置任意位的概率为 (1\xe2\x88\x921/ m ) \xe1\xb5\x8f。对于映射入的n 个对象，任意位未设置的概率为 (1 \xe2\x88\x92 1/ m ) \xe1\xb5\x8f\xe2\x81\xbf，因此任意位为集合为p set = 1 - (1 \xe2\x88\x92 1/ m ) \xe1\xb5\x8f\xe2\x81\xbf。因此，对于未映射到布隆过滤器中的测试对象的k 个哈希值，误报的概率为（我们称之为 \xe2\x80\x9c 经典公式 \xe2\x80\x9d），
\np false = p设置\xe1\xb5\x8f = (1 - (1 \xe2\x88\x92 1/ m ) \xe1\xb5\x8f\xe2\x81\xbf ) \xe1\xb5\x8f
\n
因此，Akiva 滤波器的误报概率为 (1 - (1 - k / m ) \xe2\x81\xbf ) \xe1\xb5\x8f和 (1 - (1 \xe2\x88\x92 1/ m ) \xe1\xb5\x8f\xe2\x81\xbf ) \xe1\xb5\x8f用于布隆过滤器；但前者什么时候更大呢？答案是，对于k \xe2\x89\xa5 2， Akiva 过滤器的误报率严格更大（更差） ，无论m或n的值如何。为了证明这一点，我们首先观察我们想要证明的不等式， (1 - (1 - k / m ) \xe2\x81\xbf ) \xe1\xb5\x8f > (1 - (1 \xe2\x88\x92 1/ m ) \xe1\xb5\x8f\xe2\x81\xbf ) \xe1\xb5\x8f，相当于一个更简单的不等式，通过执行以下转换：
\n最后我们可以很容易证明 1 - k / m < (1 \xe2\x88\x92 1/ m ) \xe1\xb5\x8f对于所有 k\xe2\x89\xa52 通过首先观察这对于 k=2 是正确的：
\n1 - 2/米< 1 - 2/米+ 1/米\xc2\xb2 = (1 \xe2\x88\x92 1/米) \xe1\xb5\x8f
\n...然后通过归纳进行。假设 (1 - ( k -1)/ m ) < (1 \xe2\x88\x92 1/ m ) k -1。那么我们可以将 (1 \xe2\x88\x92 1/ m ) k -1表示为 (1 - ( k -1)/ m ) + \xce\xb5，对于某些\xce\xb5 >0。然后
\n(1 \xe2\x88\x92 1/米) \xe1\xb5\x8f
\n= (1 - 1/米)(1 - ( k -1)/米+ \xce\xb5 )
\n= 1 - ( k -1)/ m + \xce\xb5 - 1/ m + ( k -1)/ m \xc2\xb2 - \xce\xb5 / m
\n= 1 - k /m + (1 - 1/ m ) \xce\xb5 + ( k -1)/ m \xc2\xb2
\n> 1 - k /m
量子ED。
\n伯顿·霍华德·布鲁姆似乎知道自己在做什么；与您考虑使用k 的替代结构相比，布隆过滤器的误报率更低，因此更优越。
\n