ai-infra-interview-305

第 284 题：`bloom filter`在缓存中的应用？假阳性率计算？

题目

bloom filter在缓存中的应用？假阳性率计算？

完整讲解

一、Bloom filter 与缓存应用

Bloom filter：位数组 + k 个哈希函数；插入时把 k 个位置置 1，查询时 k 个位置全为 1 则「可能存在」（有假阳性），任一为 0 则「一定不存在」。在缓存中用于前置过滤：先查 Bloom filter，若为「不存在」则不必访问缓存或 DB，减少穿透；若为「可能存在」再查缓存/DB。

二、假阳性率

设位数组长 m、元素数 n、哈希函数数 k。近似假阳性率 p ≈ (1 - e^(-kn/m))^k。在 n 给定下，取 k = (m/n) ln 2 时 p 最小，约 0.6185^(m/n)。故 m 越大、n 越少，假阳性率越低；工程上常取 m/n 为 10～20、k 据此计算。

三、注意

不支持删除（除非用 counting Bloom filter）；假阳性可接受时能大幅减少无效查询。常用于缓存/DB 前、去重、爬虫已访问集合等。

面试要点

Bloom filter：位数组 + k 个 hash；无假阴性、有假阳性；用于「一定不存在」的快速判断。
缓存中做前置过滤：Bloom 判不存在则不打缓存/DB；判存在再查。
假阳性率 p ≈ (1 - e^(-kn/m))^k；k ≈ (m/n)ln2 时 p 最小；m/n 大则 p 小。
不支持删除（或需 counting BF）；适合穿透防护、去重等。

记忆要点

位数组 + k 个 hash；全 1 则可能存在、有 0 则一定不存在。
假阳性率与 m、n、k 相关；k≈(m/n)ln2 最优。
缓存中做前置过滤；不支持删除。

返回模块

返回总览