布隆过滤器和布谷鸟过滤器

前言

布隆过滤器 (Bloom Filter)是由Burton Howard Bloom于1970年提出，它是一种space efficient的概率型数据结构，用于判断一个元素是否在集合中。在垃圾邮件过滤的黑白名单方法、爬虫(Crawler)的网址判重模块中等等经常被用到。哈希表也能用于判断元素是否在集合中，但是布隆过滤器只需要哈希表的1/8或1/4的空间复杂度就能完成同样的问题。布隆过滤器可以插入元素，但不可以删除已有元素。其中的元素越多，false positive rate(误报率)越大，但是false negative (漏报)是不可能的。

传统HashMap数据结构的不足

一般来说，将网页 URL 存入数据库进行查找，或者建立一个哈希表进行查找就 OK 了。

当数据量小的时候，这么思考是对的，确实可以将值映射到 HashMap 的 Key，然后可以在 O(1) 的时间复杂度内 返回结果，效率奇高。但是 HashMap 的实现也有缺点，例如存储容量占比高，考虑到负载因子的存在，通常空间是不能被用满的，举个例子如果一个 1000 万 HashMap，Key=String（长度不超过 16 字符，且重复性极小），Value=Integer，会占据多少空间呢？1.2 个 G。

实际上用 bitmap，1000 万个 int 型，只需要 40M（ 10 000 000 * 4/1024/1024 =40M）左右空间，占比 3%，

在 Java 中，Integer 是一个包装类，每个 Integer 对象包含以下几个部分：

  • 一个 int 值：4 字节（32 位）
  • 对象头：一般为 12 字节（在 64 位 JVM 中，启用压缩指针时）
  • 对象引用：一般为 4 字节（压缩指针启用时）

所以，一个 Integer 对象大约占用 16 字节的内存。

1000 万个 Integer，需要 160M 左右空间，占比 13.3%。

可见一旦你的值很多例如上亿的时候，那 HashMap 占据的内存大小就可想而知了。

但如果整个网页黑名单系统包含 100 亿个网页 URL，在数据库查找是很费时的，并且如果 URL 平均长度为 64字节，那么需要内存为 640GB，一般的服务器很难达到这个需求。

BitMap数据结构

现代计算机用二进制（bit，位）作为信息的基础单位，1 个字节等于 8 位。许多开发语言都提供了操作位的功能，合理地使用位能够有效地提高内存使用率和开发效率。

Bit-map 的基本思想就是用一个 bit 位来标记某个元素对应的 value，而 key 即是该元素。由于采用了 bit 为单位来存储数据，因此在存储空间方面，可以大大节省。

在 Java 中，int 占 4 字节，1 字节 = 8位（1 byte = 8 bit），如果我们用这个 32 个 bit 位的每一位的值来表示一个数的话是不是就可以表示 32 个数字，也就是说 32 个数字只需要一个 int 所占的空间大小就可以了，那就可以缩小空间 32 倍。

1 Byte = 8 Bit，1 KB = 1024 Byte，1 MB = 1024 KB，1GB = 1024 MB

举个例子：假设网站有 1 亿用户，每天独立访问的用户有 5 千万，如果每天用集合类型和 BitMap 分别存储活跃用户：

集合类型：假如用户 id 是 int 型，4 字节，32 位，则集合类型占据的空间为 50 000 000 * 4/1024/1024 = 200M；

BitMap：.如果按位存储，5 千万个数就是 5 千万位，占据的空间为 50 000 000/8/1024/1024 = 6M。

那么如何用 BitMap 来表示一个数呢？

上面说了用 bit 位来标记某个元素对应的 value，而 key 即是该元素，我们可以把 BitMap 想象成一个以位为单位的数组，数组的每个单元只能存储 0 和 1（0 表示这个数不存在，1 表示存在），数组的下标在 BitMap 中叫做偏移量。

比如我们需要表示{1,3,5,7}这四个数，如下：

image-20220311102113004

那如果还存在一个数 65 呢？只需要开int[N/32+1]个 int 数组就可以存储完这些数据（其中 N 表示这群数据中的最大值），即：

int[0]：可以表示 0~31

int[1]：可以表示 32~63

int[2]：可以表示 64~95

