标签：查重 布谷鸟 元素 redis 布隆 过滤器 哈希 亿级

文章很长，且持续更新，建议收藏起来，慢慢读！疯狂创客圈总目录 博客园版 为您奉上珍贵的学习资源 ：

免费赠送 :《尼恩Java面试宝典》 持续更新+ 史上最全 + 面试必备 2000页+ 面试必备 + 大厂必备 +涨薪必备
免费赠送 :《尼恩技术圣经+高并发系列PDF》 ，帮你 实现技术自由，完成职业升级， 薪酬猛涨！加尼恩免费领
免费赠送 经典图书:《Java高并发核心编程（卷1）加强版》 面试必备 + 大厂必备 +涨薪必备 加尼恩免费领
免费赠送 经典图书:《Java高并发核心编程（卷2）加强版》 面试必备 + 大厂必备 +涨薪必备 加尼恩免费领
免费赠送 经典图书:《Java高并发核心编程（卷3）加强版》 面试必备 + 大厂必备 +涨薪必备 加尼恩免费领

免费赠送 资源宝库： Java 必备 百度网盘资源大合集 价值>10000元 加尼恩领取

---

京东面试：亿级黑名单 如何设计？亿级查重 呢？（答案含：布隆过滤器、布谷鸟过滤器）

尼恩特别说明： 尼恩的文章，都会在 《技术自由圈》 公号 发布， 并且维护最新版本。 如果发现图片 不可见， 请去 《技术自由圈》 公号 查找

尼恩说在前面

在40岁老架构师 尼恩的读者交流群(50+)中，最近有小伙伴拿到了一线互联网企业如得物、阿里、滴滴、极兔、有赞、希音、百度、网易、美团的面试资格，遇到很多很重要的面试题：

亿级海量数据查重，如何实现 ？

亿级海量数据黑名单 ，如何存储？

50亿个电话号码，如何判断是否10万个电话号码是否存在？

安全连接网址，全球数10亿的网址判断？

最近有小伙伴在面试 京东，又遇到了相关的面试题。小伙伴懵了，因为没有遇到过，所以支支吾吾的说了几句，面试官不满意，面试挂了。

所以，尼恩给大家做一下系统化、体系化的梳理，使得大家内力猛增，可以充分展示一下大家雄厚的 “技术肌肉”，让面试官爱到 “不能自已、口水直流”，然后实现”offer直提”。

当然，这道面试题，以及参考答案，也会收入咱们的 《尼恩Java面试宝典PDF》V171版本，供后面的小伙伴参考，提升大家的 3高 架构、设计、开发水平。

最新《尼恩 架构笔记》《尼恩高并发三部曲》《尼恩Java面试宝典》的PDF，请关注本公众号【技术自由圈】获取，回复：领电子书

redis 二值判断相关的面试题，是一个非常常见的高并发面试题，很多面试官也非常熟悉，上来就让面试者讲讲 redis 锁。

珍藏此文， 帮大家 吊打面试官。

首先回顾一下：四大统计（基数统计，二值统计，排序统计、聚合统计）的原理 和应用场景

尼恩这边的文章都有一个 基本的规则，从最为基础的讲起。

先看看 常见的四大统计。

亿级海量数据查重，如何实现 ？ 涉及的是四大统计其中的 二值统计

亿级海量数据黑名单 ，如何存储？涉及的也是四大统计其中的 二值统计

第1大统计：基数统计

基数（Cardinality）是指一个集合中不同元素的数量， 或者说统计一个集合中不重复元素的个数。

简单来说： 基数（Cardinality）就是去除重复后的数的个数

例如，对于一个包含重复元素的集合{1, 2, 2, 3, 4, 4, 4}，其基数为4，即不同元素的个数。

在Redis中，HashSet / HyperLogLog数据结构都能提供 高效的基数统计，而HyperLogLog算法可以在不保存原始数据的情况下快速计算出一个集合的基数。

基数统计的2大类型

类型 1：精确计算：

对于较小规模的数据集，可使用数据结构如哈希集合（HashSet）来实现基数统计。

哈希集合利用哈希函数将元素映射到存储位置，其内部会自动处理元素的插入和冲突问题。

当插入一个元素时，哈希集合会根据元素的哈希值确定存储位置，若该位置没有元素，则直接插入；若已存在元素（哈希冲突），则通过一定的冲突解决策略（如链表法或开放寻址法）来处理。

通过计算哈希集合中的元素数量，即可得到集合的基数。

类型 2：近似计算原理（以 HyperLogLog 为例）：

HyperLogLog 是一种基于概率的数据结构，用于估算大数据集的基数。

它的基本原理是将元素哈希为二进制串，然后通过统计哈希值的前导零的最大长度来估算基数。

每个不同的元素经过哈希后，其哈希值的前导零长度呈现一定的概率分布。

HyperLogLog 通过维护多个寄存器来记录这些最大长度，然后根据这些寄存器的值和一定的数学公式来估算集合中的不同元素数量。

这种方法以牺牲一定的准确性为代价，换取了对内存的高效利用，能够在有限的内存空间内处理大规模数据集。

HyperLogLog不存储数据，只记录不重复数的个数，HyperLogLog有误差，在0.8125%

基数统计的应用场景和案例

基数统计场景1：网站流量分析：

互联网公司中，用于统计网站的独立访客数量，为市场部门评估网站的用户覆盖范围和广告效果提供重要数据

例如，像百度这样的大型搜索引擎网站，每天有海量的访问请求。

通过基数统计，可以了解有多少不同的用户访问了网站，而不需要记录每个用户的详细访问信息。

使用 HyperLogLog 算法，在内存占用较小的情况下，就能快速估算出 UV/PV/ 注册IP数/ 每日访问IP数/统计在线人数:

1. 统计网站注册IP数：使用HyperLogLog可以高效地统计网站注册用户的独立IP数量，为网站运营者提供有价值的数据支持。
2. 统计每日访问IP数：通过对用户访问日志进行处理，使用HyperLogLog可以快速统计出每日的独立访问IP数，有助于分析网站流量和用户行为。
3. 统计页面实时UV PV数：在实时监控系统中，使用HyperLogLog可以估算出页面的实时访问用户数（UV）和页面访问量（PV），为网站运营者提供实时反馈。
4. 统计在线人数：在实时在线人数统计系统中，HyperLogLog可以用于估算当前在线用户的数量，为系统性能优化和用户体验改进提供数据支持。
5. APP活跃用户数：统计一个APP的日活(日活跃用户数量)、月活数(月活跃用户数量)，即每天或每月有多少不同的用户活跃

上面的基数统计，其实对应到一些常见名词：UV、PV、DAU、MAU

1. UV(Unique Visitor)：独立访客，一般为客户端IP，要去重
2. PV(Page View)：页面浏览量，不用去重
3. DAU(Daily Active User)：日活跃用户量，当天登录或者使用某个产品的用户数，要去掉重复登录的用户，多次登录只记录一次
4. MAU(Monthly Active User)：月活跃用户

基数统计场景2：数据库去重：

在数据库管理中，用于统计一个表中某列的不同值的数量。

比如，在电商数据库中，统计产品表中不同品牌的数量，有助于了解产品的品牌多样性和市场分布。

• 若数据量小，通过使用哈希集合可以精确计算基数

• 若数据量庞大，HyperLogLog 则是一种更合适的近似计算方法。

第2大统计：二值统计

二值统计通常涉及到将数据分为两个类别或状态，比如成功与失败、是与非等，并对这些类别进行计数和分析。

这种统计方法在处理二分类问题时非常常见，比如在质量控制、用户行为分析等领域。

二值统计的4大类型

类型 1：计数器数组 ：

使用一个数组作为计数器，数组的每个元素用于记录两种状态中的一种状态的数量。

例如，有一个数组counts，counts[0]用于记录状态为 0 的元素数量，counts[1]用于记录状态为 1 的元素数量。

当一个元素状态发生变化时，相应的计数器就会增加或减少。

这种方法在简单的编程场景中比较直观，适用于小规模的二值统计。

类型2：位图（Bitmap）：

位图是一种简单直观的二值统计数据结构。它将每个元素对应到位图中的一个位，位的值只能是 0 或 1，分别代表两种状态。

例如，在统计用户是否登录的场景中，将用户 ID 与位图中的位进行一一对应，若用户已登录，对应的位设为 1；若未登录，则设为 0。

通过对所有位进行扫描和计数，可以快速统计出处于两种状态的元素数量。

类型3：布隆过滤器BloomFilter

布隆过滤器底层使用一个初值全为0的bit数组和多个hash函数，

每次查找时，先将key根据hash函数映射到某个位置，判断是否为0，为0说明该数据不存在，直接返回，可以添加和快速查找元素是否存在，

添加时先对key经过所有的hash并对长度取模，得到多个位置并对每个位置设置为1，

查询时仍是得到多个位置，只要有一个为0，则该key不存在，当然，BloomFilter 判存在的时候，有误判，即使是全为1时也不一定存在，因为存在哈希冲突

类型4：布谷鸟过滤器 CuckooFilter

布隆过滤器最大的缺陷就是不能删除数据。

因此诞生了需要布隆过滤器的增强版本，布谷鸟过滤器就是其中一种。

布谷鸟过滤器可以被认为是一个增强版的布隆过滤器，它支持元素的动态添加和删除，同时提供了比传统布隆过滤器更高的查询效率和空间利用率。

布谷鸟过滤器的核心在于使用“指纹信息”代替简单的位数组来存储数据。

每个元素通过哈希函数生成一个或多个“指纹”，这些指纹被存储在过滤器中。

查询时，只需检查对应位置上是否存在相应的指纹信息即可。

相比于布隆过滤器，布谷鸟过滤器可以删除数据。

而且基于相同的集合和误报率，布谷鸟过滤器通常占用的空间更少。相对的，算法实现也就更复杂。

不过，布谷鸟过滤器 同样存有误判率。即有可能将⼀个不在集合中的元素错误的判断成在集合中。

注：布隆过滤器的误报率通过调整位数组的大小和哈希函数来控制，而布谷鸟过滤器的误报率受指纹大小和桶大小控制。桶大小：数组大小；指纹大小：每个位置存在数据个数

