空间效率：布隆过滤器使用位数组，每个元素只占用1 bit，因此空间效率很高。
查询速度快：布隆过滤器的查询时间复杂度为 O(K)，其中 K 是哈希函数的个数，通常 K 较小，因此查询速度快。
简单实现：布隆过滤器的实现相对简单，不需要存储元素本身，适合对保密要求严格的场合。
可并行运算：哈希函数相互独立，方便硬件并行运算。
适用性广：在数据量大时，布隆过滤器可以表示全集，而其他数据结构可能无法做到。

布隆过滤器的缺点：

误判率：存在假阳性（False Positive），即可能会错误地判断某个元素存在于集合中。
不支持删除：布隆过滤器不支持删除操作，一旦元素被添加到过滤器中，就无法删除，这可能会导致误判率随着元素数量的增加而提高。
实现复杂性：选择合适的哈希函数和确定过滤器的大小需要仔细考虑，以平衡空间效率和误判率。

布谷鸟过滤器（Cuckoo Filter）的优化：

布谷鸟过滤器是布隆过滤器的一种改进，它解决了布隆过滤器的一些缺点：

支持删除：布谷鸟过滤器支持动态添加和删除元素，这是布隆过滤器所不具备的。
高查找性能：即使在接近满载的情况下，布谷鸟过滤器也能提供比传统布隆过滤器更高的查找性能。
空间效率：在目标假阳性率低于3%的情况下，布谷鸟过滤器比布隆过滤器更节省空间。
简单实现：布谷鸟过滤器的实现比商过滤器（Quotient Filter）等替代方案更简单。

工业级别的布谷鸟过滤器实现：

Cuckoo Filter 的源码分析：可以查看论文作者提供的源代码，例如在 GitHub 上的实现。
数据结构：布谷鸟过滤器使用二维数组来存储桶，每个桶中可以存储多个元素的指纹。
哈希函数：布谷鸟过滤器使用两个独立的哈希函数来计算元素的主位置和备用位置。
插入、查找和删除操作：布谷鸟过滤器详细定义了插入、查找和删除元素的具体流程，包括处理哈希冲突和踢出策略。

工业级别的实现需要考虑性能、并发、内存管理等多个方面，可能需要对基本的布谷鸟过滤器算法进行优化和扩展。

https://github.com/efficient/cuckoofilter

布谷鸟过滤器的核心原理：

哈希函数：布谷鸟过滤器使用两个独立的哈希函数，每个哈希函数将元素映射到一个特定的位置，称为主位置和备用位置。
桶结构：过滤器由多个桶组成，每个桶可以存储多个元素的指纹（即元素的一部分哈希值）。桶的大小通常根据目标假阳性率来确定。
插入操作：
- 首先，使用两个哈希函数计算元素的主位置和备用位置。
- 如果主位置空闲，元素的指纹被存储在主位置。
- 如果主位置被占用，元素的指纹会尝试存储在备用位置。如果备用位置也已被占用，则会触发“踢出”机制。
踢出机制：
- 当备用位置也被占用时，会将原本在备用位置的元素“踢出”，并尝试将其放入它的备用位置。
- 这个过程可能引发连锁反应，即被踢出的元素再次占用其他元素的位置，这个过程会一直持续，直到找到一个空闲的位置或者达到某个最大迭代次数。
删除操作：
- 删除操作相对简单，只需要根据元素的两个哈希值找到对应的桶和位置，然后清除元素的指纹即可。
查找操作：
- 查找元素时，会使用两个哈希函数计算元素可能在的位置。
- 在这些位置中查找元素的指纹，如果找到，则认为元素存在于集合中；如果没有找到，则元素不在集合中。
假阳性率：
- 布谷鸟过滤器可能会产生假阳性，即错误地认为某个元素存在于集合中。这通常发生在多个元素的指纹在同一个桶中发生冲突时。
空间效率：
- 布谷鸟过滤器通过优化存储结构和哈希函数的使用，可以在较低的误判率下实现较高的空间效率。

布谷鸟过滤器的优点：

支持元素的动态添加和删除。
在高负载因子下，查找性能优于布隆过滤器。
实现相对简单，易于理解和实现。

布谷鸟过滤器的缺点：

当过滤器接近满载时，插入操作可能会失败，需要进行rehash。
在极端情况下，如果同一元素被多次插入，可能会导致过滤器性能下降。

原理

❝

为啥要取名布谷鸟呢?

有个成语，「鸠占鹊巢」,布谷鸟也是,布谷鸟从来不自己筑巢。它将自己的蛋产在别人的巢里，让别人来帮忙孵化。待小布谷鸟破壳而出之后，因为布谷鸟的体型相对较大，它又将养母的其它孩子（还是蛋）从巢里挤走 —— 从高空摔下夭折了。

布谷鸟哈希

最简单的布谷鸟哈希结构是一维数组结构，会有两个 hash 算法将新来的元素映射到数组的两个位置。如果两个位置中有一个位置为空，那么就可以将元素直接放进去。但是如果这两个位置都满了，它就不得不「鸠占鹊巢」，随机踢走一个，然后自己霸占了这个位置。