image-20220311102821020

假设我们要判断任意整数是否在列表中，则 M/32 就得到下标，M%32就知道它在此下标的哪个位置，如：

65/32 = 2，65%32=1，即 65 在int[2] 中的第 1 位。

1
Java BitArray使用long类型来实现，long占8字节，64位，所以需要构建long[Math.ceil(n/64)]大小的long数组。

布隆过滤器

概念

本质上布隆过滤器是一种数据结构，比较巧妙的概率型数据结构，特点是高效地插入和查询，可以用来告诉你 “某 样东西一定不存在或者可能存在”。

网页交互初探：Bloom Filters (jasondavies.com)

特点

相比于传统的 List、Set、Map 等数据结构，它更高效、占用空间更少，但是缺点是其返回的结果是概率性的，而不是确切的。

实际上，布隆过滤器广泛应用于网页黑名单系统、垃圾邮件过滤系统、爬虫网址判重系统等，Google 著名的分布式数据库 Bigtable 使用了布隆过滤器来查找不存在的行或列，以减少磁盘查找的 IO 次数，Google Chrome 浏览器使用了布隆过滤器加速安全浏览服务。

在很多 Key-Value 系统中也使用了布隆过滤器来加快查询过程，如 Hbase，Redis。一般而言，Value 保存在磁盘中，访问磁盘需要花费大量时间，然而使用布隆过滤器可以快速判断某个 Key 对应的 Value 是否存在，因此可以避免很多不必要的磁盘 IO 操作。通过一个 Hash 函数将一个元素映射成一个位阵列（Bit Array）中的一个点。这样一来，我们只要看看这个点是不是 1 就知道可以集合中有没有它了。这就是布隆过滤器的基本思想。

当一个元素加入布隆过滤器中的时候，会进行如下操作：

1
2
使用布隆过滤器中的哈希函数对元素值进行计算，得到哈希值（有几个哈希函数得到几个哈希值）。
根据得到的哈希值，在位数组中把对应下标的值置为 1。

当我们需要判断一个元素是否存在于布隆过滤器的时候，会进行如下操作：

1
2
对给定元素再次进行相同的哈希计算；
得到值之后判断位数组中的每个元素是否都为 1，如果值都为 1，那么说明这个值在布隆过滤器中(注意：由于hash冲突问题，所谓的存在只能是可能存在)，如果存在一个值不为 1，说明该元素不在布隆过滤器中。

布隆过滤器不支持删除

传统的布隆过滤器并不支持删除操作。因为hash碰撞的原因，你想要删除的元素有可能存储着其他元素的信息。但是名为 Counting Bloom filter 的变种可以用来测试元素计数个数是否绝对小于某个阈值，它支持元素删除。

综上，我们可以得出：

1.布隆过滤器说某个元素存在，小概率会误判，不一定存在；

2.布隆过滤器说某个元素不在，那么这个元素一定不在；

3.布隆过滤器不支持删除。（不包含变种）

运用场景

1、目前有 10 亿数量的自然数，乱序排列，需要对其排序。限制条件在 32 位机器上面完成，内存限制为 2G。如何完成？

2、如何快速在亿级黑名单中快速定位 URL 地址是否在黑名单中？(每条 URL 平均 64 字节)

3、需要进行用户登陆行为分析，来确定用户的活跃情况？

4、网络爬虫-如何判断 URL 是否被爬过？

5、快速定位用户属性（黑名单、白名单等）？

6、数据存储在磁盘中，如何避免大量的无效 IO？

7、判断一个元素在亿级数据中是否存在？

8、缓存穿透。

1
2
3
4
5
6
7
8
9
10
11
12
解决缓存穿透

缓存穿透是指查询一个根本不存在的数据，缓存层和存储层都不会命中，如果从存储层查不到数据则不写入缓存层。
缓存穿透将导致不存在的数据每次请求都要到存储层去查询，失去了缓存保护后端存储的意义，可能会使后端存储负载加大，数据库宕机。

因此我们可以用布隆过滤器来解决，在访问缓存层和存储层之前，将存在的 key 用布隆过滤器提前保存起来，做第一层拦截。

