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

位图布隆过滤器

news 来源：原创 2025/8/3 3:45:25

1.位图

所谓位图，就是用每一位来存放某种状态，适用于海量数据，整数，数据无重复的场景。通常是用来判断某个数据存不存在的。

如上例子，10个整数本应该存放需要40个字节，此时用位图只需要3个字节。

下面代码：储存结果并不是将结果本身存储起来，

1.先找到位于所定范围的对应的bit位

2.将对应的bit为置为1，即可

package bitset;import java.util.Arrays;public class MyBitset {public int usedsize;//记录有效数字的个数public byte[] arr;//自己赋值确定数组的大小public MyBitset(int n) {this.arr=new byte[n/8+1];}//没有赋值默认数组长度大小public MyBitset() {this.arr=new byte[1];}/**** @param val  可以等价于 将数据的对应位置置为1*/public void set(int val){if(val<0){throw new IndexOutOfBoundsException();}//确定数字存储的位置int arrayindex=val/8;//扩容if(arrayindex>arr.length-1){arr= Arrays.copyOf(arr,arrayindex+1);}int bitindex=val%8;//将对应的二进制位置为1arr[arrayindex]=(byte)(arr[arrayindex]| (1<<bitindex));usedsize++;}/**** @param val 测试该数字是否存在* @return*/public boolean get(int val){if(val<0){throw new IndexOutOfBoundsException();}//确定数字存储的位置int arrayindex=val/8;int bitindex=val%8;if((arr[arrayindex]&(1<<bitindex))!=0){return true;}return false;}/**** @param val  可以等价于 将数据的对应位置置为0*/public void reset(int val){if(val<0){throw new IndexOutOfBoundsException();}//确定数字存储的位置int arrayindex=val/8;int bitindex=val%8;int cur=arrayindex;arr[arrayindex]=(byte) (arr[arrayindex]& ~(1<<bitindex));if(cur!=arr[arrayindex]){usedsize--;}}public int getUsedsize(){return usedsize;}
}

完成好自己建造的位图后在测试类运行，可以发现下面代码对数组进行了一个去重和排序的操作

位图可以的操作

1. 快速查找某个数据是否在一个集合中

2. 排序 + 去重

3. 求两个集合的交集、并集等

4. 操作系统中磁盘块标记

2.布隆过滤器

2.1布隆过滤器的原理

一般来讲，计算机中的集合是用哈希表（hash table）来存储的。它的好处是快速准确，缺点是费存储空间。当集合比较小时，这个问题不显著，但是当集合巨大时，哈希表存储效率低的问题就显现出来了。

1. 用哈希表存储用户记录，缺点：浪费空间

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

布隆过滤器比较巧妙的概率型数据结构，特点是高效地插入和查询，可以用来告诉你 “某样东西一定不存在或者可能存在”，它是用多个哈希函数，将一个数据映射到位图结构中。此种方式不仅可以提升查询效率，也可以节省大量的内存空间。

布隆过滤器的思想是将一个元素用多个哈希函数映射到一个位图中，因此被映射到的位置的比特位一定为1。所以可以按照以下方式进行查找：分别计算每个哈希值对应的比特位置存储的是否为零，只要有一个为零，代表该元素一定不在哈希表中，否则可能在哈希表中。

注意：布隆过滤器如果说某个元素不存在时，该元素一定不存在，如果该元素存在时，该元素可能存在，因为有些哈希函数存在一定的误判。

比如：在布隆过滤器中查找"alibaba"时，假设3个哈希函数计算的哈希值为：1、3、7，刚好和其他元素的比特位重叠，此时布隆过滤器告诉该元素存在，但实该元素是不存在的。

布隆过滤器的插入

比如下面就是给出三个hash函数，对X,Y,Z,分别进行hash在储存在位图中分别储存三个位置

2.2布隆过滤器的实现

package BurtonowardBloom;import java.util.BitSet;//构建哈希函数
class SimpleHash{//容量//cap在下面hash函数中有作用，cap就是保证hash·计算出来的值保证在在0~cap-1之间private  int cap;//随机种子//用于生成多样化的hash函数，减少冲突private int seed;public SimpleHash(int cap, int seed) {this.cap = cap;this.seed = seed;}/*** 把当前字符串转换成一个哈希值* (cap-1)&result：保证了返回的hash值在0~cap-1之间* seed:不同的seed会导致不同的权重分配，从而生成不同的hash值* value.charAt(i)：导致最后的hash值是一个字符串中每一个字母都影响的结果* @param value* @return*/public int hash(String value){int result=0;int len =value.length();for(int i=0;i<len;i++){result=seed*result+value.charAt(i);}return (cap-1)&result;}
}public class BloomFilter {private  static  final int DEFAULT_SIZE =1<<24;//都是质数，提高了hash函数之间的独立性private  static final int [] seeds=new int[]{5,7,11,13,31,37,61};public BitSet bits;//位图用于存储元素private  SimpleHash [] func ;//哈希函数所对应的类private  int size=0;//初始化bits和funcpublic BloomFilter() {this.bits = new BitSet(DEFAULT_SIZE);this.func = new SimpleHash[seeds.length];//把所有的哈希对象进行初始化for(int i=0;i<seeds.length;i++){func[i]=new SimpleHash(DEFAULT_SIZE,seeds[i]);}}public void set(String value){if(value==null){return;}for(SimpleHash f:func){bits.set(f.hash(value));}size++;}public boolean contains(String value){if(value==null){return false;}for(SimpleHash f:func){if (!bits.get(f.hash(value))){return false;}}return true;//会有误判}
}