二值统计的应用场景和案例

二值统计的场景1：设备状态监测：

在网络设备管理中，用于统计设备的在线（1）和离线（0）状态。

例如，在一个数据中心，有大量的服务器，通过二值统计监控服务器的运行状态。可以使用计数器数组，每次服务器状态变化时更新相应的计数器。

当需要了解在线和离线服务器的数量时，直接读取计数器的值即可，以便及时发现设备故障和网络问题。

二值统计的场景2：用户行为分析：

在互联网产品中，统计用户对某个功能的使用情况。

以一款移动社交应用为例，统计用户开启或关闭推送通知功能的比例，可以使用位图来记录每个用户的推送通知状态。

通过统计位为 1（开启）和位为 0（关闭）的数量，就能得到开启和关闭推送通知的用户比例，帮助产品团队评估推送功能的受欢迎程度和对用户的干扰程度。

再以网站的签到功能为例: 电商用户签到记录，就是二值统计，可以基于bitmap二进制数组实现签到日历，用bit统计一位用户，用一个二进制bit位代表一天的签到状态

第3大统计：排序统计

排序统计涉及将数据按照一定的顺序（如升序或降序）进行排列，以便于分析和比较。

排序统计的例子，比如，可以使用ZSET对排序统计

1. 可以 使用ZSET对文章的点赞数排序并分页展示
2. 对评论根据时间进行排序

排序算法如快速排序、归并排序、堆排序等，都是排序统计中常用的方法。

排序统计的2大类型

第1类：基于比较的排序算法原理（如快速排序、归并排序）：

这些算法的基本思想是通过比较元素之间的大小关系来确定它们的顺序。

以快速排序为例，它首先选择一个基准元素，将数组分为两部分，小于基准元素的放在左边，大于基准元素的放在右边。然后对这两部分分别进行快速排序，直到整个数组有序。

排序过程中，通过不断地比较和交换元素的位置，实现元素的排序。

第2类：基于索引的数据结构原理（如有序集合）：

有序集合（Sorted Set）是一种同时具备集合和排序功能的数据结构。当插入一个新元素时，根据其排序值将元素插入到合适的位置，以保持集合的有序性。

它通过为每个元素关联一个分数（score）来实现排序。

元素按照分数的大小进行排序，分数可以是任意的数值，用于表示元素的某种属性。

例如，在一个电商系统中，将商品的价格作为分数，商品名称作为元素，就可以构建一个按照价格排序的有序集合。当插入一个新元素时，根据其分数将元素插入到合适的位置，以保持集合的有序性。

排序统计的应用场景和案例

排序统计的场景1：排行榜系统：

在游戏、音乐、电商等众多领域都有广泛应用。

例如，在游戏排行榜中，根据玩家的得分对玩家进行排名。

使用（Sorted Set）有序集合，将玩家的得分作为分数，玩家 ID 作为元素，通过有序集合的操作，可以快速插入新玩家的分数，更新排行榜，并且可以方便地获取前几名玩家的信息，用于展示排行榜页面。

排序统计的场景 2：数据筛选和统计：

在数据分析中，根据一定的数值范围对数据进行筛选和统计。

例如，在电商系统中，统计价格在某个区间的商品数量。

通过有序集合，按照商品价格进行排序后，可以使用范围查询操作，快速获取价格在指定区间的商品数量，帮助商家进行价格策略分析和库存管理。

第4大统计：聚合统计

聚合统计是一种数据处理技术，它将多个数据记录组合成一个集合，并计算该集合的统计信息，如总和、平均值、最大值和最小值等。

聚合操作通常用于数据仓库和数据分析中，以简化数据并提取有用的信息。

聚合统计的核心在于对数据进行分组（grouping），然后对每个组应用聚合函数（如sum, avg, max, min等）来计算统计值。

Redis 聚合统计的数据结构

Redis 提供了多种数据结构用于聚合统计，如集合（Set）、有序集合（Sorted Set）、哈希（Hash）等。

集合可以存储不重复的元素，通过操作命令（如SCARD统计集合元素个数、SINTER计算集合交集等）实现简单的聚合。

Redis 有序集合（ Sorted Set） 为每个元素关联一个分数，可根据分数进行排序和范围统计。

Redis 哈希（Hash） 结构以键 - 值对的形式存储数据，方便对不同属性进行统计。

Redis 聚合统计的命令执行机制

对于聚合统计命令，Redis 在内部会遍历相关的数据结构进行计算。在处理有序集合的范围统计时，会根据元素的分数，通过二分查找等算法快速定位符合范围的元素。

例如，在计算集合交集时，Redis 会逐个比较参与交集运算的集合中的元素，找出共同的元素。

聚合统计的应用场景

场景1：网站流量分析

• UV（独立访客）和 PV（页面浏览量）统计：

  通过在 Redis 中使用集合记录每个访问用户的唯一标识来统计 UV。

  每当有新用户访问，就将其 ID 添加到集合中，利用SCARD命令获取集合大小即 UV。

  对于 PV，可以在每次页面加载时，对一个计数器进行递增操作，计数器可以存储在 Redis 的字符串（String）类型中。

• 热门页面统计：

  利用有序集合，将页面 URL 作为元素，页面的访问次数作为分数。

  每次页面被访问，就更新对应的分数。通过ZRANGE命令可以获取访问次数最多的页面列表，从而找出热门页面。

场景2：电商数据分析

• 商品销售统计：使用哈希存储商品信息，如商品 ID 作为键，包含销量、销售额等信息的字典作为值。每当有商品销售，就更新对应的销量和销售额。通过遍历哈希表中的所有商品记录，可以统计总销量、总销售额等信息。
• 用户购买行为分析：用集合记录用户购买的商品类别，通过集合的交集、并集等运算，可以分析不同用户群体之间购买行为的相似性。例如，计算购买母婴产品和购买美妆产品的用户群体的交集，找出既购买母婴产品又购买美妆产品的用户。

场景3：社交平台用户行为分析

• 粉丝重合度分析：

  假设在一个社交平台上，有用户 A 和用户 B。使用 Redis 集合分别存储用户 A 的粉丝集合set:A_fans和用户 B 的粉丝集合set:B_fans。

  通过SINTER命令计算两个集合的交集SINTER set:A_fans set:B_fans，可以得到同时是用户 A 和用户 B 粉丝的用户列表。

  这个数据可以用于分析用户之间的影响力关联，例如，如果两个明星的粉丝重合度很高，可能意味着他们在某些方面具有相似的受众群体。

• 用户互动统计

  对于用户的点赞、评论、分享等互动行为，可以通过有序集合来统计。以用户发布的内容为单位，将内容 ID 作为有序集合的元素，互动次数作为分数。

  例如，有序集合zset:content_interactions存储了所有内容的互动情况。

  当一条内容获得新的互动时，更新对应的分数。

  通过ZRANGEBYSCORE命令，可以获取互动次数在一定范围内的内容列表，用于发现热门内容或者筛选出需要重点关注的内容。

场景4：游戏数据分析

• 玩家道具统计：在游戏中，使用哈希来存储玩家的道具信息。例如，哈希表hash:player_props中，键是玩家 ID，值是一个包含各种道具数量的字典。每次玩家获得或使用道具，就更新对应的道具数量。通过遍历哈希表，可以统计所有玩家的某种道具的总持有量，用于游戏平衡性分析。
• 关卡通关率统计：利用有序集合，将游戏关卡 ID 作为元素，通关玩家数量作为分数。每当有玩家通关一个关卡，就更新对应的分数。通过ZRANGE命令可以获取通关率最高的关卡列表，用于游戏关卡的优化和推荐。例如，如果某个关卡的通关率过低，开发者可以考虑调整关卡难度。

回到前面的相关面试题，都属于二值统计的类型

亿级海量数据查重，如何实现 ？

亿级海量数据黑名单 ，如何存储？

50亿个电话号码，如何判断是否10万个电话号码是否存在？

安全连接网址，全球数10亿的网址判断？

大概的方案有三个：

• 使用 BitMap 位图进行二值统计
• 使用BloomFilter 进行二值统计
• 使用Cuckoo Filter 布谷鸟过滤器 进行二值统计

使用 BitMap 位图进行二值统计

BitMap 可以用作签到、统计、用户状态等的处理

• 支持统计 1 的数量
• 支持统计某个偏移量是不是 1
• 支持多个 BitMap做And和OR等操作

除了最后一个功能，Set无法完全支持，其他都是可以支持的。

那么，为什么还需要BitSet了？

原因是空间占用。

BitSet 不是 Redis 中的数据结构，其本质是String 的内部数据结构 Bit。

我们可以理解为：一连串 Bit构成了String，每一个 Bit只能存储 0 和 1，同时有自己的偏移量，而Redis 可以根据偏移量对任何一个Bit进行 位操作 。

Redis中 String 最大可以达到 512M ，根据这个公式：($offset/8/1024/1024)MB可以算出，offset最大为4,294,967,296，也就是 2的32次方 ，所以 offset也不能大于这个值。

使用 BitMap 位图进行用户黑名单管理

key为user_blacklist，offset 是用户的 id(用户 不能大于 2^32次方, 不能大于10个亿)

以下是一个使用 Redis 的位图（BitMap）实现用户黑名单管理的示例代码：

引入 Redis 的 Java 客户端依赖，如果使用 Maven，可以在pom.xml文件中添加以下依赖：

<dependency>
    <groupId>redis.clients</groupId>
    <artifactId>jedis</artifactId>
    <version>3.3.0</version>
</dependency>

Java 实现代码如下

import redis.clients.jedis.Jedis;

public class RedisUserBlacklist {
    public static void main(String[] args) {
        // 连接到 Redis 服务器
        Jedis jedis = new Jedis("localhost", 6379);

        // 假设用户 ID 范围为 1 到 1000
        int userId = 123;

        // 将用户加入黑名单，将对应位置的位设置为 1
        jedis.setbit("user_blacklist", userId - 1, true);

        // 检查用户是否在黑名单中
        boolean isInBlacklist = jedis.getbit("user_blacklist", userId - 1);

        System.out.println("User " + userId + " is in blacklist: " + isInBlacklist);

        // 关闭连接
        jedis.close();
    }
}

