布谷鸟过滤器

布谷鸟过滤器是一种节省内存空间的概率数据结构，用于检测指定元素是否存在于某个集合中。与布隆过滤器相比，布谷鸟过滤器支持删除元素、在高负载因子场景下查询效率更高、存储空间开销更低，并且更容易实现。布谷鸟过滤器采用备用候选桶方案，插入时可能会出现对应位置上已经存储了指纹，需要将已存储的值踢出到候选桶，导致插入性能低于布隆过滤器。布谷鸟过滤器的删除操作不完美，可能会误删除其他元素。布谷鸟哈希算法使用两个哈希函数和两个哈希表来插入和查询元素。布谷鸟过滤器通过使用多路哈希桶、只存储指纹以减少内存使用、通过异或计算寻找新桶等优化改进了布谷鸟哈希算法。开源库linvon/cuckoo-filter实现了布谷鸟过滤器，支持调节参数、半排序桶、压缩空间等功能。