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

高阶数据结构----布隆过滤器和位图

news 2025/7/21 14:48:13

（一）位图

位图是用来存放某种状态的，因为一个bit上只能存0和1所以一般只有两种状态的情况下适合用位图，所以非常适合判断数据在或者不在，而且位图十分节省空间，很适合于海量数据，且容易存储，数据无重复的场景（因为位图是天然去重的）

那我们来看一下他是如何节省空间的

我们看这个例子，如果我们不使用位图，一共10个整型数据，需要消耗40个字节，但是如果使用位图，我们就只需要3个字节就可以判断这个数字是否存在

注：10亿字节1个g

（二)位图的实现及作用

public class bitmap {public byte[] elem;public int usedSize;public bitmap() {elem=new byte[1];}//初始化位图长度public bitmap(int n) {elem=new byte[(n/8)+1];}public void setElem(int val){//找到插入第几个byte中   val/8if (val<0)throw new IndexOutOfBoundsException();int arrIndex=val/8;//找到插入到byte的第几个bit中 val%8int bitIndex=val%8;elem[arrIndex] |= (1<<bitIndex); //这里用| 之前为1的就一直为1，当前我要插入的一定会修改为1usedSize++;  //这里其实不一定正确，因为如果本身就存在这个元素，那么我们不应该++}public boolean get(int val){//找到插入第几个byte中   val/8if (val<0)throw new IndexOutOfBoundsException();int arrIndex=val/8;//找到插入到byte的第几个bit中 val%8int bitIndex=val%8;if((elem[arrIndex] & 1<<bitIndex)!=0){   //这里是用& 把其余所有位都变成0，如果当前我要找的存在就不为0return true;}return false;}public void delete(int val){//找到删除第几个byte中   val/8if (val<0)throw new IndexOutOfBoundsException();int arrIndex=val/8;//找到删除到byte的第几个bit中 val%8int bitIndex=val%8;elem[arrIndex] &=~(1<<bitIndex);usedSize--;}
}

我们之后来看一下我们的set delete和get方法中的不同点

我们发现只有对bit位的处理是不同的，找位置的代码都是一样的，所以我们就来看对bit位的处理

首先是set方法，我们是用了 | 只要有1就为1 这样是为了确保在我们添加元素的时候不影响其他bit位上的元素，如果我们变成& 就会这样

我们发现下标为5的元素被修改为0了，这显然是不对的，如果是异或那就更不对了

然后我们来看get 我们用了 & 只有都为1的时候才为1，其他都是0，也就是说我们想找这个元素，且他存在的时候才为1，其他都为0，如果使用 | 我们就无法判断了

最后一个我们看delete 我们先取反然后再& ，这样能够保证只有这一位是0，其他位全为1，如果其他位本身不存在那么1&0还是0，如果存在1&1为1还是存在，而我们要删除的位，无论如何都为0，这里可能要问，为什么不能使用异或，异或有一个情况会发生错误，如果我们删除的位置本身不存在为0，那么就会导致0^1为1，反倒存在了，所以不可以用^

我们可以使用我们的位图进行排序

 public static void main(String[] args) {int[] array = {1,3,2,13,10,3,14,18,3};final bitmap bitSet = new bitmap(18);for (int tmp:array) {bitSet.setElem(tmp);}for (int i = 0; i < bitSet.elem.length; i++) {for (int j = 0; j < 8; j++) {if((bitSet.elem[i] & (1 << j) ) != 0 ) {System.out.println(i*8+j);}}}}

其实位图我们Java也给我们实现过了