我的编程空间,编程开发者的网络收藏夹
学习永远不晚

什么是布隆过滤器

短信预约 -IT技能 免费直播动态提醒
省份

北京

  • 北京
  • 上海
  • 天津
  • 重庆
  • 河北
  • 山东
  • 辽宁
  • 黑龙江
  • 吉林
  • 甘肃
  • 青海
  • 河南
  • 江苏
  • 湖北
  • 湖南
  • 江西
  • 浙江
  • 广东
  • 云南
  • 福建
  • 海南
  • 山西
  • 四川
  • 陕西
  • 贵州
  • 安徽
  • 广西
  • 内蒙
  • 西藏
  • 新疆
  • 宁夏
  • 兵团
手机号立即预约

请填写图片验证码后获取短信验证码

看不清楚,换张图片

免费获取短信验证码

什么是布隆过滤器

本篇内容介绍了“什么是布隆过滤器”的有关知识,在实际案例的操作过程中,不少人都会遇到这样的困境,接下来就让小编带领大家学习一下如何处理这些情况吧!希望大家仔细阅读,能够学有所成!

在正式讲解布隆过滤器之前,先让我们看看这个业务场景:

Redis 是软件架构中常用的组件,最常见的用法是将热点数据缓存到 Redis 中,以减少数据库的压力;查询过程中最常见的用法是:查询  Redis,如果能查询到则直接返回,如果 Redis 中不存在则继续查询数据库。

这种方式可以减少数据库的访问次数,但是“当缓存中没有,就查询数据库”,在高并发的环境中依然会有风险,比如 90%  的请求数据都不在缓存中,那么这些请求就都会落到数据库上,这就是缓存穿透。

那么有没有什么办法解决这个问题呢?这就可以使用【布隆过滤器】了,它可以确定“某项数据肯定不存在”。

01.布隆过滤器的概念

布隆过滤器是一个叫“布隆”的人提出的,它本身是一个很长的二进制向量(想象成数组)和一系列随机映射函数(想象成多个 Hash  函数),二进制向量中存放的不是0,就是1(在学习布隆过滤器之前,可以先了解 BitMap 算法,便于理解)。

比如要根据客户手机号做为条件查询客户信息,通常会把手机号码设置成缓存中的 Key,让我们设置一个长度为 16 的布隆过滤器。

布隆过滤器初始化都是 0;

对 13800000000 分别进行 hash2()、hash3()、hash4() 运算,得到三个结果 5、9、12,把对应位置设置成 1;

什么是布隆过滤器

对 18900000000 分别进行 hash2()、hash3()、hash4() 运算,得到三个结果 2、8、12,把对应位置设置成 1,现在  2、5、8、9、12 都是 1,其余元素都是 0;

什么是布隆过滤器

如果我们想要验证某个电话号码是否存在,需要怎么做呢?

对 13700000000 分别进行 hash2()、hash3()、hash4() 运算,得到三个结果 1、9、13,然后去判断第 1、9、13  位上的值是 0 还是 1,如果不全是 1 的话,就说明 13700000000 不在这个布隆过滤器上;这就确定了“某项数据肯定不存在”。

什么是布隆过滤器

当然我们也可以看出来布隆过滤器有个问题,那就是不能保证数据肯定存在,比如对 18000000000 分别进行  hash2()、hash3()、hash4() 运算,得到的结果是 5、8、9,恰好这三位都是  1,但实际上这条数据并不存在,所以布隆过滤器有一定的误判率;

而且因为多个数据经过运算后可能会映射到同一个位置(138 和 189 的运算结果都有  12),所以布隆过滤器很难做到删除,除非要为每一位增加一个计数器,删除的时候需要给计数器减 1,直到计数器为 0 时,才将布隆过滤器对应位置修改成 0。

02.特点总结

可以确定一个元素肯定不存在,但是不能确定一个元素肯定存在;

二进制向量越长,映射函数越多,误判率越低;如果提前可以确定误判率,也可以反推出来布隆过滤器的长度;

可以添加元素,但是不能删除元素(除非增加计数器);

在存储空间和插入查询的时间复杂度都有巨大优势。