例如：一个推荐系统有 4 亿个用户 id，每个小时算法工程师会根据每个用户之前历史行为计算出推荐数据放到存储层中，但是最新的用户由于没有历史行为，就会发生缓存穿透的行为，为此可以将所有推荐数据的用户做成布隆过滤器。

如果布隆过滤器认为该用户 id 不存在，那么就不会访问存储层，在一定程度保护了存储层。

注：布隆过滤器可能会误判，放过部分请求，当不影响整体，所以目前该方案是处理此类问题最佳方案

9.短视频的曝光页面瀑布流式展示

image-20230624005823225

为了兼顾短视频质量和时效性，短视频排序采用了重力算法：

image-20230624005845050

H为短视频的质量分，通过观看，点赞，评论，转发等数据加权求和计算，T为短视频发布时间戳，T0位基准时间，取发现页最早发布的短视频创建时间戳，单位均为秒。A为时间系数，根据发现页短视频的平均更新间隔，取36000(10小时)。该算法的效果是，发布时间接近，质量分高的短视频靠前，随着时间推移，短视频不断下沉，削弱头部曝光产生的马太效应。

为了提高内容的新鲜感，我们希望用户在每次下拉刷新以及翻页的时候，都能看到新的短视频，同时在短视频列表头部加入新的短视频时，能得到优先展示，如下图所示：

image-20230624005900854

左图为首屏显示的短视频，如在此时，短视频列表顺序发生了更新，C+和D+插在了看过的视频中间，我们希望在下次刷新的时候，把浏览过的其他视频去掉，相当于优先插入C+、D+。实现这个需求最简单的方法是保存用户最近观看过的全部短视频作为过滤器，每次返回列表的时候，从头部开始遍历，去掉用户看过的短视频。显然，过滤器的容量，决定了短视频列表的最大展示深度？？？？？（返回的列表一定，只是对列表进行过滤？？？）。根据产品需求，发现页需要展示最近一个月的短视频，大约4000个，平均每个短视频id的长度为50字节，这个过滤器如果用传统的redis set等手段实现，存储成本和过滤效率都比较低，针对这个问题，我们采用了一个简单而强大的数据结构—布隆过滤器。

Bloom Filter(布隆过滤器)是一种空间效率很高的随机数据结构，它利用位数组很简洁地表示一个集合，并能判断一个元素是否属于这个集合。Bloom Filter的这种高效是有一定代价的：在判断一个元素是否属于某个集合时，有可能会把不属于这个集合的元素误认为属于这个集合（false positive）。因此，Bloom Filter不适合那些“零错误”的应用场合。而在能容忍低错误率的应用场合下，Bloom Filter通过极少的错误换取了存储空间的极大节省。

我们使用MurmurHash和bitset实现了一个可以序列化成整形数组的布隆过滤器，可以利用redis支持的简单key-value数据结构进行存取，在本地实现高效的过滤运算，一个能保存4000个短视频id的布隆过滤器，只占用不到8KB的空间，get&set的效率都比较高。

因为布隆过滤器容量有限，且无法删除元素，需要配合重建策略使用。我们用redis维护了一个最近观看的100个短视频id，当布隆过滤器空间利用率超过百分之50的时候，清空并使用这100个id进行重建，避免了极端情况下的重复问题。

注：常见的布隆过滤器：

1
2
3
4
5
6
7
8
9
10
11
12
13
1.RedisBloom
布隆过滤器可以使用 Redis 中的位图(bitmap)操作实现，直到 Redis4.0 版本提供了插件功能，Redis 官方提供的布隆过滤器才正式登场，布隆过滤器作为一个插件加载到 Redis Server 中，官网推荐了一个 RedisBloom 作为 Redis 布隆过滤器的 Module。
详细安装、指令操作参考：https://github.com/RedisBloom/RedisBloom
文档地址：https://oss.redislabs.com/redisbloom/
整合redis方案:
①.将算法和bitmap数据放在client
②.算法在client，bitmap数据在redis
③.讲算法和bitmap数据都放在redis


2.Guava 的 BloomFilter
Guava 项目发布版本11.0时，新添加的功能之一是BloomFilter类。
Guava 提供的布隆过滤器的实现还是很不错的（想要详细了解的可以看一下它的源码实现），但是它有一个重大的缺陷就是只能单机使用（另外，容量扩展也不容易），而现在互联网一般都是分布式的场景，还得是redis出马。