在这个示例中，首先连接到本地的 Redis 服务器，然后使用setbit方法将位图中对应参与者编号的位设置为 1 表示加入黑名单，再使用getbit方法检查某个参与者是否黑名单。

问题： 上面讲到，Redis中 String 最大可以达到 512M ，根据这个公式：($offset/8/1024/1024)MB可以算出，offset最大为4,294,967,296，也就是 2的32次方 ，所以 offset也不能大于这个值。

问题1：假设40亿账号， 有1千万的黑名单， 假设使用 32 位无符号整数来表示用户 ID，那么可能需要一个非常长的位图来涵盖所有可能的用户 ID，这可能会导致内存空间的浪费， 512M 内存，可能很多都是 空闲位。

问题2： 假设100亿账号， 有1千万的黑名单，Redis中 String 最大可以达到 512M，最多也就 40多亿，可能编号不够用。

假设100亿账号， 有1千万的黑名单，使用布隆过滤器进行二值统计， 需要的内存大概只要 600kb， 内存的估算大致如下：

那么是吧 错误率提升到 0.01 ，也只要 2.5M 内存， 是 bitmap 的百分之一。

使用 布隆过滤器（Bloom Filter） 进行二值统计

布隆过滤器（英语：Bloom Filter）是 1970 年由布隆提出的。主要用于判断一个元素是否在一个集合中。

它实际上是一个很长的二进制向量和一系列随机映射函数。BloomFilter在NoSql、大数据的去重、判断数据是否存在等领域有着广泛的应用。

BloomFilter常见应用场景：

• 文档存储检查系统也采用布隆过滤器来检测先前存储的数据；

• Goole Chrome浏览器使用了布隆过滤器加速安全浏览服务；

• 垃圾邮件地址过滤；

• 爬虫URL地址去重：布隆过滤器可以用来去重已经爬取过的URL。

• 黑白名单。

• 爬虫URL地址去重；

• 著名Hbase使用了布隆过滤器来查找不存在的行或列，以及减少磁盘查找的IO次数；

• 减少 昂贵的 磁盘IO 。Google Bigtable，HBase 和 Cassandra 以及 Postgresql 使用BloomFilter来减少不存在的行或列的磁盘查找。避免代价高昂的磁盘查找会大大提高数据库查询操作的性能。

• 减少 重复推送：业务场景中判断用户是否阅读过某视频或文章，比如抖音或头条，当然会导致一定的误判，但不会让用户看到重复的内容。

• 解决缓存穿透问题 ： 缓存宕机、缓存击穿场景，一般判断用户是否在缓存中，如果在则直接返回结果，不在则查询db，如果来一波冷数据，会导致缓存大量击穿，造成雪崩效应，这时候可以用布隆过滤器当缓存的索引，只有在布隆过滤器中，才去查询缓存，如果没查询到，则穿透到db。如果不在布隆器中，则直接返回。

• WEB拦截器，如果相同请求则拦截，防止重复被攻击。用户第一次请求，将请求参数放入布隆过滤器中，当第二次请求时，先判断请求参数是否被布隆过滤器命中。可以提高缓存命中率。Squid 网页代理缓存服务器在 cache digests 中就使用了布隆过滤器。Google Chrome浏览器使用了布隆过滤器加速安全浏览服务。

• Venti 文档存储系统也采用布隆过滤器来检测先前存储的数据。

• SPIN 模型检测器也使用布隆过滤器在大规模验证问题时跟踪可达状态空间。

经典场景：解决缓存穿透的问题

一般情况下，先查询缓存是否有该条数据，缓存中没有时，再查询数据库。

当数据库也不存在该条数据时，每次查询都要访问数据库，这就是缓存穿透。

缓存穿透带来的问题是，当有大量请求查询数据库不存在的数据时，就会给数据库带来压力，甚至会拖垮数据库。

可以使用布隆过滤器解决缓存穿透的问题，把已存在数据的key存在布隆过滤器中。

当有新的请求时，先到布隆过滤器中查询是否存在，如果不存在该条数据直接返回；如果存在该条数据再查询缓存查询数据库。

经典场景：黑名单校验

发现存在黑名单中的，就执行特定操作。

比如：识别垃圾邮件，只要是邮箱在黑名单中的邮件，就识别为垃圾邮件。

假设黑名单的数量是数以亿计的，存放起来就是非常耗费存储空间的，布隆过滤器则是一个较好的解决方案。

把所有黑名单都放在布隆过滤器中，再收到邮件时，判断邮件地址是否在布隆过滤器中即可。

布隆过滤器（Bloom Filter）原理

了解布隆过滤器原理之前，先回顾下 Hash 函数原理。

哈希函数

哈希函数的概念是：将任意大小的输入数据转换成特定大小的输出数据的函数，转换后的数据称为哈希值或哈希编码，也叫散列值。

下面是一幅示意图：

所有散列函数都有如下基本特性：

• 如果两个散列值是不相同的（根据同一函数），那么这两个散列值的原始输入也是不相同的。这个特性是散列函数具有确定性的结果，具有这种性质的散列函数称为单向散列函数。
• 散列函数的输入和输出不是唯一对应关系的，如果两个散列值相同，两个输入值很可能是相同的，但也可能不同，这种情况称为“散列碰撞（collision）”。

但是用 hash表存储大数据量时，空间效率还是很低，当只有一个 hash 函数时，还很容易发生哈希碰撞。

布隆过滤器数据结构

BloomFilter 是由一个固定大小的二进制向量或者位图（bitmap）和一系列映射函数组成的。

在初始状态时，对于长度为 m 的位数组，它的所有位都被置为0，如下图所示：

当有变量被加入集合时，通过 K 个映射函数将这个变量映射成位图中的 K 个点，把它们置为 1（假定有两个变量都通过 3 个映射函数）。

查询某个变量的时候我们只要看看这些点是不是都是 1 就可以大概率知道集合中有没有它了

• 如果这些点有任何一个 0，则被查询变量一定不在；
• 如果都是 1，则被查询变量很可能存在

为什么说是可能存在，而不是一定存在呢？那是因为映射函数本身就是散列函数，散列函数是会有碰撞的。

误判率

布隆过滤器的误判是指多个输入经过哈希之后在相同的bit位置1了，这样就无法判断究竟是哪个输入产生的，因此误判的根源在于相同的 bit 位被多次映射且置 1。

这种情况也造成了布隆过滤器的删除问题，因为布隆过滤器的每一个 bit 并不是独占的，很有可能多个元素共享了某一位。如果我们直接删除这一位的话，会影响其他的元素。(比如上图中的第 3 位)

特性

• 一个元素如果判断结果为存在的时候元素不一定存在，但是判断结果为不存在的时候则一定不存在。
• 布隆过滤器可以添加元素，但是不能删除元素。因为删掉元素会导致误判率增加。

单体服务 本地布隆过滤器 Guava

首先引入Guava的依赖：

<dependency>
    <groupId>com.google.guava</groupId>
    <artifactId>guava</artifactId>
    <version>31.0.1-jre</version>
</dependency>

接下来，使用了 Google Guava 库中的布隆过滤器实现。

首先创建了一个可以容纳 1000 个整数元素且误判率为 0.01 的布隆过滤器，然后插入了一些元素，并测试了一个存在的元素和一个不存在的元素在布隆过滤器中的判断结果。

import com.google.common.hash.BloomFilter;
import com.google.common.hash.Funnels;

public class BloomFilterExample {
    public static void main(String[] args) {
        // 创建一个可以容纳 1000 个元素，误判率为 0.01 的布隆过滤器
        BloomFilter<Integer> bloomFilter = BloomFilter.create(Funnels.integerFunnel(), 1000, 0.01);

        // 插入元素
        for (int i = 1; i <= 500; i++) {
            bloomFilter.put(i);
        }

        // 查询元素
        int testValue = 450;
        boolean mightContain = bloomFilter.mightContain(testValue);
        System.out.println("布隆过滤器判断 " + testValue + " 是否存在：" + mightContain);

        // 测试误判
        int nonExistentValue = 10000;
        boolean falsePositive = bloomFilter.mightContain(nonExistentValue);
        System.out.println("布隆过滤器对不存在的值 " + nonExistentValue + " 的误判：" + falsePositive);
    }
}

注意，对于不存在的元素，布隆过滤器可能会产生误判，认为它存在于集合中。

Guava 提供的布隆过滤器的实现还是很不错的，但是它有一个重大的缺陷就是只能单机使用（另外，容量扩展也不容易），而现在互联网一般都是分布式的场景。

为了解决这个问题就需要用到Redis中的布隆过滤器了。

Redis 的 BloomFilter (布隆过滤器)

Redis4.0版本 之前的布隆过滤器可以使用Redis中的位图操作实现，

直到Redis4.0版本提供了插件功能，Redis官方提供的布隆过滤器才正式登场。

Redis4.0版本 开始，布隆过滤器作为一个插件加载到Redis Server中，就会给Redis提供了强大的布隆去重功能。

Redis 的 BloomFilter (布隆过滤器), 通过 一个可扩展的模块 RedisBloom 这个 Module 实现。

RedisBloom 是一款集成了众多功能的 RedisModule 模块。

RedisBloom 这个 Module 内集成了很多的小功能，其中主要包括：可扩展的布隆过滤器（BloomFilter），可扩展的布谷鸟过滤器（CuckooFilter），最小计数草图（Count-Min Sketch），近似百分位（T-Digest），头部K元素（TopK）等。

可扩展的模块 RedisBloom 这个 Module 的官方地址如下：

• 官网：https://redisbloom.io/
• GitHub 地址：https://github.com/RedisBloom/RedisBloom
• 命令文档地址：https://redis.io/docs/stack/bloom/
• 支持功能：
  • 可扩展的 BloomFilter (布隆过滤器) ： 用于确定一个元素是否存在于一个集群中；
  • 可扩展的 CuckooFilter (布谷鸟过滤器) ： 用于确定一个元素是否存在于一个集合中；
  • Count-Min Sketch (最小计数草图) ： 用于估计一个数据的出现次数；
  • T-Digest (近似百分位) ：
  • TopK ： 维护了 k 个最常见项目的列表；

