知识卡片

问题卡 · 2274.e.1.a.4.v.1.g

布隆只会把不在误判为在

理解等级:未标注

在元素已完整写入、映射规则一致且没有错误删除的前提下,布隆过滤器只会把不在集合中的元素误判为可能存在。碰撞使一些无效请求仍被放行,但不影响对未置位结果的排除作用。原文建议多个哈希同时命中才判可能存在;补充校准:须合理选择元素数、位图容量与哈希数,固定容量下无限增加哈希并不会持续降低误判率。

这张卡片看不懂?

已有反馈 · 0 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 1 处

    参考来源

    - 位置:《高并发系统设计40问》第15讲《缓存的使用姿势(三):缓存穿透了怎么办?》(源文件:_epub-src/text/part0017_split_002.html) - 结论依据:原文解释假阳性及多哈希的意图;补充条件依据Broder与Mitzenmacher论文§2.1关于位图大小、元素数与哈希数量共同决定误判率的分析。 - 原始内容:当布隆过滤器判断元素在集合中时,这个元素可能不在集合中。但是一旦布隆过滤器判断这个元素不在集合中时,它一定不在集合中 **外部补充核验(2026-10-26)**:[Broder与Mitzenmacher,Network Applications of Bloom Filters: A Survey,§2.1](https://www.eecs.harvard.edu/~michaelm/postscripts/im2005b.pdf)。本轮只读取数学基础相关范围,用于上述容量与误判条件校准,不声称通读该论文。