布隆过滤器的直接运用

先要导入依赖

 <dependency><groupId>com.google.guava</groupId><artifactId>guava</artifactId><version>19.0</version></dependency>

测试中再导入其对应的包即可

2.3布隆过滤器的优缺点

1.布隆过滤器的优点

1. 增加和查询元素的时间复杂度为:O(K), (K为哈希函数的个数，一般比较小)，与数据量大小无关 2. 哈希函数相互之间没有关系，方便硬件并行运算

3. 布隆过滤器不需要存储元素本身，在某些对保密要求比较严格的场合有很大优势

4. 在能够承受一定的误判时，布隆过滤器比其他数据结构有这很大的空间优势

5. 数据量很大时，布隆过滤器可以表示全集，其他数据结构不能

6. 使用同一组散列函数的布隆过滤器可以进行交、并、差运算

2.布隆过滤器的缺点

1. 有误判率，即存在假阳性(False Position)，即不能准确判断元素是否在集合中(补救方法：再建立一个白名单，存储可能会误判的数据)

2. 不能获取元素本身

3. 一般情况下不能从布隆过滤器中删除元素

4. 如果采用计数方式删除，可能会存在计数回绕问题

布隆过滤器不能直接支持删除工作，因为在删除一个元素时，可能会影响其他元素。

比如：删除"tencent"元素，如果直接将该元素所对应的二进制比特位置0，“baidu”元素也被删除了，因为这两个元素在多个哈希函数计算出的比特位上刚好有重叠。

一种支持删除的方法：将布隆过滤器中的每个比特位扩展成一个小的计数器，插入元素时给k个计数器(k个哈希函数计算出的哈希地址)加一，删除元素时，给k个计数器减一，通过多占用几倍存储空间的代价来增加删除操作。

缺陷：

1. 无法确认元素是否真正在布隆过滤器中【会有误判】

2. 存在计数回绕【回绕意思为：溢出】

1.哈希切割

给一个超过100G大小的log file, log中存着IP地址, 设计算法找到出现次数最多的IP地址？与上题条件相同，如何找到top K的IP？

解法：哈希切割

上面问题：就是100G在运行的时候存不下

将上面100G分成200份

步骤

1.IP本身就是一个字符串，先把IP变成一个整数，hash（IP）

2.文件的下标index=hash（IP）%200

3.读取每个文件的内容，统计每个文件的IP出现的次数即可。可以用Map

2.位图运用

1. 给定100亿个整数，设计算法找到只出现一次的整数？

解法一：哈希切割

这里出现的次数可能是1次，2次，3次

把数字哈希到对用的小文件中，一样的数字一定在一起，遍历一边小文件统计数字，此时即可知道那些数字出现了一次

解法二：两个位图

使用两个位图来做

再对两个位图对应的数字来判断

0 0：表示一次都没出现

0 1：表示出现过一次

1 0：表示出现过两次

1 1：表示出现过两个以上

解法三：一个位图

01两个bit位表示0的个数，23两个bit位表示1的个数，45两个bit位表示2的个数，67两个bit位表示3的个数，依次类推

公式：
int arrayindex=val/4；

int bitindex=val%4*2；

1%4=1*2=2；

2%4=2*2=4；

3%4=3*2=6；

2. 给两个文件，分别有100亿个整数，我们只有1G内存，如何找到两个文件交集？

解法1：哈希切割

1.先将一个两个大文件各自分成若干掉小文件

2.再将A的第一个小文件和B第一个小文件进行遍历看是否有相同元素，依次类推

解法二：位图

1.遍历第一个文件，将第一个文件的数据存入到bitSet1中

2.遍历第二个文件，将第二个文件的数据存入到bitSet中

交集

并集

差集

1.位图

2.布隆过滤器

2.1布隆过滤器的原理

2.2布隆过滤器的实现

2.3布隆过滤器的优缺点

相关文章：