可扩展的布隆过滤器（BloomFilter），可扩展的布谷鸟过滤器（CuckooFilter），最小计数草图（Count-Min Sketch），近似百分位（T-Digest），头部K元素（TopK）等。其中很多功能都是依据 BloomFilter 类 的相关功能来进行实现的。

安装REDIS 和 REDISBLOOM插件

编译安装redis

#下载
[root@localhost redis]# /root/redis
[root@localhost redis]# wget https://download.redis.io/releases/redis-5.0.5.tar.gz
 
#解压安装
[root@localhost redis]# tar -zxvf redis-5.0.5.tar.gz
[root@localhost redis]# ls
redis-5.0.5  redis-5.0.5.tar.gz
[root@localhost redis]# cd redis-5.0.5
[root@localhost redis-5.0.5]# make

　　

下载REDISBLOOM插件

https://github.com/RedisLabsModules/redisbloom/

tag:https://github.com/RedisBloom/RedisBloom/tags

下载压缩包

[root@localhost redis]# wget https://github.com/RedisBloom/RedisBloom/archive/v2.2.1.tar.gz

解压并安装，生成.so文件

[root@localhost redis]# tar -zxf v2.2.1.tar.gz 
[root@localhost redis]# ls
redis-5.0.5  redis-5.0.5.tar.gz  RedisBloom-2.2.1  v2.2.1.tar.gz
[root@localhost redis]# cd RedisBloom-2.2.1/
[root@localhost RedisBloom-2.2.1]# make
[root@localhost RedisBloom-2.2.1]# ls
changelog  contrib  Dockerfile  docs  LICENSE  Makefile  mkdocs.yml  ramp.yml  README.md  redisbloom.so  rmutil  src  tests

在redis配置文件(redis.conf)中加入该模块即可

[root@localhost redis-5.0.5]# pwd
/root/redis/redis-5.0.5
[root@localhost redis-5.0.5]# ls
00-RELEASENOTES  CONTRIBUTING  deps     Makefile   README.md   runtest          runtest-moduleapi  sentinel.conf  tests
BUGS             COPYING       INSTALL  MANIFESTO  redis.conf  runtest-cluster  runtest-sentinel   src            utils
[root@localhost redis-5.0.5]# ls |grep redis.conf
redis.conf

　配置文件添加.so文件

[root@localhost redis-5.0.5]# vim redis.conf

启动REDIS

[root@localhost redis-5.0.5]# ./src/redis-server ./redis.conf &

#查看是否启动成功
[root@localhost redis-5.0.5]# ps -ef|grep 6379
root       4234   4176  0 22:12 pts/0    00:00:07 ./redis-server *:6379
root       8744   4176  0 23:06 pts/0    00:00:00 grep --color=auto 6379

连接客户端

[root@localhost redis-5.0.5]# ./src/redis-cli 
127.0.0.1:6379> keys *
(empty list or set)
127.0.0.1:6379> 

Redis 的 BloomFilter 相关命令

REDISBLOOM基本操作命令：

命令	格式	说明
bf.reserve	bf.reserve {key} {error_rate}	创建一个大小为initial_size位向量长度，错误率为error_rate的空的Bloom过滤器
bf.add	bf.add{key}	向key指定的Bloom中添加一个元素item
bf.madd	bf.madd {key} {item} {item2} {item3} …	一次添加多个元素
bf.exists	bf.exists {key}	查询元素是否存在
bf.mexists	bf.mexists {key} {item} {item2} {item3} …	检查多个元素是否存在
bf.info	bf.info	查询key指定的Bloom的信息
bf.debug	bf.debug	查看BloomFilter的内部详细信息（如每层的元素个数、错误率等）
cf.reserve	cf.reserve {key}	创建一个initial_size位向量长度的空的Bloom过滤器
cf.add	cf.add {key}	向key指定的Bloom中添加一个元素item
cf.exists	cf.exists {key}	检查该元素是否存在
bf.scandump	bf.scandump {key}	(key：布隆过滤器的名字,iter：首次调用传值0，或者上次调用此命令返回的结果值)对Bloom进行增量持久化操作（增量保存）
bf.localchunk	bf.localchunk {key} {iter}	加载SCANDUMP持久化的Bloom数据（key：目标布隆过滤器的名字，iter：SCANDUMP返回的迭代器的值，和data一一对应，data：SCANDUMP返回的数据块（data chunk））

以下命令仅参考当时的最新的代码，详细的准确命令请参考 社区命令文档地址 。

• bf.add : 向目标布隆过滤器中添加一个元素；
• bf.madd : 向目标布隆过滤器中添加多个元素；
• bf.exists : 在目标布隆过滤器中判断一个元素是否存在；
• bf.mexists : 在目标布隆过滤器中判断多个元素是否存在；
• bf.info : 查看对应布隆过滤器的基础信息；
• bf.debug : 查看对应布隆过滤器的详细信息（包含每个布隆过滤器表的信息）；
• bf.insert : 向目标布隆过滤器中插入元素，如果对应布隆过滤器不存在则创建；
• bf.reserve : 修改目标布隆过滤器的属性；
• bf.loadchunk : 布隆过滤器从 AOF 中加载数据时用到的命令；
• bf.scandump : 布隆过滤器向 AOF 中持久化数据时用到的命令；

Redis 的 BloomFilter 的c++编码结构

一个可扩展的布隆过滤器所依赖的主要数据结构如下所示：

typedef struct SBChain {
    SBLink *filters;  // 记录所有的布隆过滤器
    size_t size;      // 记录当前所有布隆过滤器可存储元素的数量
    size_t nfilters;  // 记录当前布隆过滤器数据的个数
    unsigned options; // 创建布隆过滤器表所依赖的参数
    unsigned growth;  // 创建新的布隆过滤器时其容量是上一个布隆过滤器的容量倍数
} SBChain;

typedef struct SBLink {
    struct bloom inner; // 对应的布隆过滤器
    size_t size;        // 已插入布隆过滤器表中的元素的个数
} SBLink;

struct bloom {
    uint32_t hashes;   // 记录当前的hash数量
    uint8_t force64;
    uint8_t n2;
    uint64_t entries;  // 记录当前布隆过滤器的容量

    double error;      // 记录当前布隆过滤器的误判率
    double bpe;

    unsigned char *bf; // 指向布隆过滤器存储内容的内存块
    uint64_t bytes;    // 记录布隆过滤器存储内容的内存块的大小（字节）
    uint64_t bits;     // 记录布隆过滤器存储内容的内存块的大小（比特）
};

BloomFilter 存储结构

Redis 的 BloomFilter 的哈希规则（插入/判断规则）

按照布隆过滤器的计算规则，在不同的误判率的情况下我们需要使用多个不同的哈希函数计算对应的比特位，我们接下来看一下布隆过滤器的判断/插入规则：

哈希算法： MurmurHash64A

判断方式：

• 首先使用固定的哈希种子，对传入的元素计算其哈希值，并将其作为基础的哈希值；
• 然后使用传入元素的哈希值作为哈希种子，计算下一次哈希位置的步进值；
• 利用得到的传入元素的哈希特征，在多个布隆过滤器中进行判断元素是否存在；
  • 判断基础的哈希值对应的比特索引；
  • 利用计算的步进值，判断下一个对应的比特索引；

// 计算传入元素的哈希特征
bloom_hashval bloom_calc_hash64(const void *buffer, int len) {
    bloom_hashval rv;
    rv.a = MurmurHash64A_Bloom(buffer, len, 0xc6a4a7935bd1e995ULL);
    rv.b = MurmurHash64A_Bloom(buffer, len, rv.a);
    return rv;
}

// 判断多个布隆过滤器中的对应比特位
for (int ii = sb->nfilters - 1; ii >= 0; --ii) {
    if (bloom_check_h(&sb->filters[ii].inner, h)) {
        return 0;
    }
}

Redis Client客户端中布隆过滤器的基本使用

在Redis中，布隆过滤器有两个基本命令，分别是：

• bf.add：添加元素到布隆过滤器中，类似于集合的sadd命令，不过bf.add命令只能一次添加一个元素，如果想一次添加多个元素，可以使用bf.madd命令。
• bf.exists：判断某个元素是否在过滤器中，类似于集合的sismember命令，不过bf.exists命令只能一次查询一个元素，如果想一次查询多个元素，可以使用bf.mexists命令。

比如：

> bf.add one-more-filter fans1
(integer) 1
> bf.add one-more-filter fans2
(integer) 1
> bf.add one-more-filter fans3
(integer) 1
> bf.exists one-more-filter fans1
(integer) 1
> bf.exists one-more-filter fans2
(integer) 1
> bf.exists one-more-filter fans3
(integer) 1
> bf.exists one-more-filter fans4
(integer) 0
> bf.madd one-more-filter fans4 fans5 fans6
1) (integer) 1
2) (integer) 1
3) (integer) 1
> bf.mexists one-more-filter fans4 fans5 fans6 fans7
1) (integer) 1
2) (integer) 1
3) (integer) 1
4) (integer) 0

上面的例子中，没有发现误判的情况，是因为元素数量比较少。

当元素比较多时，可能就会发生误判，怎么才能减少误判呢？

Redis Client 创建一个自定义参数的布隆过滤器

上面的例子中使用的布隆过滤器，只是默认参数的布隆过滤器，它在我们第一次使用bf.add命令时自动创建的。

Redis还提供了自定义参数的布隆过滤器，想要尽量减少布隆过滤器的误判，就要设置合理的参数。

在使用bf.add命令添加元素之前，使用bf.reserve命令创建一个自定义的布隆过滤器。

bf.reserve命令有三个参数，分别是：

• key：键
• error_rate：期望错误率，期望错误率越低，需要的空间就越大。
• capacity：初始容量，当实际元素的数量超过这个初始化容量时，误判率上升。

比如：

>  bf.reserve one-more-filter 0.0001 1000000
OK

如果对应的key已经存在时，在执行bf.reserve命令就会报错。

