Cuckoo Filter：设计与实现
这篇讲的是如何设计和实现一种名为 Cuckoo Filter 的高效过滤器。作者从实际业务中海量数据快速查询的需求出发，指出经典的 Bloom Filter 虽然空间利用率高，但存在无法删除元素的硬伤，一旦删除就会导致漏报。 为了解决这个问题，文章引入了布谷鸟哈希（Cuckoo Hashing）的设计思想。每个元素有两个哈希位置，发生冲突时，新元素会“踢走”原有元素，并利用其备用位置重新安置，就像布谷鸟侵占别的鸟巢一样。通过使用包含多个槽位的桶结构，可以大幅缓冲碰撞几率，实现高达 80% 以上的空间占用率（论文数据超过 90%），同时支持可靠的插入、查询和删除操作。 作者随后展示了自己用不到 500 行 C 代码实现的完整案例。核心思路是在内存中维护一个轻量级的哈希表，仅存储元素的部分摘要（tag）来快速过滤，将完整数据存放在后端存储（如 Flash）。这样查询时能最大程度避免不必要的磁盘读取。代码清晰地定义了哈希表、槽位结构，并实现了查询、插入等关键操作，验证了该方案在正确性和效率上的可行性。
