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

（一）位图

位图是用来存放某种状态的，因为一个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/8
        if (val<0)throw new IndexOutOfBoundsException();
        int arrIndex=val/8;
        //找到插入到byte的第几个bit中 val%8
        int bitIndex=val%8;
        elem[arrIndex] |= (1<<bitIndex); //这里用| 之前为1的就一直为1，当前我要插入的一定会修改为1
        usedSize++;  //这里其实不一定正确，因为如果本身就存在这个元素，那么我们不应该++
    }
    public boolean get(int val){
        //找到插入第几个byte中   val/8
        if (val<0)throw new IndexOutOfBoundsException();
        int arrIndex=val/8;
        //找到插入到byte的第几个bit中 val%8
        int bitIndex=val%8;
        if((elem[arrIndex] & 1<<bitIndex)!=0){   //这里是用& 把其余所有位都变成0，如果当前我要找的存在就不为0
            return true;
        }
        return false;
    }
    public void delete(int val){
        //找到删除第几个byte中   val/8
        if (val<0)throw new IndexOutOfBoundsException();
        int arrIndex=val/8;
        //找到删除到byte的第几个bit中 val%8
        int 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也给我们实现过了