知识卡片
布隆用位图判断是否在集合
布隆过滤器用位图记录元素哈希所对应的位置。查询时,所检查位置有0可排除该元素;全部为1只表示可能存在。原书先讲单哈希简化模型,再说明多哈希。它用20亿位约238MiB对比直接存20亿个4字节标识的空间量级;这只是位数换算,不能据此断言238MiB足以在指定误判率下容纳20亿个元素。容量还要同时预算元素数、位图大小和哈希数量。
结构图:
flowchart LR
E[元素] --> H[哈希后对数组长度取模]
H --> B{该位是否为 1}
B -->|否| N[一定不在集合中]
B -->|是| Y[可能在集合中]
这张卡片看不懂?
这张卡片已通过人工审查,不再接受失败反馈。
已有反馈 · 0 条
还没有人提交反馈。
在整书笔记中的位置
原书出处 · 1 处
- 缓存的使用姿势(三):缓存穿透了怎么办? · 查看原书依据
如果这个位置的值为1就认为这个元素在集合中,否则则认为不在集合中
参考来源
- 位置:《高并发系统设计40问》第15讲《缓存的使用姿势(三):缓存穿透了怎么办?》(源文件:_epub-src/text/part0017_split_002.html)
- 结论依据:原文给出位图映射、单向误判及20亿位的空间算式;本轮将位数换算与可达到的误判率明确分开,不把空间对比当容量保证。
- 原始内容:如果这个位置的值为1就认为这个元素在集合中,否则则认为不在集合中
**外部补充核验(2026-10-26)**:[Broder与Mitzenmacher,Network Applications of Bloom Filters: A Survey,§2.1](https://www.eecs.harvard.edu/~michaelm/postscripts/im2005b.pdf)。本轮只读取数学基础相关范围,用于上述容量与误判条件校准,不声称通读该论文。