知识卡片

结构图卡 · 2274.e.1.a.4.v.1.e

布隆用位图判断是否在集合

理解等级:未标注

布隆过滤器用位图记录元素哈希所对应的位置。查询时,所检查位置有0可排除该元素;全部为1只表示可能存在。原书先讲单哈希简化模型,再说明多哈希。它用20亿位约238MiB对比直接存20亿个4字节标识的空间量级;这只是位数换算,不能据此断言238MiB足以在指定误判率下容纳20亿个元素。容量还要同时预算元素数、位图大小和哈希数量。

结构图:

flowchart LR
    E[元素] --> H[哈希后对数组长度取模]
    H --> B{该位是否为 1}
    B -->|否| N[一定不在集合中]
    B -->|是| Y[可能在集合中]
这张卡片看不懂?

已有反馈 · 0 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 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)。本轮只读取数学基础相关范围,用于上述容量与误判条件校准,不声称通读该论文。