布谷鸟过滤器

定义

布谷鸟过滤器(Cuckoo Filter)是一种近似成员查询(AMQ)数据结构,由 Bin Fan 等人于 2014 年提出,用于快速判断元素"一定不存在"或"可能存在",与布隆过滤器用途相同,但支持删除操作。

原理

它基于布谷鸟哈希:不存元素本身,而是存元素的短指纹(fingerprint,如 8 位)。每个元素有两个候选桶,第二个桶位置由第一个位置与指纹异或哈希得出(partial-key cuckoo hashing),因此仅凭桶内指纹即可算出其备选位置。插入时若两个桶都满,就随机踢出一个已有指纹,把它安置到其备选桶,如此连锁"鸠占鹊巢",直到成功或达到踢出上限。查询只需检查两个桶是否含指纹;删除则移除一个匹配指纹。

对比布隆过滤器

优势:支持删除、查询只碰两个桶(缓存友好)、在误判率约低于 3% 时空间更省。劣势:装载率接近上限时插入可能失败,重复插入同一元素有次数限制。

应用

常用于存储引擎、缓存与网络系统中替代布隆过滤器做存在性预判。