我曾尝试使用布隆过滤器进行会员资格测试。我希望对800亿个条目进行会员测试，只允许发生大约100次冲突，即只有100个条目可能会出现假阳性结果。布卢姆过滤器的替代品
我知道这可以通过布隆过滤器来实现，但是使用公式来确定每个条目所需的位数以及给定允许的误报率的哈希函数的数量。我想我最终会使用270 GB的内存和19个散列函数。
我也看过杜鹃过滤器，但其内存要求与我的要求不符。我的要求如下：在最大6位每个元素
有人可能会建议我一个概率数据结构，除了上面提到的可以帮助实现我的要求吗？
散列函数的数量问题并不是真正的问题 - 只需选择一个具有多位输出的散列函数，并将这些位分成好几个位，就好像它们来自单独的散列函数一样。这里真正的问题是存储空间的误报率。
你说
我想只有 允许大约100碰撞发生，即只有100个条目可以 给出假阳性结果80个十亿条目执行成员测试。
根据定义，地图中的条目可以不是false肯定。他们是true positives。
接下来的问题是“你打算测试多少个条目 需要100个误报？”如果答案奇怪的话，也就是800亿，那么你就要求大约100/80,000,000,000 = 1/800,000,000，小于2^-29的假阳性率。
布鲁姆滤波器或布谷鸟滤波器等任何近似成员数据结构的最小空间是n lg 1 /ε位，其中n是结构中元素的数量，lg是对数基2，ε是假阳性率。换句话说，每个元素需要超过29位才能达到每800亿100个假阳性率。每个元素6位会得到1.56％的假阳性率最多为。这是每80亿十亿12.5亿，或每6400 100.
据我所知，没有已知的实际数据结构接近实现这一目标。例如，布卢姆过滤器不会，因为他们使用每个项目超过lg 1 /ε比特。杜鹃过滤器并不是因为它们每个项目至少使用了两个额外的元数据位，并且具有与lg n一致的每项比特率。
我知道在我的情况下内存要求会更多。但是，使用单个散列函数并分割位的建议很有趣。你有没有实现过这一点，发现结果与使用单独的散列函数得到的结果相似？ –
是的，我已经实现了这一点，它很好。但是，它不适用于低质量的哈希族。这个边界太小而不能包含更完整的答案，但是请阅读vhash，通用哈希，SipHash和类似的东西。 – jbapple
您似乎不太可能找到任何数据结构，即使您没有对数字进行限制，也只能使用60千兆字节，这样您就可以区分800亿个项目，误判率为.00000000125，仅使用60 GB的散列函数。我没有数学来证明它，但它在我看来像是在推动理论上可能的界限。 –
好的，如果我增加了自己的记忆，或者我的误报率高达1％，那么布隆过滤器是一个很好的选择，还是有其他概率数据结构可以作为更好的选择吗？ –