如果不使用bf.reserve命令创建，而是使用Redis自动创建的布隆过滤器，默认的error_rate是 0.01，capacity是 100。

布隆过滤器的error_rate越小，需要的存储空间就越大，对于不需要过于精确的场景，error_rate设置稍大一点也可以。

布隆过滤器的capacity设置的过大，会浪费存储空间，设置的过小，就会影响准确率，所以在使用之前一定要尽可能地精确估计好元素数量，还需要加上一定的冗余空间以避免实际元素可能会意外高出设置值很多。

总之，error_rate和 capacity都需要设置一个合适的数值。

实战：使用redisson 布隆过滤器实现用户黑名单

pom中引入redisson依赖:

<dependency>
    <groupId>org.redisson</groupId>
    <artifactId>redisson</artifactId>
    <version>3.16.0</version>
</dependency>

编写代码测试

import org.redisson.Redisson;
import org.redisson.api.RBloomFilter;
import org.redisson.api.RedissonClient;
import org.redisson.config.Config;

public class RedissonBloomFilterBlacklist {
    public static void main(String[] args) {
        // 创建 Redisson 配置
        Config config = new Config();
        config.useSingleServer().setAddress("redis://127.0.0.1:6379");

        // 创建 Redisson 客户端
        RedissonClient redisson = Redisson.create(config);

        // 创建布隆过滤器，用于存储用户黑名单
        RBloomFilter<String> blacklistFilter = redisson.getBloomFilter("userBlacklist");
        // 初始化布隆过滤器，预计存储 10000 个元素，误报率为 0.01
        blacklistFilter.tryInit(10000, 0.01);

        // 将用户 ID 添加到黑名单
        blacklistFilter.add("user123");
        blacklistFilter.add("user456");

        // 检查用户是否在黑名单中
        boolean isInBlacklist = blacklistFilter.contains("user123");
        System.out.println("User123 is in blacklist: " + isInBlacklist);

        boolean isNotInBlacklist = blacklistFilter.contains("user789");
        System.out.println("User789 is in blacklist: " + isNotInBlacklist);

        // 关闭 Redisson 客户端
        redisson.shutdown();
    }
}

在这个示例中，首先创建了 Redisson 客户端连接到 Redis 服务器。

然后创建了一个布隆过滤器，用于存储用户黑名单。

可以将用户 ID 添加到布隆过滤器中，并检查某个用户 ID 是否在黑名单中。

注意，布隆过滤器存在一定的误报率，即可能会将不在黑名单中的用户误判为在黑名单中，但不会出现漏报（即真正在黑名单中的用户一定能被检测到）。

实战：BloomFilter实现亿级海量数据查重/亿级海量数据黑名单

package com.crazymaker.cloud.redis.redission.demo.business;

import io.rebloom.client.Client;
import lombok.extern.slf4j.Slf4j;
import org.springframework.beans.factory.annotation.Autowired;
import org.springframework.stereotype.Service;
import redis.clients.jedis.Jedis;
import redis.clients.jedis.JedisPool;

/**
 * redis BloomFilter 布隆过滤器module 基于位图算法
 * 功能：海量数据（亿级）查重
 * 优点：占用内存极少，并且插入和查询速度都足够快
 * 缺点：随着数据的增加，误判率会增加；还有无法判断数据一定存在；另外还有一个重要缺点，无法删除数据。
 */
@Slf4j
@Service
public class RedisModuleBloomFilter {

    @Autowired
    private JedisPool jedisPool;

    /**
     * 手机号是否存在检测
     *
     * @param filterName 过滤器名称
     * @param phone      手机号
     * @return true 表示存在
     */
    public boolean isExist(String filterName, String phone) {

        boolean booleans = false;
        try {
            //log.info("[名单过滤]数据：应用过滤器：{}，开始：{}", filterName, System.currentTimeMillis());
            booleans = getClient().exists(filterName, phone);
            //log.info("[名单过滤]数据：应用过滤器：{}，结束：{}", filterName, System.currentTimeMillis());

        } catch (Exception e) {
            e.printStackTrace();
        }

        return booleans;
    }

    /**
     * 多手机号 是否存在检测
     *
     * @param filterName
     * @param phones     手机号数组
     * @return 返回对应的数组，true 表示存在
     */
    public boolean[] isExist(String filterName, String[] phones) {

        if (null == phones || phones.length < 1) {
            return null;
        }

        if (phones.length > 1000000) {
            return null;
        }

        boolean[] booleans = null;
        try {

            //log.info("[名单过滤]数据：应用过滤器：{}，开始：{}", filterName, System.currentTimeMillis());
            booleans = getClient().existsMulti(filterName, phones);
            //log.info("[名单过滤]数据：应用过滤器：{}，结束：{}", filterName, System.currentTimeMillis());

        } catch (Exception e) {
            e.printStackTrace();
        }

        return booleans;
    }


    /**
     * 数据添加到过滤器
     *
     * @param filterName 过滤器名称
     * @param phones     要添加的手机号
     * @return
     */
    public boolean[] addFilter(String filterName, String[] phones) {

        if (null == phones || phones.length < 1) {
            return null;
        }

        boolean[] booleans = null;
        try {
            log.info("[过滤器添加数据]数据：应用过滤器：{}，开始：{}", filterName, System.currentTimeMillis());
            booleans = this.getClient().addMulti(filterName, phones);
            log.info("[过滤器添加数据]数据：应用过滤器：{}，结束：{}", filterName, System.currentTimeMillis());
        } catch (Exception e) {
            e.printStackTrace();
        }

        return booleans;
    }

    /**
     * 初始化过滤器
     */
    public void initFilter() {

        try {
            Client client = this.getClient();

            log.info("[初始化过滤器]数据：应用过滤器开始：{}", System.currentTimeMillis());
            //初始化过滤器 投诉
            client.createFilter("REDIS_BLOOM_FILTERS_SYSTEM_BLACK_COMPLAINT", 500000, 0.0001);
            //初始化过滤器 回T
            client.createFilter("REDIS_BLOOM_FILTERS_SYSTEM_BLACK_T", 200000, 0.0001);
            log.info("[初始化过滤器]数据：应用过滤器结束：{}", System.currentTimeMillis());

        } catch (Exception e) {
            e.printStackTrace();
        }

    }

    public Client getClient() {

        Client client = new Client(jedisPool);
        return client;
    }

    public Client getClient(JedisPool pool) {

        Client client = new Client(pool);

        return client;
    }
}

布隆过滤器的大小预估

如下地址是一个免费的在线布隆过滤器在线计算的网址：
点击这里

经过哈希计算次数设置为3次，这个3%的误判率和3次哈希运算需要多大空间位数组呢？

计算得到的结果是984.14KiB，100W的key才占用了0.98M，而如果是10亿呢，计算的结果是960M，这个内存空间是完全可以接受的。

布隆过滤器的优点和缺点

和BitMap相比，BloomFilter 有个巨大的性能优点：内存仅占用其 1/10 甚至不到

相比于其它的数据结构，布隆过滤器在空间和时间方面都有巨大的优势。

布隆过滤器存储空间和插入/查询时间都是常数 ，另外，散列函数相互之间没有关系，方便由硬件并行实现。

该模块主要用于判断某个元素是否存在，利用 BitMap这样的数据结构，在牺牲可接受范围的精度下极大提高了内存使用率和性能，查询复杂度约为 O(hash fun number)，和 redis 原有的 set 结构（非 zip set int）相比，内存仅占用其 1/10 甚至不到。

以下为 redis 中和 set 的测试内存结果对比： 测试元素 100w ，元素大小 32 个字节

# 布隆过滤器
# Memory
used_memory:4714576
used_memory_human:4.50M

# set
# Memory
used_memory:73434368
used_memory_human:70.03M
123456789

根据以上结果，似乎布隆过滤器十分优秀，但由于原理的限制，布隆过滤器无法进行元素删除。

BloomFilter 同 BitSet 对比

• BloomFilter 是不可以删除元素的，BitSet 可以
• BitSet 的偏移量是有限的，BloomFilter 却不是
• BitSet 的结果是精准的，BloomFilter 却是存在偏差的
• BitSet 的复杂度不是恒订的，偏差值越大，时间复杂度越高。Bloomfilter 是恒定的

布隆过滤器的优点：

• 支持海量数据场景下高效判断元素是否存在
• 布隆过滤器存储空间小，并且节省空间，不存储数据本身，仅存储hash结果取模运算后的位标记
• 不存储数据本身，比较适合某些保密场景

布隆过滤器的 问题

3的缺点：

• 只能添加不能删除
• 假阳性问题：判断结果为存在的场景，有误判，匹配结果如果是“存在于过滤器中”，实际不一定存在
• 当容量快满时，hash碰撞的概率变大，插入、查询的错误率也就随之增加了

布隆过滤器的 问题 具体的介绍如下:

1. 只能添加不能删除，

   因为多个key映射的位置可能相同，如果删除一个，可能导致本来存在的也会被认为不存在，因为存在哈希冲突，可能添加的两个元素占一个坑位，此时如果删除其中一个则另一个的该坑位也为0，也会被认为删除，就会导致误判率增加，故不要轻易删除key

2. 假阳性问题：判断结果为存在的场景，有误判

   布隆过滤器中一个元素如果判断结果为存在的时候元素不一定存在，但是判断结果为不存在的时候则一定不存在。因此，布隆过滤器不适合那些对结果必须精准的应用场景。

   全为1不一定存在，有一个0则一定不存在，误判就是把认为存在的，可能不存在的

3. 尽可能使得初始bit数组足够大，不要后续扩容

   当容量快满时，hash碰撞的概率变大，插入、查询的错误率也就随之增加了

   当实际元素过大时，远远大于初始数组，则必须对布隆过滤器重建，否则误判率会非常大，此时重新分配一个更大的bit数组，然后将原来的元素重新添加进入，再继续判断

   使用时要尽可能使得初始bit数组足够大，不要后续扩容，后续要进行重建

   当bitmap过小时，要进行重建，重新创建一个更大的bitmap，然后将数据重新加入

其他问题

• 不支持计数，同一个元素可以多次插入，但效果和插入一次相同
• 由于错误率影响hash函数的数量，当hash函数越多，每次插入、查询需做的hash操作就越多

