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

Java的布隆过滤器你了解吗

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

北京

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

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

看不清楚,换张图片

免费获取短信验证码

Java的布隆过滤器你了解吗

BitMap

现代计算机用二进制(bit,位)作为信息的基础单位,1 个字节等于 8 位,例如big字符串是由 3 个字节组成,但实际在计算机存储时将其用二进制表示,big分别对应的 ASCII 码分别是 98、105、103,对应的二进制分别是 01100010、01101001 和 01100111。

许多开发语言都提供了操作位的功能,合理地使用位能够有效地提高内存使用率和开发效率。

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 分别存储活跃用户:

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

2.如果按位存储,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 = 265%32=1,即 65 在int[2] 中的第 1 位。

布隆过滤器

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

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

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

在很多 Key-Value 系统中也使用了布隆过滤器来加快查询过程,如 Hbase,Accumulo,Leveldb,一般而言,Value 保存在磁盘中,访问磁盘需要花费大量时间,然而使用布隆过滤器可以快速判断某个 Key 对应的 Value 是否存在,因此可以避免很多不必要的磁盘 IO 操作。

通过一个 Hash 函数将一个元素映射成一个位阵列(Bit Array)中的一个点。这样一来,我们只要看看这个点是不是 1 就知道可以集合中有没有它了。这就是布隆过滤器的基本思想。

运用场景

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

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

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

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

5、快速定位用户属性(黑名单、白名单等)?

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

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

8、缓存穿透。

传统数据结构的不足

一般来说,将网页 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%,1000 万个 Integer,需要 161M 左右空间,占比 13.3%。

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

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

实现原理

假设我们有个集合 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) = 3Hash1(URL2) = 6Hash1(URL3) = 6,如下:

image-20220311142934256

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

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

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

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 位为下:

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

image-20220311155646991

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

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

布隆过滤器可精确的代表一个集合,可精确判断某一元素是否在此集合中,精确程度由用户的具体设计决定,达到 100% 的正确是不可能的。但是布隆过滤器的优势在于,利用很少的空间可以达到较高的精确率

实现

Redis 的 bitmap

基于redis 的 bitmap数据结构的相关指令来执行。

RedisBloom

布隆过滤器可以使用 Redis 中的位图(bitmap)操作实现,直到 Redis4.0 版本提供了插件功能,Redis 官方提供的布隆过滤器才正式登场,布隆过滤器作为一个插件加载到 Redis Server 中,官网推荐了一个 RedisBloom 作为 Redis 布隆过滤器的 Module。

详细安装、指令操作参考:https://github.com/RedisBloom/RedisBloom

文档地址:https://oss.redislabs.com/redisbloom/

Guava 的 BloomFilter

Guava 项目发布版本11.0时,新添加的功能之一是BloomFilter类。

Redisson

Redisson 底层基于位图实现了一个布隆过滤器。

public static void main(String[] args) {
    Config config = new Config();
    // 单机环境
    config.useSingleServer().setAddress("redis://192.168.153.128:6379");
    //构造Redisson
    RedissonClient redisson = Redisson.create(config);
    RBloomFilter<String> bloomFilter = redisson.getBloomFilter("nameList");
    //初始化布隆过滤器:预计元素为100000000L,误差率为3%,根据这两个参数会计算出底层的 bit 数组大小
    bloomFilter.tryInit(100000L, 0.03);
    //将 10086 插入到布隆过滤器中
    bloomFilter.add("10086");
    //判断下面号码是否在布隆过滤器中
    System.out.println(bloomFilter.contains("10086"));//true
    System.out.println(bloomFilter.contains("10010"));//false
    System.out.println(bloomFilter.contains("10000"));//false
}

解决缓存穿透

缓存穿透是指查询一个根本不存在的数据,缓存层和存储层都不会命中,如果从存储层查不到数据则不写入缓存层。

缓存穿透将导致不存在的数据每次请求都要到存储层去查询,失去了缓存保护后端存储的意义。缓存穿透问题可能会使后端存储负载加大,由于很多后端存储不具备高并发性,甚至可能造成后端存储宕掉。

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

