位图&布隆过滤器的原理及实现

public byte[] elem;//利用byte数组来做
    private int usedSize;//表示当前位图有多少个数据

    /**
     * 默认构造方法给出1个字节。
     */
    public MyBitSet(){
        elem = new byte[1];
    }

    /**
     * 根据需要创建大小可能会多创建一个字节，但是没有关系。
     * @param n
     */
    public MyBitSet(int n){
        elem = new byte[n / 8 + 1];
    }

位图的插入：

养成好习惯🌸🌸🌸，如果传入一些明显不符合实际情况的值，要抛一个异常。

异常的名字就根据实际情况来写，异常要单独写一个类。

public class negativeException extends RuntimeException{
    public negativeException(){
        super();
    }
    public negativeException(String message){
        super(message);
    }
}

set：位图的插入，传入负数给出异常（我们这里只写无符号整数的情况，如果要实现负数的话，那就要给对应的数，加上值给他映射成正数的情况）。因为我们是byte数组8个字节所以除以8，如果是long的话就要除以64，除找到在数组中的对应下标，模是找到具体的bit位。

插入元素一定一定要考虑扩容😎，位图具有去重的作用故如果val已经存入的话直接return即可。

至于如何将对应bit位设置成1在上面位运算已经讲的很明白了，这里就不再赘述。

public void set(int val){
        if(val < 0){
            throw new negativeException("传入负数异常");
        }
        int arrayIndex = val / 8;//计算在byte数组对应下标
        int bitIndex = val % 8;//计算在byte数的具体哪个bit位。
        //插入就有可能会越界
        //要考虑arrayIndex越界的情况。
        if(arrayIndex + 1 > elem.length){
            //越界需要扩容
            elem = Arrays.copyOf(elem,arrayIndex + 1);
        }
        if((elem[arrayIndex] & (1 << bitIndex)) != 0){
            //这个数已经存在
            return;
        }else{
            //这个数不存在
            //把这个数对应关系存入位图
            this.elem[arrayIndex] |= (1 << bitIndex);
            usedSize++;
        }
    }

位图的查找：

判断val数是否在位图中，这个简单，唯一注意点就是越界直接return false不用扩容。其他代码里面都有注释了。

/**
     * 判断val数是否在位图中
     * @param val
     * @return
     */
    public boolean get(int val){
        if(val < 0){
            throw new negativeException("传入负数异常");
        }
        int arrayIndex = val / 8;//计算在byte数组对应下标
        int bitIndex = val % 8;//计算在byte数的具体哪个bit位。
        //防止越界
        if(arrayIndex + 1 > elem.length){
            return false;
        }
        if((elem[arrayIndex] & (1 << bitIndex)) == 0){
            //不存在
            return false;
        }else{
            //存在
            return true;
        }
    }

位图的删除：

运用位图的前置知识：位运算（3）将二进制表示的第x位修改成0来实现位图的删除，具体代码如下所示：🎉🎉🎉

/**
     * 将位图中val对应关系删除
     * @param val
     */
    public void reSet(int val){
        if(val < 0){
            throw new negativeException("负数异常");
        }
        int arrayIndex = val / 8;//计算在byte数组对应下标
        int bitIndex = val % 8;//计算在byte数的具体哪个bit位。
        if(arrayIndex + 1 > elem.length){
            //超过存储大小必定不存在，不存在直接返回
            return;
        }else{
            //先判断存不存在
            if((elem[arrayIndex] & (1 << bitIndex)) != 0){
                //存在
                elem[arrayIndex] &= (~(1 << bitIndex));
                usedSize--;
            }
        }
    }

到这我们位图就已经学完了🎉🎉🎉 ，下面我们将开始介绍布隆过滤器，是基于位图实现的。

效果如下：

布隆过滤器提出：

日常生活中，包括在设计计算机软件时，我们经常要判断一个元素是否在一个集合中。比如在字处理软件中，需要检查一个英语单词是否拼写正确（也就是要判断它是否在已知的字典中）；在 FBI，一个嫌疑人的名字是否已经在嫌疑名单上；在网络爬虫里，一个网址是否被访问过等等。最直接的方法就是将集合中全部的元素存在计算机中，遇到一个新元素时，将它和集合中的元素直接比较即可。

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