Cuckoo Filter 布谷鸟过滤器

为了解决布隆过滤器不能删除元素的问题, 论文《Cuckoo Filter：Better Than Bloom》作者提出了布谷鸟过滤器。

布谷鸟过滤器就是布隆过滤器的升级版，全面优化了布隆过滤器的痛点。

布谷鸟哈希（Cuckoo Hashing）是一种哈希表的实现方式，它允许多个元素映射到同一个哈希桶（或称为槽位）。

这种哈希方法得名于布谷鸟的寄生繁殖行为，即布谷鸟将蛋产在其他鸟的巢中，迫使其他鸟抚养其后代。

为啥要取名布谷鸟呢? 有个成语，「鸠占鹊巢」,布谷鸟也是。

布谷鸟从来不自己筑巢, 它将自己的蛋产在别人的巢里，让别人来帮忙孵化。

待小布谷鸟破壳而出之后，因为布谷鸟的体型相对较大，它又将养母的其它孩子（还是蛋）从巢里挤走 —— 从高空摔下夭折了。

布谷鸟哈希结构的原理

布谷鸟哈希结构是一种哈希表实现方式，它通过使用多个哈希函数和“踢出”机制来解决哈希冲突问题。

布谷鸟哈希（Cuckoo Hashing）是一种用于高效实现哈希表的数据结构和算法。它的主要目的是在处理哈希冲突时，通过特定的策略来保证数据的快速插入、查询和删除操作，同时尽量减少哈希冲突对性能的影响。

其核心思想是使用多个哈希函数（通常为两个或更多）来确定元素在哈希表中的存储位置。例如，假设有两个哈希函数和，当插入一个元素时，会先尝试将其插入到所对应的位置。如果该位置已经被其他元素占用（发生哈希冲突），则会根据一定的规则 “驱逐” 当前占用该位置的元素，并将被驱逐的元素重新插入到所对应的位置。

这个过程可能会持续进行，直到所有元素都找到合适的位置或者达到一定的重试次数限制。

在布谷鸟哈希中，当发生哈希冲突时，元素不是被简单地放在同一个桶中，而是会“踢出”已有的元素，并将这个被踢出的元素重新哈希到另一个位置。

是一种鸠占鹊巢的策略，最原始的布谷鸟哈希方法是使用两个哈希函数对一个key进行哈希，得到桶中的两个位置，此时

• 如果两个位置都为为空则将key随机存入其中一个位置
• 如果只有一个位置为空则存入为空的位置
• 如果都不为空，则随机踢出一个元素，踢出的元素再重新计算哈希找到相应的位置

当然假如存在绝对的空间不足，那老是踢出也不是办法，所以一般会设置一个踢出阈值，如果在某次插入行为过程中连续踢出超过阈值，则进行扩容。

Cuckoo Filter 插入

Cuckoo Filter 布谷鸟过滤器的插入是重点，与朴素的布谷鸟哈希不同，布谷鸟过滤器采取了两个并不独立的哈希函数，

布谷鸟过滤器也是由两个或者多个哈希函数构成，布谷鸟过滤器的布谷鸟哈希表的基本单位称为条目（entry）。

每个条目存储一个指纹（fingerprint），指纹指的是使用一个哈希函数生成的n位比特位，n的具体大小由所能接受的误判率来设置，论文中的例子使用的是8bits的指纹大小。

具体的指纹是通过哈希函数取一定量的比特位

fp = fingerprint(x)

假设要计算条目（entry） x的 两个桶的索引p1 、P2 ， 具体的 函数如下

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

p1 、P2 即计算出来两个桶的索引，其中

• 第一个桶的索引是通过某个哈希函数计算出来，

• 第二个是使用第一个索引和指纹的哈希做了一个异或操作，

进行异或操作的好处是，因为异或操作的特性：同为0不同为1，且0和任何数异或是这个数的本身。

那么反过来，p1也可以通过p2和指纹异或来计算。

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

换句话说，在桶中迁走一个键，我们直接用当前桶的索引ii和存储在桶中的指纹计算它的备用桶。

上图（a）(b)展示了一个基本的布谷鸟哈希表的插入操作，是由一个桶数组组成，每个插入项都有由散列函数h1(x)和h2(x)确定的两个候选桶。

哈希表由一个桶数组组成，其中一个桶可以有多个条目（比如上述图c中有四个条目）。

而每个桶中有四个指纹位置，意味着一次哈希计算后布谷鸟有四个“巢“可用，而且四个巢是连续位置，可以更好的利用cpu高速缓存。

也就是说每个桶的大小是4*8bits。

Cuckoo Filter 插入时的踢出

最简单的布谷鸟哈希结构是一维数组结构，会有两个 hash 算法将新来的元素映射到数组的两个位置。

如果两个位置中有一个位置为空，那么就可以将元素直接放进去。

但是如果这两个位置都满了，它就不得不「鸠占鹊巢」，随机踢走一个，然后自己霸占了这个位置。

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

不同于布谷鸟的是，布谷鸟哈希算法会帮这些受害者（被挤走的蛋）寻找其它的窝。

因为每一个元素都可以放在两个位置，只要任意一个有空位置，就可以塞进去。

所以这个伤心的被挤走的蛋会看看自己的另一个位置有没有空，如果空了，自己挪过去也就皆大欢喜了。但是如果这个位置也被别人占了呢？

好，那么它会再来一次「鸠占鹊巢」，将受害者的角色转嫁给别人。然后这个新的受害者还会重复这个过程直到所有的蛋都找到了自己的巢为止。

布谷鸟过滤器本质上是一个 桶数组，每个桶中保存若干数量的 指纹（指纹由元素的部分 Hash 值计算出来）。

定义一个布谷鸟过滤器，每个桶记录 2 个指纹，5 号桶和 11 号桶分别记录保存 a, b 和 c, d 元素的指纹，如下所示：

此时，向其中插入新的元素 e，发现它被哈希到的两个候选桶分别为 5 号 和 11 号，但是这两个桶中的元素已经添加满了：

按照布谷鸟过滤器的特性，它会将其中的一个元素重哈希到其他的桶中（具体选择哪个元素，由具体的算法指定），新元素占据该元素的位置，如下：

以上便是向布谷鸟过滤器中添加元素并发生冲突时的操作流程，在我们的例子中，重新放置元素 e 触发了另一个重置，将现有的项 a 从桶 5 踢到桶 15。

这个过程可能会重复，直到找到一个能容纳元素的桶，这就使得布谷鸟哈希表更加紧凑，因此可以更加节省空间。如果没有找到空桶则认为此哈希表太满，无法插入。

Cuckoo Filter 查找

布谷鸟过滤器的查找过程很简单，给定一个项 x ，算法首先根据上述插入公式，计算x的指纹和两个候选桶。

然后读取这两个桶：如果两个桶中的任何 Item 与现有指纹匹配，则布谷鸟过滤器返回true，否则过滤器返回false。

此时，只要不发生桶溢出，就可以确保没有假阴性。

Cuckoo Filter 删除

标准BloomFilter 布隆过滤器不能删除，因此删除单个项需要重建整个BloomFilter 过滤器，而计数BloomFilter 布隆过滤器需要更多的空间。

布谷鸟过滤器就像计数布隆过滤器，可以通过从哈希表删除相应的指纹删除插入的项。

具体删除的过程也很简单，检查给定项的两个候选桶；如果任何桶中的指纹匹配，则从该桶中删除匹配指纹的一份副本。

Cuckoo Filter 的问题和优化

但是会遇到一个问题，那就是如果数组太拥挤了，连续踢来踢去几百次还没有停下来，这时候会严重影响插入效率。

这时候布谷鸟哈希会设置一个阈值，当连续占巢行为超出了某个阈值，就认为这个数组已经几乎满了。这时候就需要对它进行扩容，重新放置所有元素。

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

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

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

优化的两个方案

方案之一是增加 hash 函数

让每个元素不止有两个巢，而是三个巢、四个巢。这样可以大大降低碰撞的概率，将空间利用率提高到 95%左右。

方案之二是在数组的每个位置上挂上多个座位

是在数组的每个位置上挂上多个座位

这样即使两个元素被 hash 在了同一个位置，也不必立即「鸠占鹊巢」，因为这里有多个座位，你可以随意坐一个。

除非这多个座位都被占了，才需要进行挤兑。很明显这也会显著降低挤兑次数。这种方案的空间利用率只有 85%左右，但是查询效率会很高，同一个位置上的多个座位在内存空间上是连续的，可以有效利用 CPU 高速缓存。

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

和Cuckoo Filter 相比，BloomFilter 的不足

相比布谷鸟过滤器，布隆过滤器有以下不足：查询性能弱、空间利用效率低、不支持反向操作（删除）以及不支持计数。

布隆过滤器 BloomFilter 查询性能弱

因为布隆过滤器需要使用多个 hash 函数探测位图中多个不同的位点，这些位点在内存上跨度很大，会导致 CPU 缓存行命中率低。

布隆过滤器BloomFilter 空间效率低

因为在相同的误判率下，布谷鸟过滤器的空间利用率要明显高于布隆，空间上大概能节省 40% 多。

不过布隆过滤器并没有要求位图的长度必须是 2 的指数，而布谷鸟过滤器必须有这个要求。从这一点出发，似乎布隆过滤器的空间伸缩性更强一些。

布隆过滤器 BloomFilter 不支持反向删除操作

这个问题着实是击中了布隆过滤器的软肋。

在一个动态的系统里面元素总是不断的来也是不断的走。布隆过滤器就好比是印迹，来过来就会有痕迹，就算走了也无法清理干净。

比如，本来只留下 1kw 个元素，但是整体上来过了上亿的流失元素，布隆过滤器很无奈，它会将这些流失的元素的印迹也会永远存放在那里。

随着时间的流失，这个过滤器会越来越拥挤，直到有一天你发现它的误判率太高了，不得不进行重建。

布谷鸟过滤器在论文里声称自己解决了这个问题，它可以有效支持反向删除操作。

而且将它作为一个重要的卖点，诱惑你们放弃布隆过滤器改用布谷鸟过滤器。

