当前位置：首页 > news >正文

[Collection与数据结构] 位图与布隆过滤器

news 2025/7/12 11:15:38

🌸个人主页:https://blog.csdn.net/2301_80050796?spm=1000.2115.3001.5343
🏵️热门专栏:
🧊 Java基本语法(97平均质量分)https://blog.csdn.net/2301_80050796/category_12615970.html?spm=1001.2014.3001.5482
🍕 Collection与数据结构 (93平均质量分)https://blog.csdn.net/2301_80050796/category_12621348.html?spm=1001.2014.3001.5482
🧀线程与网络(96平均质量分) https://blog.csdn.net/2301_80050796/category_12643370.html?spm=1001.2014.3001.5482
🍭MySql数据库(93平均质量分)https://blog.csdn.net/2301_80050796/category_12629890.html?spm=1001.2014.3001.5482
🍬算法(97平均质量分)https://blog.csdn.net/2301_80050796/category_12676091.html?spm=1001.2014.3001.5482
🍃 Spring(97平均质量分)https://blog.csdn.net/2301_80050796/category_12724152.html?spm=1001.2014.3001.5482
🎃Redis(97平均质量分)https://blog.csdn.net/2301_80050796/category_12777129.html?spm=1001.2014.3001.5482
🐰RabbitMQ(97平均质量分) https://blog.csdn.net/2301_80050796/category_12792900.html?spm=1001.2014.3001.5482
感谢点赞与关注~~~

1. 常见位运算总结
2. 位图
- 2.1 位图的概念
- 2.2 位图的实现
- 2.3 位图的应用
- 2.4 对应java中的类
3. 布隆过滤器
- 3.1 布隆过滤器的提出
- 3.2 布隆过滤器的概念
- 3.3 布隆过滤器的插入
- 3.4 布隆过滤器的查找
- 3.5 布隆过滤器的模拟实现
- 3.6 布隆过滤器的缺陷
- 3.7 布隆过滤器的优点
- 3.8 布隆过滤器的常见使用场景
4. 海量数据处理
- 4.1 哈希切割
- 4.2 位图应用
- 4.3 布隆过滤器的应用

1. 常见位运算总结

基础位运算
<<: 二进制左移.
>>:二进制右移.
~:二进制取反.
&: 有0就是0,全1才是1.
|: 有1就是1,全0才是0.
^: 相同为0,相异位1.其实也可以看做是一种无进位相加.
给定一个数n,确定他的二进制表示的第x位是0还是1
可以把这个数字n进行左移x位,之后&上一个二进制1,如果结果是1,说明该位是1,如果结果是0,说明该位是0.
将一个数n的二进制表示的第x位修改为1.
可以把二进制1左移x位,之后n|=左移x位之后的这个数字.
将一个数n的二进制表示的第x位修改成0.
首先把一个二进制1取反,之后再左移x位,之后n&=左移x位之后的这个数字.
提取一个数n二进制表示中最右侧的1.
n&(~n+1)
干掉一个数n二进制表示中最右侧的1.
n&(n-1)
异或^运算的运算律
消消乐运算律
- a^0 = a
- a^a = 0
- a ^ b ^ c = a ^ (b ^ c)

2. 位图

2.1 位图的概念

所谓位图,就是用每一个bit位来存放某种状态,1表示一种状态,0表示另一种状态.适用于海量数据,整数,数据无重复的场景.通常用来判断某个数据是否存在.
位图之所以可以存储海量的数据,是由于位图对空间的利用率非常高.下面我们来举个例子:
给定40亿个不重复的无符号整数,没有经过排序,给一个无符号整数,如何快速判断这个数是否在这40亿个数据中存在.
我们如果使用遍历数据的方法的话,存在两个问题,第一个问题就是内存空间有限,我们不可能把数据全部都从硬盘中读取到内存中来寻找,其次就是查找效率太低,时间复杂度为O(N).如果我们进行排序之后利用二分查找算法来查找,只能一定程度上解决时间效率上的问题,不可解决空间效率上的问题.
所以我们可以使用位图来解决:
数据是否给定的整形数据中,结果是在或者是不在,刚好是两种状态,那么可以使用一个二进制位来表示数据是否存在的信息,如果二进制比特位为1,代表的是存在,为0则代表的是不存在.
在这里插入图片描述

2.2 位图的实现

