bloom filter会在某些情况下总是返回误报吗？
bloom filter会在某些情况下总是返回误报吗？
提问于 2015-03-08 00:01:29
假设布隆过滤器api具有2个参数- 1.布隆过滤器中的比特数(n)和2.插入的预期数量(m)。
问题：
m > n是否总是会导致complete误报？通过complete，我想说的是，在m>n的条件下，是否会对“包含(元素)”方法的每一个测试都返回true？
回答 1
Stack Overflow用户
发布于 2015-04-17 17:53:03
当你的m> n时，bloom filter总是会回答yes，但当它的所有n位都是1时-那么h个位置的每个查询(其中h是散列函数的数量)将产生h个1。不过，优化空间与误报率权衡的典型设置是当设置任何位的概率为1/2时。分析显示在布隆过滤器维基百科文章：http://en.wikipedia.org/wiki/Bloom_filter
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/28916812
复制相关文章
相似问题
腾讯云开发者
