1.定义布隆过滤器Bloom Filter是由空间高效的概率性数据结构用于判断一个元素一定不存在 / 可能存在常用来解决海量数据去重缓存穿透判断请求的数据是否有效避免直接绕过缓存请求数据库等2.组成1.位数组BitSet/Bit Array位数组中的元素都只占用1 bit并且每个元素只能是0或者1。内存占用极小。2.若干个相互独立的哈希函数k 个不同 seed种子的哈希函数同一个元素会被计算出 k 个不同下标。3.添加元素流程1.传入待存入元素2.使用布隆过滤器中的哈希函数对元素值进行计算得到哈希值有几个哈希函数得到几个哈希值3.哈希值在位运算中对应的下标值为14.查询元素流程1.传入带查询元素2.使用k个哈希函数计算出k个下标;3.判断1.只要任意一个bit位0→元素一定不存在2.所有k个bit位1→元素可能存在5.核心特点1存在误判现象元素实际不存在但是查询返回可能存在原因其他元素的哈希下表恰好把当前元素需要的所有bit位置1总结不会漏判只会误判。说不存在一定不存在说存在不一定真存在。2不支持删除元素一个 bit 位会被多个元素共用。 如果直接把某个 bit 置 0可能同时影响其他存在的元素无法安全删除单个元素。拓展改进计数布隆过滤器Counting Bloom Filter把 bit 改为计数器支持删除但内存开销上升。6.优点内存占用极低添加、查询操作时间复杂度O(k)k 为哈希函数数量性能极高可以分布式改造Redis BitMap 实现分布式布隆过滤器。7.缺点存在误判原生不支持删除元素数量越多误判概率持续上升。8.业务场景解决 Redis 缓存穿透过滤不存在的请求避免大量无效查询打到数据库海量数据去重比如黑名单、垃圾号码过滤爬虫 URL 去重避免重复抓取链接。9.案例分析短信黑名单1000 万手机号过滤方案选型对比数据库查询每次发短信查 MySQL 黑名单表。 缺点并发量大时 DB 压力极高数据库 IO 瓶颈性能差。HashMap/HashSet 全量加载到内存将 1000w 手机号全部加载进 JVM 内存。 缺点字符串占用内存巨大1000w 手机号内存开销很高重启需要重新加载占用大量堆内存。布隆过滤器最优方案实现步骤1.构造测试数据源调用mockPhoneNumber(1000000)生成 100 万条手机号集合内部设置两条固定手机号周期性插入保证存在重复数据其余号码随机生成。// 1. 模拟100w个手机号码包含重复的手机号码 ListString dataList mockPhoneNumber(1000000); private static ListString mockPhoneNumber(int count) { ListString list new ArrayList(count); String phone1 11111721234; String phone2 11111721235; for (int i 0; i count; i) { if (i % 1000 0) { list.add(phone1); } else if (i % 1500 0) { list.add(phone2); } else { // 随机生成手机号 String phone 1 (30 (int) (Math.random() * 9)) String.format(%08d, (int) (Math.random() * 100000000)); list.add(phone); } } return list; }2.定义容器创建resultList用来存放识别出来的重复手机号实例化MyBloomFilter布隆过滤器用于记录已经遍历过的手机号。// 2. 保存重复的手机号码 ListString resultList new ArrayList();3.遍历数据流进行查重循环遍历每一条手机号使用bloomFilter.contains(phoneNumber)判断号码是否在过滤器中若返回 true认为该号码之前出现过属于重复号码添加到resultList若返回 false代表第一次出现调用add()将手机号存入布隆过滤器。// 3. 创建布隆过滤器对象 MyBloomFilter bloomFilter new MyBloomFilter();4.输出结果遍历resultList打印所有识别到的重复手机号。核心逻辑原理利用布隆过滤器快速判断元素是否曾经存在数据流顺序读取首次出现的数据存入过滤器再次出现时被检测出来标记为重复。for (String phoneNumber : dataList) { if (bloomFilter.contains(phoneNumber)) { // 存在判定重复 resultList.add(phoneNumber); } else { // 第一次出现添加到过滤器 bloomFilter.add(phoneNumber); } }
1.定义布隆过滤器Bloom Filter是由空间高效的概率性数据结构用于判断一个元素一定不存在 / 可能存在常用来解决海量数据去重缓存穿透判断请求的数据是否有效避免直接绕过缓存请求数据库等2.组成1.位数组BitSet/Bit Array位数组中的元素都只占用1 bit并且每个元素只能是0或者1。内存占用极小。2.若干个相互独立的哈希函数k 个不同 seed种子的哈希函数同一个元素会被计算出 k 个不同下标。3.添加元素流程1.传入待存入元素2.使用布隆过滤器中的哈希函数对元素值进行计算得到哈希值有几个哈希函数得到几个哈希值3.哈希值在位运算中对应的下标值为14.查询元素流程1.传入带查询元素2.使用k个哈希函数计算出k个下标;3.判断1.只要任意一个bit位0→元素一定不存在2.所有k个bit位1→元素可能存在5.核心特点1存在误判现象元素实际不存在但是查询返回可能存在原因其他元素的哈希下表恰好把当前元素需要的所有bit位置1总结不会漏判只会误判。说不存在一定不存在说存在不一定真存在。2不支持删除元素一个 bit 位会被多个元素共用。 如果直接把某个 bit 置 0可能同时影响其他存在的元素无法安全删除单个元素。拓展改进计数布隆过滤器Counting Bloom Filter把 bit 改为计数器支持删除但内存开销上升。6.优点内存占用极低添加、查询操作时间复杂度O(k)k 为哈希函数数量性能极高可以分布式改造Redis BitMap 实现分布式布隆过滤器。7.缺点存在误判原生不支持删除元素数量越多误判概率持续上升。8.业务场景解决 Redis 缓存穿透过滤不存在的请求避免大量无效查询打到数据库海量数据去重比如黑名单、垃圾号码过滤爬虫 URL 去重避免重复抓取链接。9.案例分析短信黑名单1000 万手机号过滤方案选型对比数据库查询每次发短信查 MySQL 黑名单表。 缺点并发量大时 DB 压力极高数据库 IO 瓶颈性能差。HashMap/HashSet 全量加载到内存将 1000w 手机号全部加载进 JVM 内存。 缺点字符串占用内存巨大1000w 手机号内存开销很高重启需要重新加载占用大量堆内存。布隆过滤器最优方案实现步骤1.构造测试数据源调用mockPhoneNumber(1000000)生成 100 万条手机号集合内部设置两条固定手机号周期性插入保证存在重复数据其余号码随机生成。// 1. 模拟100w个手机号码包含重复的手机号码 ListString dataList mockPhoneNumber(1000000); private static ListString mockPhoneNumber(int count) { ListString list new ArrayList(count); String phone1 11111721234; String phone2 11111721235; for (int i 0; i count; i) { if (i % 1000 0) { list.add(phone1); } else if (i % 1500 0) { list.add(phone2); } else { // 随机生成手机号 String phone 1 (30 (int) (Math.random() * 9)) String.format(%08d, (int) (Math.random() * 100000000)); list.add(phone); } } return list; }2.定义容器创建resultList用来存放识别出来的重复手机号实例化MyBloomFilter布隆过滤器用于记录已经遍历过的手机号。// 2. 保存重复的手机号码 ListString resultList new ArrayList();3.遍历数据流进行查重循环遍历每一条手机号使用bloomFilter.contains(phoneNumber)判断号码是否在过滤器中若返回 true认为该号码之前出现过属于重复号码添加到resultList若返回 false代表第一次出现调用add()将手机号存入布隆过滤器。// 3. 创建布隆过滤器对象 MyBloomFilter bloomFilter new MyBloomFilter();4.输出结果遍历resultList打印所有识别到的重复手机号。核心逻辑原理利用布隆过滤器快速判断元素是否曾经存在数据流顺序读取首次出现的数据存入过滤器再次出现时被检测出来标记为重复。for (String phoneNumber : dataList) { if (bloomFilter.contains(phoneNumber)) { // 存在判定重复 resultList.add(phoneNumber); } else { // 第一次出现添加到过滤器 bloomFilter.add(phoneNumber); } }