首先位图需要有存储数据的空间,我们使用byte[]数组来存储数据.
其次需要有空间使用大小.
使用构造方法初始化byte[]数组的空间.默认是1字节,如果指定了空间大小,那么就是n/8+1字节.比如n=12,除8之后就是1余4,也就是我们需要存储在第二个字节的第4个比特位,此时我们就需要2个byte.如果正好是在第8个bit位的时候,可能会多出来一个字节,但是也没有关系.
插入数据,首先/8计算在那个字节,之后判断有没有越界的情况,如果越界,使用copyof方法进行扩容,之后%8,计算在那个bit位存储这个数据,之后使用我们上面提到的常用的位运算来把指定的bit为改为1.
查找数据,首先还是把数据/8之后%8,之后还是使用我们上面的常用位运算验证对应的bit位是否是1.
删除某个数据,还是先把数据/8之后%8,之后还是使用我们上面的常用位运算把对应的bit为改为0.

代码实现:

import java.util.Arrays;public class MyBitSet {private byte[] elem;public int usedSize;public MyBitSet(){this.elem = new byte[1];}public MyBitSet(int size){this.elem = new byte[size/8+1];}/*** 添加指定元素* @param val 指定元素* @return 返回是否添加成功*/public boolean add(int val){if (val < 0){//不支持负数throw new RuntimeException("val not support lower than 0");}int byteSet = val / 8;int bitSet  = val % 8;if (byteSet > elem.length-1){//容量不够,扩容elem = Arrays.copyOf(elem,elem.length*2);}elem[byteSet] |= (byte) (1 << bitSet);usedSize++;return true;}/*** 是否包含指定元素* @param val 指定元素* @return 返回是否存在*/public boolean contains(int val){if (val < 0){throw new RuntimeException("val not support lower than 0");}int byteSet = val / 8;int bitSet  = val % 8;if ((elem[byteSet] & (byte) (1 << bitSet)) != 0){return true;}return false;}/*** 删除指定元素* @param val 指定元素*/public void del(int val){if (val < 0){throw new RuntimeException("val not support lower than 0");}int byteSet = val / 8;int bitSet  = val % 8;elem[byteSet] &= (byte) ~(1 << bitSet);usedSize--;}
}

2.3 位图的应用

去重+排序
位图这种数据结构本身就是一个萝卜一个坑,一个数据在位图中只能存在一次,其次,位图本身就是从小到大存储数据,只要把位图中的元素遍历一遍,就可以从小到大输出数据.下面是遍历位图的实现:

/*** 输出位图中的数据*/
public void display(){for (int i = 0;i < elem.length;i++){for (int j = 0;j < 8;j++){if ((elem[i] & (1<<j)) != 0){System.out.print(i*8+j+" ");}}}
}

求两个交集的交集,并集.
把两个位图进行&运算,就可以求出交集,把连个位图进行|就可以求出并集.

对位图进行测试进行测试:

public class Main {public static void main(String[] args) {MyBitSet bitSet = new MyBitSet();bitSet.add(3);bitSet.add(7);bitSet.add(10);bitSet.add(9);bitSet.add(5);System.out.println(bitSet.contains(5));bitSet.del(10);bitSet.display();}
}

测试结果符合预期:
在这里插入图片描述
3. 操作系统重磁盘块的标记

2.4 对应java中的类

位图在java中被封装为了BitSet这个类,不同的一点就是,我们自己实现的这个位图是用byte数组来保存数据的,在除和取模的时候是以8为单位来计算的,而java封装的这个位图是使用long数组来保存数据的,在除和取模的时候是使用64为单位来计算的,下面是常用的一些方法:

返回值	方法名	描述
void	clear(int bitIndex)	将指定的bit为设置为0
boolean	get(int bitIndex)	查看指定的值是否在位图中
void	set(int bitIndex)	将指定位置的值设置为1
String	toString()	将这个位图按照字符串的形式表示出来

下面是使用实例

public static void main(String[] args) {BitSet bitSet = new BitSet();bitSet.set(1);bitSet.set(2);bitSet.set(3);bitSet.set(4);bitSet.set(5);bitSet.set(6);System.out.println(bitSet.toString());System.out.println(bitSet.get(1));bitSet.clear(2);System.out.println(bitSet.get(2));System.out.println(bitSet.toString());
}

测试结果:
在这里插入图片描述

3. 布隆过滤器

3.1 布隆过滤器的提出

日常生活中，包括在设计计算机软件时，我们经常要判断一个元素是否在一个集合中。比如在字处理软件
中，需要检查一个英语单词是否拼写正确（也就是要判断它是否在已知的字典中）；在 FBI，一个嫌疑人的
名字是否已经在嫌疑名单上；在网络爬虫里，一个网址是否被访问过等等。最直接的方法就是将集合中全部
的元素存在计算机中，遇到一个新元素时，将它和集合中的元素直接比较即可。
一般来讲，计算机中的集合是用哈希表（hash table）来存储的。它的好处是快速准确，缺点是费存储空
间。当集合比较小时，这个问题不显著，但是当集合巨大时，哈希表存储效率低的问题就显现出来了。
比如说，一个像 Yahoo,Hotmail 和 Gmai 那样的公众电子邮件（email）提供商，总是需要过滤来自发送垃
圾邮件的人（spamer）的垃圾邮件。一个办法就是记录下那些发垃圾邮件的 email 地址。由于那些发送者
不停地在注册新的地址，全世界少说也有几十亿个发垃圾邮件的地址，将他们都存起来则需要大量的网络服
务器。
如果用哈希表，每存储一亿个 email 地址，就需要 1.6GB 的内存（用哈希表实现的具体办法是将每一个
email 地址对应成一个八字节的信息指纹,然后将这些信息指纹存入哈希表，由于哈希表的存储效率一般只有
50%，因此一个 email 地址需要占用十六个字节。一亿个地址大约要 1.6GB，即十六亿字节的内存）。因此
存贮几十亿个邮件地址可能需要上百 GB 的内存。除非是超级计算机，一般服务器是无法存储的。

用哈希表存储用户记录，缺点：浪费空间
用位图存储用户记录，缺点：位图一般只能处理整形，如果内容编号是字符串，就无法处理了。
将哈希与位图结合，即布隆过滤器.

3.2 布隆过滤器的概念

布隆过滤器是一种紧凑的,比较巧妙的概率型数据结构,特点是高效的插入和查询,可以用来告诉你某样东西一定不存在或者可能存在,不可以判断某样东西一定存在,他是用多个哈希函数,将一个数据映射到位图的结构中.此种方式不仅仅可以提升查询的效率,也可以节省大量的内存空间.
在这里插入图片描述
布隆过滤器与位图最大的区别就是,位图适合处理大量的整数.适合对这些整数进行查找/排序/去重,但如果不是整数,但是依然还是想在位图中存储数据,那么就需要使用到布隆过滤器.

3.3 布隆过滤器的插入

在这里插入图片描述
比如我们要向布隆过滤器中插入"baidu"和"tencent".
我们首先需要把这个字符经过不同的哈希函数进行映射,得到一个值之后,把他映射到位图之上.

我们看到在插入不同的数据的时候,经过不同的哈希函数映射之后的值是有可能产生重合的值的.如果这些值全部重合的话,在查找的时候就有可能产生误判.下面我们就来解释查找操作.

3.4 布隆过滤器的查找

布隆过滤器的思想是将一个元素用多个哈希函数映射到一个位图中,因此被映射到的位置的bit位一定为1.所以可以按照一下的方式进行查找:分别计算每个哈希值对应的比特位置存储的是否为0,只要有一个为0,代表该元素一定不在位图中,否则可能在哈希表中.
注意:布隆过滤器如果判断某个元素一定不存在时,该元素一定不存在,如果该元素存在时,则该元素可能存在,因为哈希函数映射之后存在一定的误判概率.
比如:在不同过滤器中查找alibaba时,假设经过哈希函数计算出的哈希值为1,3,7,刚好和其他元素的比特位重叠,此时布隆过滤器告诉该元素存在,但实际上元素是不存在的.

3.5 布隆过滤器的模拟实现

首先我们需要定义一个hash函数类,其中包含容积和随机种子.
之后我们需要在定义一个hash方法,使用这个hash函数求出对应的hash值.
实现布隆过滤器,布隆过滤器中存在若干个随机种子和默认容积.
存在hash函数数组,在为位图中设置值的时候,需要经过hash数组中每一个hash函数的计算,数组中每一个hash函数都会计算出一个hash值,最后我们需要把这些hash值全部设置到位图当中去.

import java.util.BitSet;/*** 创建Hash函数*/
class SimpleHash{private int cap;//容量private int seed;//随机种子public SimpleHash(int cap, int seed) {this.cap = cap;this.seed = seed;}/*** 根据容量和随机数种子计算得到val的Hash值* @param val 传入的值* @return 返回Hash值*/public int hash(String val){int ret = 0;int len = val.length();for (int i = 0;i < len;i++){ret = ret * seed + val.charAt(i);}return (cap-1) & ret;}
}/*** 布隆过滤器*/
public class MyBloomFilter {private static final int DEFAULT_SIZE = 1 << 24;//默认容积private static final int[] seeds = {1,6,3,5,10};//一共5个随机种子,在映射到位图中就需要把一个值映射到5个bit位.public int size;//过滤器存储元素的个数private SimpleHash[] simpleHashes;//不同种子的哈希函数private BitSet bitSet;//存储元素的位图public MyBloomFilter(){bitSet = new BitSet();//初始化位图//初始化哈希函数数组simpleHashes = new SimpleHash[seeds.length];for (int i = 0;i < seeds.length;i++){SimpleHash simpleHash = new SimpleHash(DEFAULT_SIZE,seeds[i]);simpleHashes[i] = simpleHash;}}/*** 为布隆过滤器中设置指定的值* @param val 指定的值*/public void set(String val){if (val == null){return;}for (SimpleHash simpleHash : simpleHashes) {bitSet.set(simpleHash.hash(val));}size++;}/*** 获取指定的值是否在布隆过滤器中存在* @param val 需要获取的值* @return 返回是否在布隆过滤器中存在*/public boolean get(String val){if (val == null){return false;}for (SimpleHash simpleHash : simpleHashes) {if (!bitSet.get(simpleHash.hash(val))) {//如果有一个不存在,就返回falsereturn false;}}return true;//如果全部存在,则可能存在}
}

3.6 布隆过滤器的缺陷

布隆过滤器不能直接支持删除操作,因为在删除一个元素的时候,可能会影响到其他的元素.
比如我们上面"baidu"和"tencent"的例子,想要在布隆过滤器中删除"tencent"元素,如果直接将该元素所对应的二进制位置为0,"tencent"元素和"baidu"元素刚好有一个重叠的位置,那么"baidu"元素也被删除了.
有误判率,即不能准确判断元素是否在集合中存在.
不能获取元素本身

3.7 布隆过滤器的优点

增加和查询元素的时间复杂度为:O(K), (K为哈希函数的个数，一般比较小)，与数据量大小无关,所以化简之后时间复杂度为O(1).
布隆过滤器不需要存储元素本身，在某些对保密要求比较严格的场合有很大优势
在能够承受一定的误判时，布隆过滤器比其他数据结构有这很大的空间优势,数据量很大的时候,布隆过滤器可以表示全集,而其他数据结构不可以.

3.8 布隆过滤器的常见使用场景

网页爬虫对URL的去重,避免爬取相同的URL地址.
垃圾邮件的过滤,从数十亿个垃圾邮件列表中判断某邮件是否为垃圾邮件.
解决数据库缓存击穿问题,当黑客攻击服务器的时候,会构建大量不存在于缓存中的key向服务器发起请求,在数据量足够大的时候,频繁的数据库查询会导致数据库服务器宕机.
秒杀系统,查看用户是否存在重复购买.

4. 海量数据处理

4.1 哈希切割

给一个超过100G大小的log file.log中保存着IP地址,设计算法找到出现次数最多的IP地址.

IP本身是一个字符串,先把使用哈希函数把一个字符串变为一个hash值,hash(IP)
我们需要把这些地址存入不同的文件中,首先计算出IP地址需要在那个文件中存放,即存放文件的下标.index = hash(IP)%文件数
把每个小文件都加载到内存中,统计每个文件中出现IP的次数(使用Map统计).

4.2 位图应用

给定100亿个整数,设计算法找到只出现一次的整数.
我们可以使用位图来解决,其中有两个位图,我们针对没有出现的数据在两个位图中分别使用0 0来表示,针对只出现一次数据在两个位图中分别用1 0表示,针对出现两次的数据分别使用0 1来表示,针对出现两次以上的数据使用1 1来表示.
给定两个文件,分别有100亿个整数,我们只有1G内存,如何找到两个文件的交集.
- 第一种方法使用哈希切割的方法
  首先我们把一个文件拆分为多个小文件,之后比较每个小文件中的交集((1,1)文件,(2,2)文件依次比较).
- 第二种方法是使用位图的算法.
  遍历第一个文件,把存在的数据存放到位图中,之后遍历第二个文件,看读取到的数据是否在位图中存在,如果存在,就是交集.

4.3 布隆过滤器的应用

给定两个文件,分别有100亿个query,我们只有1G内存,如果找到两个文件的交集,分别给出精确的算法和近似的算法.
- 精确算法: 利用哈希切割,把两个大文件利用hash函数分为若干个小文件,之后比较小文件之间的交集((1,1)文件,(2,2)文件以此类推).
- 近似算法: 把第一个文件中的query使用hash函数映射到布隆过滤器中,之后再把第二个文件中的query使用hash函数映射出对应的值.之后再从布隆过滤器中查找,如果存在,就是交集.如果不存在就不是.

目录