回到本文开头的那个业务场景,为了防止缓存穿透,可以使用布隆过滤器过滤掉肯定不存在的数据,误判的请求虽然还是会放到到数据库,但已经极大地减少了穿透的数量。

03.手写一个布隆过滤器

Code 不是目的,Coding 的过程是为了加深理解。

首先我们需要定义一个 bitmap,在 JDK 中,已经有对应实现的数据结构类 java.util.BitSet:

//设置一个布隆过滤器 private int DEFAULT_SIZE = 1 << 30;  private BitSet bitset ;

我们还需要一组映射函数,这里可以使用加法 hash 函数,设置 6 个质数,对应 6 个不同的 hash 函数:

//定义一个质数数组,长度为6,可以生成6个hash函数,用于随机映射 private int[] seeds = {3, 7, 13, 31, 37, 61};  private HashFunction[] functions = new HashFunction[seeds.length];

在构造函数中进行初始化,设置 BitSet 的长度,生成映射函数:

 public BloomFilter() {   bitset = new BitSet(DEFAULT_SIZE);    for (int i = 0; i < seeds.length; i++) {       functions[i] = new HashFunction(DEFAULT_SIZE, seeds[i]);   } }

增加元素的时候,对入参进行 6 次 hash 运算,并将结果对应的位置修改成 1(BitSet 对应的位置修改成 true):

 public void add(String value) {   if (value != null) {       for (HashFunction f : functions) {     bitset.set(f.hash(value), true);       }   } }

