← 返回刚才阅读的位置

知识卡片

操作参考卡 · 5405

布隆参数按误判预算算

理解等级:中级

位数组m、预计成员n和哈希数k共同影响误判。理想独立均匀哈希下,p约为(1-exp(-kn/m))^k,最优k约(m/n)ln2,反算m约-n ln(p)/(ln2)^2。先估成员上限和允许误判,再取整数k与足够位数;这是近似模型,超量插入和偏斜哈希会改变实际效果。

这张卡片看不懂?

已有反馈 · 0 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 1 处

    • 大数据常用的算法与数据结构 · 查看原书依据

      在实际应用中,一般希望可以在一定范围内控制误判率的大小,比如低于1%。那么哪些因素会影响误判率呢?影响因素包括集合大小n 、哈希函数的个数k 和位数组大小m 。n 和m 对误判率的影响从直观上是很好理解的,因为集合大小n 越大,其他条件固定的情况下,位数组中就会有更多比例的位置被设置为1,误判概率就会增大。而位数组大小m 越大,那么在n 和k 固定的情况下,位数组中剩余为0的比特位比例就会越高,所以误判率就会越小。哈希函数个数对误判率的影响情况比较复杂,一方面在将集合成员映射到位数组过程中,如果其他条件固定,使用的哈希函数越多,则位数组中会有更多比例位置被设置为1,即增大误判率,但是在查询时,如果哈希函数个数越多,明显误判的可能就越小。经过数学分析,3个因素与误判率的关系如下:

    参考来源

    - 位置:《大数据日知录:架构与算法》第3章《大数据常用的算法与数据结构》(来源项目:book-sources;源文件:extracted/大数据日知录_架构与算法/_epub-src/OEBPS/text00008.html) - 结论依据:原文以“影响因素包括集合大小n”所在段落解释具体机制;本卡保留其条件,另将实现限制、勘误和教学推导在正文中明确区分。 - 原始内容:在实际应用中,一般希望可以在一定范围内控制误判率的大小,比如低于1%。那么哪些因素会影响误判率呢?影响因素包括集合大小n 、哈希函数的个数k 和位数组大小m 。n 和m 对误判率的影响从直观上是很好理解的,因为集合大小n 越大,其他条件固定的情况下,位数组中就会有更多比例的位置被设置为1,误判概率就会增大。而位数组大小m 越大,那么在n 和k 固定的情况下,位数组中剩余为0的比特位比例就会越高,所以误判率就会越小。哈希函数个数对误判率的影响情况比较复杂,一方面在将集合成员映射到位数组过程中,如果其他条件固定,使用的哈希函数越多,则位数组中会有更多比例位置被设置为1,即增大误判率,但是在查询时,如果哈希函数个数越多,明显误判的可能就越小。经过数学分析,3个因素与误判率的关系如下: - 边界对照:[LevelDB实现说明](https://raw.githubusercontent.com/google/leveldb/main/doc/impl.md)、[Bitcoin原论文](https://bitcoin.org/bitcoin.pdf)、[SILT原论文](https://www.cs.cmu.edu/~dga/papers/silt-sosp2011.pdf);用于校正原书简化,未将书外观点伪作原文。