知识卡片
布隆只会把不在误判为在
在元素已完整写入、映射规则一致且没有错误删除的前提下,布隆过滤器只会把不在集合中的元素误判为可能存在。碰撞使一些无效请求仍被放行,但不影响对未置位结果的排除作用。原文建议多个哈希同时命中才判可能存在;补充校准:须合理选择元素数、位图容量与哈希数,固定容量下无限增加哈希并不会持续降低误判率。
这张卡片看不懂?
这张卡片已通过人工审查,不再接受失败反馈。
已有反馈 · 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)。本轮只读取数学基础相关范围,用于上述容量与误判条件校准,不声称通读该论文。