布谷鸟过滤器
原文中文，约9800字，阅读约需24分钟。发表于：。布谷鸟过滤器是一种节省内存空间的概率数据结构，基于布谷鸟哈希算法实现的过滤器，和布隆过滤器一样，用于检测指定元素是否存在于某个集合中，返回 “元素一定不存在” 或 “有较大可能存在” 两种语义之一。
布谷鸟过滤器是一种节省内存空间的概率数据结构，与布隆过滤器相比具有支持删除元素、高负载因子场景下查询效率更高、存储空间开销更低、更容易实现等优点。然而，布谷鸟过滤器的缺点是需要桶的大小是2的指数倍，插入性能低于布隆过滤器，对重复元素的插入存在上限，删除操作不完美。布谷鸟过滤器使用布谷鸟哈希算法进行优化改进，采用多路哈希桶提高桶的利用率，只存储指纹以减少内存使用，通过异或计算寻找新桶。布谷鸟过滤器还可以使用半排序桶进行空间优化。开源库linvon/cuckoo-filter实现了布谷鸟过滤器，支持调节参数和半排序桶，压缩空间到紧凑的位数组，支持二进制序列化。
