布隆过滤器误判率如何计算、哈希函数个数如何选
哪些公司问过
拼多多158同城1
答案要点
- 误判率近似公式 (1 - e^(-kn/m))^k
- 最优哈希函数个数 k = (m/n)·ln2
- 给定 n 和 p 时位数 m = -n·ln p / (ln2)^2
- k 过大位数组填满更快,误判率先降后升
- 只会误判不会漏判,标准布隆过滤器不支持删除
易错点
- 以为哈希函数越多误判率越低
- 说布隆过滤器会漏判
- 不预估元素量,容量不足导致误判率失控
面试官常见追问
- 为什么标准布隆过滤器不能删除?
- 元素数超过预估 n 会怎样?
- k 个哈希函数怎么高效实现?
完整的口述示范答案、每个追问的参考回答,在启面刷题中心查看;也可以让 AI 面试官用语音按这道题连环追问你。
相关面试题
- 布隆过滤器的原理58 场
- 10 亿用户中如何快速判断某用户是否存在1 场