实现原理

假设我们有个集合 A，A 中有 n 个元素。利用k个哈希散列函数，将A中的每个元素映射到一个长度为 a 位的数组 B中的不同位置上，这些位置上的二进制数均设置为 1。

如果待检查的元素，经过这 k个哈希散列函数的映射后，发现其 k 个位置上的二进制数全部为 1，这个元素很可能属于集合A，反之，一定不属于集合A。

比如我们有 3 个 URL {URL1,URL2,URL3}，通过一个hash 函数把它们映射到一个长度为 16 的数组上，如下：

image-20220311114106069

若当前哈希函数为 Hash1()，通过哈希运算映射到数组中，假设Hash1(URL1) = 3，Hash1(URL2) = 6，Hash1(URL3) = 6，如下：

image-20220311142934256

因此，如果我们需要判断URL1是否在这个集合中，则通过Hash(1)计算出其下标，并得到其值若为 1 则说明存在。

由于 Hash 存在哈希冲突，如上面URL2,URL3都定位到一个位置上，假设 Hash 函数是良好的，如果我们的数组长度为 m 个点，那么如果我们想将冲突率降低到例如 1%， 这个散列表就只能容纳 m/100 个元素，显然空间利用率就变低了，也就是没法做到空间有效（space-efficient）。

解决方法也简单，就是使用多个 Hash 算法，如果它们有一个说元素不在集合中，那肯定就不在，如下：

1
2
3
Hash1(URL1) = 3,Hash2(URL1) = 5,Hash3(URL1) = 6
Hash1(URL2) = 5,Hash2(URL2) = 8,Hash3(URL2) = 14
Hash1(URL3) = 4,Hash2(URL3) = 7,Hash3(URL3) = 10

image-20220311154805364

以上就是布隆过滤器做法，使用了k个哈希函数，每个字符串跟 k 个 bit 对应，从而降低了冲突的概率。

误判现象

上面的做法同样存在问题，因为随着增加的值越来越多，被置为 1 的 bit 位也会越来越多，这样某个值即使没有被存储过，但是万一哈希函数返回的三个 bit 位都被其他值置位了 1 ，那么程序还是会判断这个值存在。

比如此时来一个不存在的 URL1000，经过哈希计算后，发现 bit 位为下：

1
Hash1(URL1000) = 7,Hash2(URL1000) = 8,Hash3(URL1000) = 14

image-20220311155646991

但是上面这些 bit 位已经被URL1,URL2,URL3置为 1 了，此时程序就会判断 URL1000 值存在。

这就是布隆过滤器的误判现象，所以，布隆过滤器判断存在的不一定存在，但是，判断不存在的一定不存在。

布隆过滤器可精确的代表一个集合，可精确判断某一元素是否在此集合中，精确程度由用户的具体设计决定，达到 100% 的正确是不可能的。

但是布隆过滤器的优势在于，利用很少的空间可以达到较高的精确率。

Bloom Filter公式推导

image-20230224221925075

image-20230224222617820

image-20230224222649851

Coding

1.spark中构建布隆过滤器，然后进行广播；

2.整合redis布隆过滤

3.Hbase也有布隆过滤器

布谷鸟过滤器

背景

除了删除这个问题之外，布隆过滤器还有一个问题：查询性能不高。

因为真实场景中过滤器中的数组长度是非常长的，经过多个不同 Hash 函数后，得到的数组下标在内存中的跨度可能会非常的大。跨度大，就是不连续。不连续，就会导致 CPU 缓存行命中率低。

变种的[Counting Bloom Filter](CountMinSketch计数器：基于布隆过滤器思想的近似计数器 - 掘金 (juejin.cn))，虽然实现了删除操作，但是用多占用3 到 4 倍倍的存储空间的代价，才给 Bloom Filter 增加了删除操作，不够优雅。

因此出现新的解决方案，那就是布谷鸟过滤器。

特点

论文《Cuckoo Filter: Practically Better Than Bloom》提出了删除并不需要在空间或性能上提出更高的开销。

