一文理解布隆过滤器和布谷鸟过滤器
💡
原文中文，约6900字，阅读约需17分钟。
📝
内容提要
布隆过滤器是一种概率性数据结构，用于检查集合中元素的存在，具有节省空间和快速查询的优点。它通过哈希多个位置来降低假阳性率。布谷鸟过滤器则支持删除操作，查找性能更高，空间利用更紧凑，适合用于用户名检测和广告投放等场景。
🎯
关键要点
- 布隆过滤器是一种概率性数据结构，用于检查集合中元素的存在，具有节省空间和快速查询的优点。
- 布隆过滤器通过哈希多个位置来降低假阳性率，但不支持删除操作。
- 布谷鸟过滤器支持删除操作，查找性能更高，空间利用更紧凑，适合用于用户名检测和广告投放等场景。
- 布隆过滤器的准确度受填充率影响，填充率越高，假阳性率越高。
- Redis 提供可扩展的布隆过滤器，解决了容量固定的问题。
- 布隆过滤器的插入时间复杂度为 O(K)，检查元素的复杂度为 O(K) 或 O(K*(n + 1))。
- 布谷鸟过滤器通过驱逐现有元素来解决删除问题，查找性能更高且空间利用更紧凑。
- 布谷鸟过滤器的假阳性原因包括有限的空间、指纹冲突和哈希函数的性质。
- 布谷鸟过滤器的删除方法通过检查两个候选桶来实现，存在一定的假阳性风险。
- 布隆过滤器适用于检测用户名是否存在、广告投放和延保业务实践等场景。
➡️
