2020-11-09：谈谈布隆过滤器和布谷鸟过滤器的相同点和不同点？
原创2020-11-09：谈谈布隆过滤器和布谷鸟过滤器的相同点和不同点？
原创
福大大架构师每日一题
修改于 2020-11-10 10:18:53
修改于 2020-11-10 10:18:53
福哥答案2020-11-09：
相同点：
都是过滤器。
不同点：
算法：布隆过滤器多个hash函数。布谷鸟过滤器用布谷鸟哈希算法。
能否删除：布隆过滤器无法删除元素。布谷鸟过滤器可以删除元素，有误删可能。
空间是否2的指数：布隆过滤器不需要2的指数。布谷鸟过滤器必须是2的指数。
空间利用率：相同误判下，布谷鸟空间节省40%多。
查询性能：布隆过滤器查询性能弱，原因是使用了多个hash函数，内存跨度大，缓存行命中率低。布谷鸟过滤器访问内存次数低，效率相对高。
哈希相关：布隆过滤器的多个函数函数之间没关系。布谷鸟过滤器的两个哈希函数可互相推导，两者有关系，用到了【空间是2的指数】和【按位与】。
重复插入相同元素：布隆过滤器天然自带重复过滤。布谷鸟过滤器会发生挤兑循环问题。
原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。
如有侵权，请联系 cloudcommunity@tencent.com 删除。
原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。
如有侵权，请联系 cloudcommunity@tencent.com 删除。
评论
登录后参与评论
推荐阅读
相关产品与服务
云数据库 Redis
腾讯云数据库 Redis（TencentDB for Redis）是腾讯云打造的兼容 Redis 协议的缓存和存储服务。丰富的数据结构能帮助您完成不同类型的业务场景开发。支持主从热备，提供自动容灾切换、数据备份、故障迁移、实例监控、在线扩容、数据回档等全套的数据库服务。