Closed OctopusLian closed 2 years ago
https://www.jianshu.com/p/61602c47d597 相同点： 都是过滤器。
不同点： 算法：布隆过滤器多个hash函数。布谷鸟过滤器用布谷鸟哈希算法。 能否删除：布隆过滤器无法删除元素。布谷鸟过滤器可以删除元素，有误删可能。 空间是否2的指数：布隆过滤器不需要2的指数。布谷鸟过滤器必须是2的指数。 空间利用率：相同误判下，布谷鸟空间节省40%多。 查询性能：布隆过滤器查询性能弱，原因是使用了多个hash函数，内存跨度大，缓存行命中率低。布谷鸟过滤器访问内存次数低，效率相对高。 哈希相关：布隆过滤器的多个函数函数之间没关系。布谷鸟过滤器的两个哈希函数可互相推导，两者有关系，用到了【空间是2的指数】和【按位与】。 重复插入：布隆过滤器天然自带重复过滤。布谷鸟过滤器会发生挤兑循环问题。
https://www.jianshu.com/p/61602c47d597 相同点： 都是过滤器。
不同点： 算法：布隆过滤器多个hash函数。布谷鸟过滤器用布谷鸟哈希算法。 能否删除：布隆过滤器无法删除元素。布谷鸟过滤器可以删除元素，有误删可能。 空间是否2的指数：布隆过滤器不需要2的指数。布谷鸟过滤器必须是2的指数。 空间利用率：相同误判下，布谷鸟空间节省40%多。 查询性能：布隆过滤器查询性能弱，原因是使用了多个hash函数，内存跨度大，缓存行命中率低。布谷鸟过滤器访问内存次数低，效率相对高。 哈希相关：布隆过滤器的多个函数函数之间没关系。布谷鸟过滤器的两个哈希函数可互相推导，两者有关系，用到了【空间是2的指数】和【按位与】。 重复插入：布隆过滤器天然自带重复过滤。布谷鸟过滤器会发生挤兑循环问题。