2020-11-09：谈谈布隆过滤器和布谷鸟过滤器的相同点和不同点？
【摘要】 福哥答案2020-11-09：相同点：都是过滤器。不同点：算法：布隆过滤器多个hash函数。布谷鸟过滤器用布谷鸟哈希算法。能否删除：布隆过滤器无法删除元素。布谷鸟过滤器可以删除元素，有误删可能。空间是否2的指数：布隆过滤器不需要2的指数。布谷鸟过滤器必须是2的指数。空间利用率：相同误判下，布谷鸟空间节省40%多。查询性能：布隆过滤器查询性能弱，原因是使用了多个hash函数，内存跨度大，缓存行...
福哥答案2020-11-09：
相同点：
都是过滤器。
不同点：
算法：布隆过滤器多个hash函数。布谷鸟过滤器用布谷鸟哈希算法。
能否删除：布隆过滤器无法删除元素。布谷鸟过滤器可以删除元素，有误删可能。
空间是否2的指数：布隆过滤器不需要2的指数。布谷鸟过滤器必须是2的指数。
空间利用率：相同误判下，布谷鸟空间节省40%多。
查询性能：布隆过滤器查询性能弱，原因是使用了多个hash函数，内存跨度大，缓存行命中率低。布谷鸟过滤器访问内存次数低，效率相对高。
哈希相关：布隆过滤器的多个函数函数之间没关系。布谷鸟过滤器的两个哈希函数可互相推导，两者有关系，用到了【空间是2的指数】和【按位与】。
重复插入相同元素：布隆过滤器天然自带重复过滤。布谷鸟过滤器会发生挤兑循环问题。
***
[Redis布隆Bloom过滤器](https://www.jdon.com/bigdata/redis-bloom.html)
[布隆过滤器过时了，未来属于布谷鸟过滤器？](https://cloud.tencent.com/developer/article/1447177)
[【Redis 第七篇】面试加分项：缓存穿透，布隆过滤器-计数过滤器-布谷鸟过滤器（好文005）](https://maoqizhi.blog.csdn.net/article/details/108532523?utm_medium=distribute.pc_relevant.none-task-blog-BlogCommendFromMachineLearnPai2-1.compare&depth_1-utm_source=distribute.pc_relevant.none-task-blog-BlogCommendFromMachineLearnPai2-1.compare)
【声明】本内容来自华为云开发者社区博主，不代表华为云及华为云开发者社区的观点和立场。转载时必须标注文章的来源（华为云社区）、文章链接、文章作者等基本信息，否则作者和本社区有权追究责任。如果您发现本社区中有涉嫌抄袭的内容，欢迎发送邮件进行举报，并提供相关证据，一经查实，本社区将立刻删除涉嫌侵权内容，举报邮箱：
cloudbbs@huaweicloud.com
- 点赞
- 收藏
- 关注作者
作者其他文章
- 2025-03-07：网格图操作后的最大分数。给定一个 n x n 的二维矩阵 grid，初始时所有格子均为白色。你可以进行操作
- 2025-03-06：给定一个长度为 n 的整数组 nums，其中 n 是偶数，同时还有一个整数 k。 你可以进行一些操作，每次
- 绝了！k3s (k8s) 安装 ollama 运行 deepseek 全流程揭秘，yaml全公开
- 2025-03-04：求出硬币游戏的赢家。用go语言，给定两个正整数 x 和 y，分别代表75元和10元硬币的数量。 Alice
- 2025-03-03：切蛋糕的最小总开销Ⅱ。用go语言，你有一个大小为 m x n 的矩形蛋糕，需要将其切割成 1 x 1 的小
评论（0）