布谷鸟过滤器是一个实用的数据结构，提供了四大优势：

  • 1.支持动态的新增和删除元素。
  • 2.提供了比传统布隆过滤器更高的查找性能，即使在接近满的情况下（比如空间利用率达到 95% 的时候）。
  • 3.比诸如商过滤器（quotient filter，另一种过滤器）之类的替代方案更容易实现。
  • 4.如果要求错误率小于3%，那么在许多实际应用中，它比布隆过滤器占用的空间更小。

实现原理

布谷鸟过滤器不同于布隆过滤器主要有两点改动：

1.hash算法：
在布谷鸟过滤器中，数组中存储的是每个元素的”指纹信息”，也就是hash运算之后的几个bit位。查询数据的时候，就是看看对应的位置上有没有对应的“指纹”信息，删除数据的时候，也只是抹掉该位置上的“指纹”而已。
由于指纹是对元素进行 hash 计算得出的，那么必然会出现 hash 碰撞的问题，也就是“指纹”相同的情况，也就是会出现误判的情况，所以这点和布隆过滤器一样。
布谷鸟过滤器的hash算法是基于布谷鸟哈希算法做了改进，计算公式如下：

1
2
3
fp = fingerprint(x)
h1 = hash(x)
h2 = h1 ^ hash(fp)  // 异或

在上列公式可以看出，h2的位置是根据h1的位置计算出来的，也就是说我们知道了其中一个位置，就可以直接获取到另外一个位置，不需要再做全量的hash运算。因为使用的异或运算，所以这两个位置具有对偶性。这也是提高查询效率的一个点。
只要保证 hash(fp) !=0，那么就可以确保 h2!=h1，也就可以确保不会出现自己踢自己的死循环问题了。
这里还有个注意点：就是hash运算的时候，并没有对值进行长度取模运算，那么他是如何保证计算出来hash坐标，一定是在数组长度范围内呢？这就说到布谷鸟过滤器的一个限制条件了，那就是强制数组的长度必须是 2 的指数倍。2 的指数倍的二进制一定是这样的：10000000…（n个0）。
这个限制带来的好处就是，进行异或运算时，可以保证计算出来的下标一定是落在数组中的

2.存储结构：

布谷鸟过滤器的存储结构是每个坐标下的空位是多个，不同于布隆过滤器的一个空位。如下图所示：

img-625861032ff5480e9e3170253dfefd01.png

布谷鸟过滤器会记录每个元素的两个hash位置，每个位置下都会有多个空位，空位内存储的就是元素的“指纹信息”。

布谷鸟过滤器添加元素的流程是这样的：
布谷鸟过滤器会先计算出元素对应的指纹信息，然后对元素进行hash运算，计算出元素的第一个存储坐标，该坐标下存在四个空位，如果四个空位中有空闲的，就将该元素的指纹信息存进去；如果没有空位，就会根据指纹和第一个hash坐标进行异或运算，计算出第二个坐标，如果第二个坐标下有空位，就将该元素的指纹信息存进去；如果还没有空位，那么该元素就会随机将一个空位中的指纹信息挤出，然后自己存进去，被挤出的指纹信息会计算出自己的第二个坐标，然后判断是否有空位，重复上述操作，直到达到一个阀值，布谷鸟过滤器返回false或进行扩容处理。

数据Data(指纹11)想要存储到布谷鸟过滤器中，首先会计算出h1和h2两个存储坐标，结果发现两个坐标的空位都已经“满员”了，此时会随机挤掉一个元素的指纹信息，假设挤掉了h1坐标的指纹3，然后指纹3会找自己的第二个坐标，然后判断是否有空位，有空位就存到第二个坐标下，如下图：

img-7467220cf5a34202a5873dbf0c8cdf21.png

扩容：如果数组过小，会发生循环挤兑的情况，就可以设置最大挤兑次数，如果超过该次数，进行扩容，重新计算每个指纹的位置。

当 hash 函数固定为 2 个的时候，如果一个下标只能放一个元素的指纹信息，那么空间利用率是 50%。如果为 2，4，8 个元素的时候，空间利用率分别是 84%，95%，98%，可以发现空间利用率飙升。