例如:一个推荐系统有 4 亿个用户 id,每个小时算法工程师会根据每个用户之前历史行为计算出推荐数据放到存储层中,但是最新的用户由于没有历史行为,就会发生缓存穿透的行为,为此可以将所有推荐数据的用户做成布隆过滤器。如果布隆过滤器认为该用户 id 不存在,那么就不会访问存储层,在一定程度保护了存储层。

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

总结

本篇文章就到这里了,希望能够给你带来帮助,也希望您能够多多关注编程网的更多内容!    

免责声明:

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

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

Java的布隆过滤器你了解吗

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

下载Word文档

猜你喜欢

Java中的布隆过滤器你真的懂了吗

经常会听到大家说起布隆过滤器,但是很多人都只是听过名字,却并不知道其是怎么实现的。下面将详细介绍一下布隆过滤器,并且使用简单的代码演示
2023-05-18

布隆过滤器,你用对了吗?

布隆过滤器是一种简单但非常有效的数据结构,特别适用于大规模数据的快速查找和去重等场景。

你了解布隆过滤器的“大家族”吗?

布隆过滤器(Bloom Filter)是1970年由伯顿·霍华德·布隆(Burton Howard Bloom)提出的。它实际上是一个很长的二进制向量和一系列随机映射函数。

Java中的布隆过滤器,你知道吗?

布隆过滤器可以用于检索一个元素是否在一个集合中。它的优点是空间效率和查询时间都远远超过一般的算法,缺点是有一定的误识别率和删除困难。

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

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

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

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

Java的布隆过滤器如何实现

今天小编给大家分享一下Java的布隆过滤器如何实现的相关知识点,内容详细,逻辑清晰,相信大部分人都还太了解这方面的知识,所以分享这篇文章给大家参考一下,希望大家阅读完这篇文章后有所收获,下面我们一起来了解一下吧。BitMap现代计算机用二进
2023-06-29

Java布隆过滤器怎么使用

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

Java怎么实现布隆过滤器

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

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

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

redis的set get[布隆过滤器]

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

Java布隆过滤器的原理和实现分析

数组、链表、树等数据结构会存储元素的内容,一旦数据量过大,消耗的内存也会呈现线性增长所以布隆过滤器是为了解决数据量大的一种数据结构。本文就来和大家详细说说布隆过滤器的原理和实现,感兴趣的可以了解一下
2022-11-13

编程热搜

  • Python 学习之路 - Python
    一、安装Python34Windows在Python官网(https://www.python.org/downloads/)下载安装包并安装。Python的默认安装路径是:C:\Python34配置环境变量:【右键计算机】--》【属性】-
    Python 学习之路 - Python
  • chatgpt的中文全称是什么
    chatgpt的中文全称是生成型预训练变换模型。ChatGPT是什么ChatGPT是美国人工智能研究实验室OpenAI开发的一种全新聊天机器人模型,它能够通过学习和理解人类的语言来进行对话,还能根据聊天的上下文进行互动,并协助人类完成一系列
    chatgpt的中文全称是什么
  • C/C++中extern函数使用详解
  • C/C++可变参数的使用
    可变参数的使用方法远远不止以下几种,不过在C,C++中使用可变参数时要小心,在使用printf()等函数时传入的参数个数一定不能比前面的格式化字符串中的’%’符号个数少,否则会产生访问越界,运气不好的话还会导致程序崩溃
    C/C++可变参数的使用
  • css样式文件该放在哪里
  • php中数组下标必须是连续的吗
  • Python 3 教程
    Python 3 教程 Python 的 3.0 版本,常被称为 Python 3000,或简称 Py3k。相对于 Python 的早期版本,这是一个较大的升级。为了不带入过多的累赘,Python 3.0 在设计的时候没有考虑向下兼容。 Python
    Python 3 教程
  • Python pip包管理
    一、前言    在Python中, 安装第三方模块是通过 setuptools 这个工具完成的。 Python有两个封装了 setuptools的包管理工具: easy_install  和  pip , 目前官方推荐使用 pip。    
    Python pip包管理
  • ubuntu如何重新编译内核
  • 改善Java代码之慎用java动态编译

目录