比如说，一个像 Yahoo,Hotmail 和 Gmai 那样的公众电子邮件（email）提供商，总是需要过滤来自发送垃圾邮件的人（spamer）的垃圾邮件。一个办法就是记录下那些发垃圾邮件的 email 地址。由于那些发送者不停地在注册新的地址，全世界少说也有几十亿个发垃圾邮件的地址，将他们都存起来则需要大量的网络服务器。

布隆过滤器概念：

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

实现布隆过滤器需要多个哈希函数，为了方便描述我们下面布隆过滤器的代码实现采用下面的哈希函数：

利用随机种子和容量来创建不同的哈希函数（可以不一样，只要能区分开来就行）。

class SimpleHash{
    private int cap;//容量
    private int seed;//随机种子
    public SimpleHash(int cap,int seed){
        this.cap = cap;
        this.seed = seed;
    }

    /**
     * 把val字符串变成一个哈希值
     * @param val
     * @return
     */
    public int hash(String val){
        int result = 0;
        for(int i = 0;i < val.length();i++){
            result = result * seed + val.charAt(i);
        }
        return result & (cap - 1);
    }
}

🍒布隆过滤器的实现：

布隆过滤器的基本参数：

我们定义一个容量大小为2^24次方大小的位图，将多个函数设置为数组（SimpleHash[]）方便调用,在调用MyBloomFilter类似通过传进构造方法的参数实现对哈希函数的初始化。😎😎😎

private static final int DEFAULT_SIZE = 1 << 24;
private static final int[] seeds = new int[]{5,7,11,13,31,37,61};//随机数
private BitSet bitSet;//位图
private SimpleHash[] hashFun;
public MyBloomFilter(){
    //创建位图
    bitSet = new BitSet(DEFAULT_SIZE);
    hashFun = new SimpleHash[seeds.length];
    //初始化哈希方法
    for(int i = 0;i < seeds.length;i++){
        hashFun[i] = new SimpleHash(DEFAULT_SIZE,seeds[i]);
    }
}

布隆过滤器的插入：

在位图的插入时是利用多个哈希函数将得到的哈希值对应到位图位置置为1，可能会存在两个不同元素哈希值相同的情况，所以我们说布隆过滤器是比较巧妙的概率型数据结构，它只能表明某样东西一定不存在或者可能存在。

通过多个哈希函数将对应哈希值映射到位图中。

/**
     * 将字符串value添加到布隆过滤器
     * @param value
     */
    public void set(String value){
        if(value == null){
            return;
        }
        for(SimpleHash fun:hashFun){
            bitSet.set(fun.hash(value));
        }
    }

布隆过滤器的查找：

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

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

利用位图进行查找。

/**
     * 判断value元素在不在布隆过滤器中，可能有误判
     * @param value
     * @return
     */
    public boolean contains(String value){
        for(SimpleHash fun:hashFun){
            int index = fun.hash(value);
            if(bitSet.get(index) == false){
                return false;
            }
        }
        //会有误判
        return true;
    }

效果如下：

布隆过滤器的删除：

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

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

👍布隆过滤器优点：

（1）增加和查询元素的时间复杂度为:O(K), (K为哈希函数的个数，一般比较小)，与数据量大小无关。

（2）哈希函数相互之间没有关系，方便硬件并行运算。

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

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

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

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

😭布隆过滤器缺陷：

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

（2）不能获取元素本身。

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

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

😎布隆过滤器使用场景：

（1）google的guava包中有对Bloom Filter的实现。

（2）网页爬虫对URL的去重，避免爬去相同的URL地址。

（3）垃圾邮件过滤，从数十亿个垃圾邮件列表中判断某邮箱是否是垃圾邮箱。

（4）解决数据库缓存击穿，黑客攻击服务器时，会构建大量不存在于缓存中的key向服务器发起请求，在数据量足够大的时候，频繁的数据库查询会导致挂机。

（5）秒杀系统，查看用户是否重复购买。

总结：布隆过滤器和位图主要是使用在大量数据的情况，布隆过滤器和位图相比布隆过滤器支持存储除了整形之外的数据类型，而位图只能存储整形🎉🎉🎉。

结语：

其实写博客不仅仅是为了教大家，同时这也有利于我巩固知识点，和做一个学习的总结，由于作者水平有限，对文章有任何问题还请指出，非常感谢。如果大家有所收获的话还请不要吝啬你们的点赞收藏和关注，这可以激励我写出更加优秀的文章。