判断元素是否在布隆管理器中,需要对入参进行 6 次 hash 运算,再查看结果对应的位置上是 0 还是 1(true or false),如果其中一位是  0,表示数据肯定不存在,如果都是 1,表示数据(大概率)可能存在。

 public boolean contains(String value) {   if (value == null) {       return false;   }    for (HashFunction f : functions) {     if(!bitset.get(f.hash(value))){       //一个位置上不为1(true),就证明不存在,直接返回false       return false;     }   }    return true; }

04.Guava 中的 BloomFilter

已经有很多开源框架帮我们实现了布隆管理器,比如 Google 出品的 Guava 工具库,其中就有开箱即用的布隆过滤器;

public class BloomFilterTest {   public static void main(String[] args){     int size = 1000000;     //布隆过滤器     BloomFilter<Integer> bloomFilter = BloomFilter.create(Funnels.integerFunnel(), size, 0.001);          for (int i = 0; i < size; i++) {             bloomFilter.put(i);         }          List<Integer> list = new ArrayList<Integer>(1000);         for (int i = size + 1; i < size + 10000; i++) {             if (bloomFilter.mightContain(i)) {                 list.add(i);             }         }         System.out.println("误判数量:" + list.size());   } }

“什么是布隆过滤器”的内容就介绍到这里了,感谢大家的阅读。如果想了解更多行业相关的知识可以关注编程网网站,小编将为大家输出更多高质量的实用文章!

免责声明:

① 本站未注明“稿件来源”的信息均来自网络整理。其文字、图片和音视频稿件的所属权归原作者所有。本站收集整理出于非商业性的教育和科研之目的,并不意味着本站赞同其观点或证实其内容的真实性。仅作为临时的测试数据,供内部测试之用。本站并未授权任何人以任何方式主动获取本站任何信息。

② 本站未注明“稿件来源”的临时测试数据将在测试完成后最终做删除处理。有问题或投稿请发送至: 邮箱/279061341@qq.com QQ/279061341

什么是布隆过滤器

下载Word文档到电脑,方便收藏和打印~

下载Word文档

猜你喜欢

什么是布隆过滤器?如何实现布隆过滤器?

以下我们介绍了什么是布隆过滤器?它的使用场景和执行流程,以及在 Redis 中它的使用,那么问题来了,在日常开发中,也就是在 Java 开发中,我们又将如何操作布隆过滤器呢?

什么是布隆过滤器?

布隆过滤器是一种基于哈希函数的概率性数据结构,用于判断元素是否属于给定集合。其原理是将元素映射到位数组中,并通过查询这些位置来判断元素是否可能存在于集合中。布隆过滤器以其空间效率和快速查询著称,广泛应用于网络安全、缓存系统和数据库等领域。其缺点是可能出现假阳性,但可以通过调整其参数来控制假阳性率。扩展版本的布隆过滤器,如可计数布隆过滤器和局部敏感哈希布隆过滤器,可用于解决特定问题,如近似最近邻搜索和动态集合维护。
什么是布隆过滤器?
2024-04-02

redis布隆过滤器的作用是什么

Redis布隆过滤器是一种数据结构,用于快速判断一个元素是否存在于一个集合中。它可以高效地判断一个元素是否可能在集合中,但无法确保元素一定在集合中或者排除元素已经在集合中。布隆过滤器通常用于减少对数据库的查询次数,节省资源和时间。常见的应用
redis布隆过滤器的作用是什么
2024-04-09

什么是布隆过滤器?你学会了吗?

在对响应时间要求比较严格的情况下,如果我们有里面,那么随着集合中元素数量的增加,我们需要的存储空间越来越大,检索时间也越来越长,导致内存过多开销和时间效率变低。

redis布隆过滤器的工作原理是什么

Redis布隆过滤器是一种数据结构,用于快速判断一个元素是否存在于一个集合中。它基于位数组和多个哈希函数实现。工作原理如下:初始化:布隆过滤器包含一个位数组,所有位都初始化为0。同时,需要选择合适数量的哈希函数和哈希函数的种子。添加元素
redis布隆过滤器的工作原理是什么
2024-04-09

如何在 Java 中实现布隆过滤器?(java怎么实现布隆过滤器)

在Java开发中,布隆过滤器是一种用于快速判断元素是否存在的数据结构。它具有高效的空间和时间复杂度,特别适用于大规模数据的去重和判断。下面将详细介绍如何在Java中实现布隆过滤器。一、了解布隆过滤器的原理布隆过滤器的核心
如何在 Java 中实现布隆过滤器?(java怎么实现布隆过滤器)
Java2024-12-22

牛哄哄的布隆过滤器,有什么用?

日常开发中,大家经常使用缓存,但是你知道大型的互联网公司面对高并发流量,要注意缓存穿透问题吗?

Python实现布隆过滤器

转载自:http://blog.csdn.net/demon24/article/details/8537665http://blog.csdn.net/u013402746/article/details/28414901        
2023-01-31

Java布隆过滤器怎么使用

本文小编为大家详细介绍“Java布隆过滤器怎么使用”,内容详细,步骤清晰,细节处理妥当,希望这篇“Java布隆过滤器怎么使用”文章能帮助大家解决疑惑,下面跟着小编的思路慢慢深入,一起来学习新知识吧。通常你判断某个元素是否存在用的是什么?很多
2023-06-29

Java怎么实现布隆过滤器

这篇“Java怎么实现布隆过滤器”文章的知识点大部分人都不太理解,所以小编给大家总结了以下内容,内容详细,步骤清晰,具有一定的借鉴价值,希望大家阅读完这篇文章能有所收获,下面我们一起来看看这篇“Java怎么实现布隆过滤器”文章吧。什么是布隆
2023-07-05

Redis布隆过滤器大小的算法公式是什么

今天小编给大家分享一下Redis布隆过滤器大小的算法公式是什么的相关知识点,内容详细,逻辑清晰,相信大部分人都还太了解这方面的知识,所以分享这篇文章给大家参考一下,希望大家阅读完这篇文章后有所收获,下面我们一起来了解一下吧。1. 简介客户端
2023-06-29

redis的set get[布隆过滤器]

布隆过滤器是什么 在做JAVA项目时候用到这个(参考地址),今天咱们就讲一讲 名字就跟每个定律一样,你问为什么叫牛顿定律,因为是牛顿发明或者发现的。 他能做什么?它是将一个二进制向量和函数映射,布隆过滤器可以用在检测元素是否存在某个集合或者用于快速检索中。 缺
redis的set get[布隆过滤器]
2018-08-21

图解布隆过滤器和布谷鸟过滤器实现原理

我们元数据通过两个哈希函数函数之后得到2和7两个值,然后将2和7这个两个值对应的bit位上的值设置为1,这样我们就将元数据存放到布隆过滤器上。

编程热搜

目录