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-07-15:子字符串匹配模式。用go语言,给定一个字符串 s 和一个模式字符串 p,且 p 中恰好包含一个 ‘*‘ 字
- 2025-07-14:统计恰好有 K 个相等相邻元素的数组数目。用go语言,给定三个整数 n、m、k,定义一个长度为 n 的数组
- 2025-07-13:统计特殊子序列的数目。用go语言,给定一个只包含正整数的数组 nums,我们定义长度为4的特殊子序列,其下
- 2025-07-11:使每一列严格递增的最少操作次数。用go语言,给定一个由非负整数组成的 m 行 n 列的矩阵 grid。 每
- 2025-07-10:字符相同的最短子字符串Ⅰ。用go语言,给定一个长度为 n 的二进制字符串 s 和一个允许执行的最大操作次数
评论(0)