p1 = hash1(x) % lp2 = hash2(x) % l

不同于布谷鸟的是，布谷鸟哈希算法会帮这些受害者（被挤走的蛋）寻找其它的窝。因为每一个元素都可以放在两个位置，只要任意一个有空位置，就可以塞进去。所以这个伤心的被挤走的蛋会看看自己的另一个位置有没有空，如果空了，自己挪过去也就皆大欢喜了。但是如果这个位置也被别人占了呢？好，那么它会再来一次「鸠占鹊巢」，将受害者的角色转嫁给别人。然后这个新的受害者还会重复这个过程直到所有的蛋都找到了自己的巢为止。

布谷鸟哈希的问题

但是会遇到一个问题，那就是如果数组太拥挤了，连续踢来踢去几百次还没有停下来，这时候会严重影响插入效率。这时候布谷鸟哈希会设置一个阈值，当连续占巢行为超出了某个阈值，就认为这个数组已经几乎满了。这时候就需要对它进行扩容，重新放置所有元素。

还会有另一个问题，那就是可能会存在挤兑循环。比如两个不同的元素，hash 之后的两个位置正好相同，这时候它们一人一个位置没有问题。但是这时候来了第三个元素，它 hash 之后的位置也和它们一样，很明显，这时候会出现挤兑的循环。不过让三个不同的元素经过两次 hash 后位置还一样，这样的概率并不是很高，除非你的 hash 算法太挫了。

布谷鸟哈希算法对待这种挤兑循环的态度就是认为数组太拥挤了，需要扩容（实际上并不是这样）。

优化

上面的布谷鸟哈希算法的平均空间利用率并不高，大概只有 50%。到了这个百分比，就会很快出现连续挤兑次数超出阈值。这样的哈希算法价值并不明显，所以需要对它进行改良。

改良的方案之一是增加 hash 函数，让每个元素不止有两个巢，而是三个巢、四个巢。这样可以大大降低碰撞的概率，将空间利用率提高到 95%左右。

另一个改良方案是在数组的每个位置上挂上多个座位，这样即使两个元素被 hash 在了同一个位置，也不必立即「鸠占鹊巢」，因为这里有多个座位，你可以随意坐一个。除非这多个座位都被占了，才需要进行挤兑。很明显这也会显著降低挤兑次数。这种方案的空间利用率只有 85%左右，但是查询效率会很高，同一个位置上的多个座位在内存空间上是连续的，可以有效利用 CPU 高速缓存。

所以更加高效的方案是将上面的两个改良方案融合起来，比如使用 4 个 hash 函数，每个位置上放 2 个座位。这样既可以得到时间效率，又可以得到空间效率。这样的组合甚至可以将空间利用率提到高 99%，这是非常了不起的空间效率。

布谷鸟过滤器

布谷鸟过滤器和布谷鸟哈希结构一样，它也是一维数组，但是不同于布谷鸟哈希的是，布谷鸟哈希会存储整个元素，而布谷鸟过滤器中只会存储元素的指纹信息（几个bit，类似于布隆过滤器）。这里过滤器牺牲了数据的精确性换取了空间效率。正是因为存储的是元素的指纹信息，所以会存在误判率，这点和布隆过滤器如出一辙。

首先布谷鸟过滤器还是只会选用两个 hash 函数，但是每个位置可以放置多个座位。这两个 hash 函数选择的比较特殊，因为过滤器中只能存储指纹信息。当这个位置上的指纹被挤兑之后，它需要计算出另一个对偶位置。而计算这个对偶位置是需要元素本身的，我们来回忆一下前面的哈希位置计算公式。

fp = fingerprint(x)p1 = hash1(x) % lp2 = hash2(x) % l

我们知道了 p1 和 x 的指纹，是没办法直接计算出 p2 的。

特殊的 hash 函数

布谷鸟过滤器巧妙的地方就在于设计了一个独特的 hash 函数，使得可以根据 p1 和元素指纹直接计算出 p2，而不需要完整的 x 元素。

fp = fingerprint(x)p1 = hash(x)p2 = p1 ^ hash(fp) // 异或

从上面的公式中可以看出，当我们知道 fp 和 p1，就可以直接算出 p2。同样如果我们知道 p2 和 fp，也可以直接算出 p1 —— 对偶性。

p1 = p2 ^ hash(fp)

所以我们根本不需要知道当前的位置是 p1 还是 p2，只需要将当前的位置和 hash(fp) 进行异或计算就可以得到对偶位置。而且只需要确保 hash(fp) != 0 就可以确保 p1 != p2，如此就不会出现自己踢自己导致死循环的问题。

也许你会问为什么这里的 hash 函数不需要对数组的长度取模呢？实际上是需要的，但是布谷鸟过滤器强制数组的长度必须是 2 的指数，所以对数组的长度取模等价于取 hash 值的最后 n 位。在进行异或运算时，忽略掉低 n 位之外的其它位就行。将计算出来的位置 p 保留低 n 位就是最终的对偶位置。

参考

https://mp.weixin.qq.com/s/BmgH5oX13wJLjRCoVjoYTw

布谷鸟过滤器Cuckoo Filter

目录

布隆过滤器的优点：