Redis 的 CuckooFilter (布谷鸟过滤器)

布谷鸟过滤器在某些场景下能够比布隆过滤器提供更好的填充率，并且支持了删除元素，在某些场景下也为很多业务提供了更好的支持。

Redis 的 CuckooFilter (布谷鸟过滤器)相关命令

以下命令仅参考当时的最新的代码，详细的准确命令请参考 社区命令文档地址 。

• cf.add : 向目标布谷鸟过滤器中添加一个元素；
• cf.addnx : 向目标布谷鸟过滤器中添加一个元素，只有当元素不存在时才会添加成功；
• cf.count : 计算在目标布谷鸟过滤器中对应元素的个数，由于是计算对应元素的指纹的存在个数，因此最终结果可能不准确；
• cf.del : 从布谷鸟过滤器中删除一个元素，删除的是元素的指纹，并且只删除一次；
• cf.exists : 判断布谷鸟过滤器中对应元素是否存在；
• cf.mexists : 判断布谷鸟过滤器中多个元素是否存在；
• cf.info : 获取布谷鸟过滤器的信息；
• cf.insert : 向布谷鸟过滤器中插入一个元素，如果布谷鸟过滤器不存在则创建；
• cf.insertnx : 向布谷鸟过滤器中插入一个元素，如果布谷鸟过滤器不存在则创建，如果对应元素已经存在则不会插入成功；
• cf.reserve : 修改对应布谷鸟过滤器的属性；
• cf.loadchunk : 持久化的相关命令；
• cf.scandump : 持久化的相关命令；

Redis 的 布谷鸟过滤器 的主要c++ 数据结构

Redis 的 布谷鸟过滤器 的主要c++ 数据结构如下所示：

typedef struct {
    uint64_t numBuckets;     // bucket 的数量，大小为2次幂的值
    uint64_t numItems;       // 插入元素的数量
    uint64_t numDeletes;     // 删除元素的数量
    uint16_t numFilters;     // 所有子布谷鸟过滤器的数量
    uint16_t bucketSize;     // 每个 bucket 中可以存储指纹的数量，默认为2
    uint16_t maxIterations;  // 寻找指纹的存储空间时的最大迭代次数，默认为20次
    uint16_t expansion;      // 扩展倍数，大小为2次幂的值，默认为2
    SubCF *filters;          // 所有子布谷鸟过滤器信息的数组
} CuckooFilter;

typedef struct {
    uint32_t numBuckets;     // bucket 的数量，大小为2次幂的值
    uint8_t bucketSize;      // 每个 bucket 中可以存储指纹的数量
    uint8_t *data;           // 实际存储数据的内存块指针
} SubCF;

typedef struct {
    uint64_t i1;             // 记录元素的一个哈希值
    uint64_t i2;             // 记录元素的另一个哈希值
    uint8_t fp;              // 指纹的大小是1到255
} CuckooKey;

Redis 的 布谷鸟过滤器 哈希规则（插入/判断规则）

按照布谷鸟过滤器的计算规则，当我们需要判断一个元素是否存在的时候, 需要判断两个位置上的空间中是否存在特定的指纹信息；

当需要进行插入操作的时候需要从两个索引的位置上随机找到一个空余的空间进行插入操作，因此针对于每一个传入的元素，我们都会生成两个对应的特征值。

哈希算法： MurmurHash64A

判断方式：

• 依据传入的元素，利用哈希算法 MurmurHash64A 计算其哈希值；
• 利用哈希值计算对应传入元素的指纹信息(fp)，以及对应的两个哈希特征值(h1 和 h2)；
• 依次判断多个子布谷鸟过滤器中是否有足够的空间来存储新的元素；
• 每次都使用传入元素的两个哈希特征值 h1 和 h2判断在对应的 bucket 的数组中是否存在空位置：
  • 如果有空位置则将对应的元素指纹插入对应空位；
  • 如果没有空位置则尝试进行踢除操作；
• 插入元素或者判断元素是否存在结束；

Redis 的 布谷鸟过滤器 踢除规则

由于不同传入值的指纹可能相同，同一个 bucket 的空间可能会被其他相同指纹的传入值占满，导致新的值无法插入，这时就需要对已有空间中的值进行踢除操作。

相关函数：Filter_KOInsert

具体流程：

1. 将从最新的布谷鸟过滤器中执行踢除操作；

2. 依据传入值的其中一个哈希值，找到对应的 bucket 的位置，获取其中特定位置中的指纹信息，然后将新的指纹存储到特定位置上；

3. 寻找上次获取到的 bucket 中的老的指纹的下一个位置点，判断对应的 bucket 中是否有空闲位置：

   • 如果有空闲位置，则将之前替换出的指纹存到新 bucket 的空闲位置中；

   • 如果没有空闲位置，则再次进行寻找，再次从第2步开始；

Redis Client客户端 布谷鸟过滤器的命令

创建布谷鸟过滤器

CF.RESERVE {key} {capacity} [BUCKETSIZE {bucketsize}] [MAXITERATIONS {maxiterations}]
[EXPANSION {expansion}]

命令用于创建布谷鸟过滤器，时间复杂度：O(1)，

其中参数介绍如下：

• key：布谷鸟过滤器的键。
• capacity：布谷鸟过滤器的容量。根据布谷鸟过滤器原理，写入时则可能未满，但由于互踢而被判定为满，需要扩容，故设置时，如果不考虑子过滤器扩容，则需要预设多于实际使用容量的 30%。
• bucketsize：存储桶中的元素数，相比于原始的布谷鸟算法，redisbloom 中引入了存储桶的改进方式，以降低互踢次数，提高内存使用效率，但同时也会导致误判提高和写入性能的下降的问题（由于桶的存在，互踢需要将数组桶的内容交换，故性能下降），默认值为 2。
• maxiterations：最大互踢次数。
• EXPANSION：当容量不足时，扩容的倍率（这里的扩容用词不准，实际上是建立了子过滤器进行实现，根据这个原理，需要注意的是当子过滤器过多时，会成倍数的影响性能），不填默认为 1。例如：1，则当容量 100 满时，自动扩容为 100 + 100。

布谷鸟过滤器中添加元素

CF.ADD {key} {item}

命令用于布谷鸟过滤器中添加元素。

时间复杂度：O(sub filter number + maxiterations)。

其中参数介绍如下：

• key：布谷鸟过滤器的键，当键不存在时创建一个容量为 1080 的默认过滤器。
• item：写入的元素。

布谷鸟过滤器中添加元素（不存在时则插入）

CF.ADDNX {key} {item}

命令用于布谷鸟过滤器中添加元素，当元素不存在时则插入，

之所以需要提供这样的命令，源于布谷鸟的占位踢出算法，如果连续的插入相同的元素，则会导致内存使用率降低，同时会导致删除后数据依然存在，故写入前应当判断元素是否存在。

时间复杂度：O(sub filter number + maxiterations)。

其中参数介绍如下：

• key：布谷鸟过滤器的键，当键不存在时创建一个容量为 1080 的默认过滤器。
• item：写入的元素。

CF.RESERVE 和 CF.ADD，CF.ADDNX 的复合体

创建的同时，添加元素

CF.INSERT {key} [CAPACITY {capacity}] [NOCREATE] ITEMS {item ...}
CF.INSERTNX {key} [CAPACITY {capacity}] [NOCREATE] ITEMS {item ...}

这两个命令为 CF.RESERVE 和 CF.ADD，CF.ADDNX 的复合体，这里不在重复介绍。

布谷鸟过滤器中判断元素是否存在

CF.EXISTS {key} {item}

命令用于布谷鸟过滤器中判断元素是否存在，时间复杂度：O(sub filter number)。

其中参数介绍如下：

• key：布谷鸟过滤器的键。
• item：要判断的元素。

布谷鸟过滤器中删除元素

CF.DEL {key} {item}

命令用于布谷鸟过滤器中删除元素，这里需要注意的是，如果同一个元素添加多次，则同样需要删除多次，时间复杂度：O(sub filter number)。

其中参数介绍如下：

• key：布谷鸟过滤器的键。
• item：移除的元素。

布谷鸟过滤器中查询元素存在的数量

CF.COUNT {key} {item}

命令用于布谷鸟过滤器中查询元素存在的数量，这里需要注意的是返回的不是一个准确值，时间复杂度：O(sub filter number)。

其中参数介绍如下：

• key：布谷鸟过滤器的键。
• item：查询数量元素。

将一个布谷鸟过滤器以分片的方式读出

CF.SCANDUMP {key} {iter}

命令用于将一个布谷鸟过滤器以分片的方式读出，返回两个子段分别为分片总数和分片字节，当返回分配总数为 0，且字节为空时代表读取结束，时间复杂度：O(n)，

其中参数介绍如下：

• key：布谷鸟的键。
• iter：返回的分片下标，首个下标从 0 开始。

将一个布谷鸟过滤器以分片的方式写入

CF.LOADCHUNK {key} {iter} {data}

命令用于将一个布谷鸟过滤器以分片的方式写入，存在则覆盖。时间复杂度：O(n)，其中参数介绍如下：

• key：布谷鸟过滤器的键。
• iter：返回的分片下标，首个下标从 0 开始。
• data：写入的字节。

查看布谷鸟过滤器详情

CF.INFO {key}

命令用于查看布谷鸟过滤器详情，时间复杂度：O(1)，

其中参数介绍如下：

• key：布谷鸟过滤器的键。

实战：CuckooFilter实现亿级海量数据查重/亿级海量数据黑名单

package com.crazymaker.cloud.redis.redission.demo.business;

import io.rebloom.client.Client;
import lombok.extern.slf4j.Slf4j;
import org.springframework.beans.factory.annotation.Autowired;
import org.springframework.stereotype.Service;
import redis.clients.jedis.Jedis;
import redis.clients.jedis.JedisPool;

import java.util.ArrayList;
import java.util.List;

/**
 * redis CuckooFilter 布谷鸟过滤器module 基于位图算法
 * 功能：亿级海量数据查重/或者亿级海量数据黑名单 
 * 优点：占用内存极少，并且插入和查询速度都足够快
 * 缺点：随着数据的增加，误判率会增加；还有无法判断数据一定存在；另外还有一个重要缺点，无法删除数据。
 */
