布谷鸟过滤器

蛮荆 · 2023-06-30T00:00:00Z

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