但是需要对重复数据进行限制：如果需要布谷鸟过滤器支持删除，它必须知道一个数据插入过多少次。不能让同一个数据插入 kb+1 次。其中 k 是 hash 函数的个数，b 是一个下标的位置能放几个元素。

比如 2 个 hash 函数，一个二维数组，它的每个下标最多可以插入 4 个元素。那么对于同一个元素，最多支持插入 8 次。

例如下面这种情况：

image-20230624031242087

why 已经插入了 8 次了，如果再次插入一个 why，则会出现循环踢出的问题，直到最大循环次数，然后返回一个 false。

怎么避免这个问题呢？

我们维护一个记录表，记录每个元素插入的次数就行了。

虽然逻辑简单，但是架不住数据量大呀。你想想，这个表的存储空间又怎么算呢？

优缺点

优点

1.支持删除元素。

布隆过滤器不支持删除元素

2.更节省空间。

布谷鸟哈希表更加紧凑
布谷鸟过滤器在错误率小于3%的时候空间性能是优于布隆过滤器
布谷鸟过滤器比布隆过滤器空间节省40%多

3.查询效率很高

布隆过滤器要采用多种哈希函数进行多次哈希

缺点

1.插入性能较差

布谷鸟过滤器在计算哈希后可能当前位置上已经存储了指纹，这时就要将已存储的项踢到候选桶，随着桶越来越满，产生冲突的可能性越来越大，插入耗时越来越高
布隆过滤器插入时计算好哈希直接写入位即可

2.插入重复元素存在上限

布谷鸟过滤器对已存在的值会做踢出操作，因此重复元素的插入存在上限。
布隆过滤器在插入重复元素时并没有影响，只是对已存在的位再置一遍。

3.空间大小

布谷鸟过滤器必须是2的指数。
布隆过滤器不需要2的指数。

4.删除问题

有上述重复插入的限制，删除时也会出现相关的问题：
1.删除仅在相同哈希值被插入一次时是完美的;
2.如果元素没有插入便进行删除，可能会出现误删除，这和假阳性率的原因相同;
3.如果元素插入了多次，那么每次删除仅会删除一个值，你需要知道元素插入了多少次才能删除干净，或者循环运行删除直到删除失败为止.

Redis布谷鸟过滤器：https://github.com/kristoff-it/redis-cuckoofilter

Redis通过插件支持sql及布谷鸟过滤器：https://github.com/RedBeardLab/rediSQL

扩展布谷鸟 hash原理

首先，先了解下布谷鸟hash。

image-20230624031012608

它的工作原理，总结起来是这样的：

它有两个 hash 表，记为 T1，T2。

两个 hash 函数，记为 h1，h2。

当一个不存在的元素插入的时候，会先根据 h1 计算出其在 T1 表的位置，如果该位置为空则可以放进去。

如果该位置不为空，则根据 h2 计算出其在 T2 表的位置，如果该位置为空则可以放进去。

如果该位置不为空，就把当前位置上的元素踢出去，然后把当前元素放进去就行了。

也可以随机踢出两个位置中的一个，总之会有一个元素被踢出去。

被踢出去的元素怎么办呢？没事啊，它也有自己的另外一个位置。

image-20230624031051607

上面的图说的是这样的一个事儿：

我想要插入元素 x，经过两个 hash 函数计算后，它的两个位置分别为 T1 表的 2 号位置和 T2 表的 1 号位置。

两个位置都被占了，那就随机把 T1 表 2 号位置上的 y 踢出去吧。

而 y 的另一个位置被 z 元素占领了。

于是 y 毫不留情把 z 也踢了出去。

z 发现自己的备用位置还空着（虽然这个备用位置也是元素 v 的备用位置），赶紧就位。

所以，当 x 插入之后，图就变成了这样：

image-20230624031126647

这种类似于套娃的解决方式看是可行，但是总是有出现循环踢出导致放不进 x 的问题。

当遇到这种情况时候，说明布谷鸟 hash 已经到了极限情况，应该进行扩容，或者 hash 函数的优化。

当踢来踢去了 （MaxLoop）次还没插入完成后，它会告诉你，需要 rehash 并对数组扩容了。

优化

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

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

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

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

Coding

1.redis4.0支持module,将布谷鸟过滤器加载到module中.