@Slf4j
@Service
public class RedisModuleCuckooFilter {

    @Autowired
    private JedisPool jedisPool;


    /**
     * 手机号是否存在过滤器中
     *
     * @param filterName 过滤器名称
     * @param phone      手机号
     * @return true 表示存在
     */
    public boolean isExist(String filterName, String phone) {

        boolean booleans = false;
        try {
            //log.info("[名单过滤]数据：应用过滤器：{}，开始：{}", filterName, System.currentTimeMillis());
            booleans = getClient().cfExists(filterName, phone);
            //log.info("[名单过滤]数据：应用过滤器：{}，结束：{}", filterName, System.currentTimeMillis());

        } catch (Exception e) {
            e.printStackTrace();
        }
        return booleans;
    }

    /**
     * 数据添加到过滤器
     *
     * @param filterName 过滤器名称
     * @param phone      要添加的手机号
     * @return
     */
    public Boolean addFilter(String filterName, String phone) {
        Boolean booleans = false;
        try {
            log.info("[过滤器添加数据]数据：应用过滤器：{}，开始：{}", filterName, System.currentTimeMillis());
            booleans = this.getClient().cfAddNx(filterName, phone);
            log.info("[过滤器添加数据]数据：应用过滤器：{}，结束：{}", filterName, System.currentTimeMillis());
        } catch (Exception e) {
            e.printStackTrace();
        }
        return booleans;
    }

    /**
     * 数据添加到过滤器
     *
     * @param filterName 过滤器名称
     * @param phones     要添加的手机号
     * @return
     */
    public List<Boolean> addFilter(String filterName, String[] phones) {

        if (null == phones || phones.length > 0) {
            return new ArrayList<>();
        }
        List<Boolean> booleans = new ArrayList<>();
        try {
            log.info("[过滤器添加数据]数据：应用过滤器：{}，开始：{}", filterName, System.currentTimeMillis());
            booleans = this.getClient().cfInsertNx(filterName, phones);
            log.info("[过滤器添加数据]数据：应用过滤器：{}，结束：{}", filterName, System.currentTimeMillis());
        } catch (Exception e) {
            e.printStackTrace();
        }
        return booleans;
    }

    /**
     * 数据从过滤器删除
     *
     * @param filterName 过滤器名称
     * @param phone      要删除的手机号
     * @return
     */
    public boolean deleteFilter(String filterName, String phone) {

        if (null == phone) {
            return false;
        }

        boolean booleans = false;
        try {
            log.info("[过滤器删除数据]数据：应用过滤器：{}，开始：{}", filterName, System.currentTimeMillis());
            booleans = this.getClient().cfDel(filterName, phone);
            log.info("[过滤器删除数据]数据：应用过滤器：{}，结束：{}", filterName, System.currentTimeMillis());
        } catch (Exception e) {
            e.printStackTrace();
        }

        return booleans;
    }

    /**
     * 初始化过滤器
     */
    public void initFilter() {

        try {
            Client client = this.getClient();
            log.info("[初始化过滤器]数据：应用过滤器开始：{}", System.currentTimeMillis());
            //初始化过滤器 系统白名单
            client.createFilter("REDIS_BLOOM_FILTERS_SYSTEM_WHITE", 100000, 0.0001);
        } catch (Exception e) {
            e.printStackTrace();
        }

    }

    public Client getClient() {
        Client client = new Client(jedisPool);
        return client;
    }

    public Client getClient(JedisPool pool) {

        Client client = new Client(pool);
        return client;
    }
}

布谷鸟过滤器和布隆过滤器的对比

该模块主要用于判断某个元素是否存在，相比于布隆过滤器，布谷鸟过滤器支持数据删除，同时由于布谷鸟算法，其占用内存在理论情况下比布隆过滤器更小，查询复杂度约为 O(2)，

以下为 redis 中和 set 的测试内存结果对比： 测试元素 100w ，元素大小 32 个字节

# 布谷鸟过滤器
# Memory
used_memory:2114792
used_memory_human:2.02M

# set
# Memory
used_memory:73434368
used_memory_human:70.03M

根据以上结果，看上去似乎布谷鸟过滤器在查询和内存的使用效率上会高于布隆过滤器，但在实际情况中为了减少互踢问题，需要扩容，实际使用内存甚至会高于布隆过滤器，同样，由于互踢问题的存在，在实际的写入效率上也比布隆过滤器要差一些。

但在实际使用场景中，常常存在需要进行数据擦除的情况，相比于布隆过滤器，布谷鸟过滤器在不是极端的使用场景则更为灵活。

布谷鸟过滤器优点和缺点

优点

• 空间效率：相较于布隆过滤器，布谷鸟过滤器能够在相同的存储空间内存储更多的元素，且误判率较低。
• 快速查找：查找操作的时间复杂度为 O(1)，非常快速，适合高吞吐量的场景。
• 支持删除：与布隆过滤器不同，布谷鸟过滤器支持有效的删除操作，尽管相对复杂，但仍然比布隆过滤器更灵活。
• 误判率低：布谷鸟过滤器的误判率可以通过调整桶的大小和元素的指纹长度来控制，通常比布隆过滤器更低。
• 实现简单：数据结构相对简单，易于实现。

缺点

• 删除操作复杂：删除元素时，可能需要迁移指纹，这增加了操作的复杂性。
• 扩展性限制：当过滤器满时，可能需要重新分配并重建过滤器，这会影响性能。
• 存储占用：尽管比布隆过滤器更高效，但相较于传统哈希表，布谷鸟过滤器在存储指纹和桶的开销上仍然存在占用。
• 哈希函数依赖：过滤器的性能依赖于哈希函数的质量，若哈希函数不均匀，可能导致某些桶过载。
  不适用于小集合：对于小型集合，布谷鸟过滤器的优势不明显，可能不如其他简单的数据结构（如哈希表）更有效。

使用的过程中，还是并且要充分考虑布谷鸟过滤器存在误判率的特点，合理应用于合适的场景。

尼恩架构团队塔尖的redis 面试题

史上最全： Redis: 缓存击穿、缓存穿透、缓存雪崩 ，如何彻底解决？

史上最全：Redis脑裂 ，如何预防？

史上最全： Redis锁如何续期 ？Redis锁超时，任务没完怎么办？

史上最全：Redis分布式 锁失效了，怎么办？

史上最全：Redis分段锁，如何设计？

redis 锁的5个大坑，如何规避？

史上最全：Redis热点Key，如何 彻底解决问题

史上最全：为啥Redis用哈希槽，不用一致性哈希？

史上最全：如何保持 Redis 数据一致性？

说在最后：有问题找老架构取经‍

回到开始的时候的面试题：

亿级海量数据查重，如何实现 ？

亿级海量数据黑名单 ，如何存储？

50亿个电话号码，如何判断是否10万个电话号码是否存在？

安全连接网址，全球数10亿的网址判断？

按照此文的套路去回答， 把三个方案都讲一通：

• 使用 BitMap 位图进行二值统计
• 使用BloomFilter 进行二值统计
• 使用Cuckoo Filter 布谷鸟过滤器 进行二值统计

一定会 吊打面试官，让面试官爱到 “不能自已、口水直流”，然后实现”offer直提”。

在面试之前，建议大家系统化的刷一波 5000页《尼恩Java面试宝典PDF》，里边有大量的大厂真题、面试难题、架构难题。

很多小伙伴刷完后， 吊打面试官， 大厂横着走。

在刷题过程中，如果有啥问题，大家可以来 找 40岁老架构师尼恩交流。

另外，如果没有面试机会，可以找尼恩来改简历、做帮扶。前段时间，刚指导一个小伙 暴涨200%（涨2倍），29岁/7年/双非一本 ， 从13K一次涨到 37K ，逆天改命。

狠狠卷，实现 “offer自由” 很容易的， 前段时间一个武汉的跟着尼恩卷了2年的小伙伴， 在极度严寒/痛苦被裁的环境下， offer拿到手软， 实现真正的 “offer自由” 。

技术自由的实现路径：

实现你的 架构自由：

《吃透8图1模板，人人可以做架构》

《10Wqps评论中台，如何架构？B站是这么做的！！！》

《阿里二面：千万级、亿级数据，如何性能优化？ 教科书级 答案来了》

《峰值21WQps、亿级DAU，小游戏《羊了个羊》是怎么架构的？》

《100亿级订单怎么调度，来一个大厂的极品方案》

《2个大厂 100亿级 超大流量 红包 架构方案》

… 更多架构文章，正在添加中

实现你的 响应式 自由：

《响应式圣经：10W字，实现Spring响应式编程自由》

这是老版本 《Flux、Mono、Reactor 实战（史上最全）》

实现你的 spring cloud 自由：

《Spring cloud Alibaba 学习圣经》 PDF

《分库分表 Sharding-JDBC 底层原理、核心实战（史上最全）》

《一文搞定：SpringBoot、SLF4j、Log4j、Logback、Netty之间混乱关系（史上最全）》

实现你的 linux 自由：

《Linux命令大全：2W多字，一次实现Linux自由》

实现你的 网络 自由：

《TCP协议详解 (史上最全)》

《网络三张表：ARP表, MAC表, 路由表，实现你的网络自由！！》

实现你的 分布式锁 自由：

《Redis分布式锁（图解 - 秒懂 - 史上最全）》

《Zookeeper 分布式锁 - 图解 - 秒懂》

实现你的 王者组件 自由：

《队列之王： Disruptor 原理、架构、源码 一文穿透》

《缓存之王：Caffeine 源码、架构、原理（史上最全，10W字 超级长文）》

《缓存之王：Caffeine 的使用（史上最全）》

《Java Agent 探针、字节码增强 ByteBuddy（史上最全）》

实现你的 面试题 自由：

4800页《尼恩Java面试宝典 》 40个专题

免费获取11个技术圣经PDF：

标签：查重,布谷鸟,元素,redis,布隆,过滤器,哈希,亿级
From： https://www.cnblogs.com/crazymakercircle/p/18536727