布谷鸟过滤器
💡
原文中文，约9800字，阅读约需24分钟。
📝
内容提要
布谷鸟过滤器是一种节省内存空间的概率数据结构，与布隆过滤器相比具有支持删除元素、高负载因子场景下查询效率更高、存储空间开销更低、更容易实现等优点。然而，布谷鸟过滤器的缺点是需要桶的大小是2的指数倍，插入性能低于布隆过滤器，对重复元素的插入存在上限，删除操作不完美。布谷鸟过滤器使用布谷鸟哈希算法进行优化改进，采用多路哈希桶提高桶的利用率，只存储指纹以减少内存使用，通过异或计算寻找新桶。布谷鸟过滤器还可以使用半排序桶进行空间优化。开源库linvon/cuckoo-filter实现了布谷鸟过滤器，支持调节参数和半排序桶，压缩空间到紧凑的位数组，支持二进制序列化。
🎯
关键要点
-
布谷鸟过滤器是一种节省内存空间的概率数据结构，基于布谷鸟哈希算法实现。
-
布谷鸟过滤器支持删除元素，而布隆过滤器不支持。
-
在高负载因子场景下，布谷鸟过滤器查询效率更高，存储空间开销更低。
-
布谷鸟过滤器的缺点包括桶的大小必须是2的指数倍，插入性能低于布隆过滤器，删除操作不完美。
-
布谷鸟过滤器使用多路哈希桶提高桶的利用率，只存储指纹以减少内存使用。
-
布谷鸟过滤器通过异或计算寻找新桶，并可以使用半排序桶进行空间优化。
-
开源库linvon/cuckoo-filter实现了布谷鸟过滤器，支持调节参数和半排序桶，压缩空间到紧凑的位数组。
-
布谷鸟哈希算法使用两个哈希函数和两个哈希表进行元素插入和查询。
-
布谷鸟过滤器的插入和查询过程涉及元素的踢出和扩容操作。
-
半排序桶通过对指纹进行组合计算来优化存储空间。
-
linvon/cuckoo-filter库支持动态调整假阳性率和二进制序列化，适应性更强。
-
库的实现中包含了对并发的限制，使用时需注意并发竞态问题。
➡️
