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

位图的概念：

位图的前置知识：位运算

位图的实现：

位图的基本参数和构造方法：

位图的插入：

位图的查找：

位图的删除：

布隆过滤器概念：

布隆过滤器的实现：

布隆过滤器的基本参数：

布隆过滤器的插入：

布隆过滤器的查找：

布隆过滤器的删除：

布隆过滤器优点：

布隆过滤器缺陷：

布隆过滤器使用场景：

前言：

由于布隆过滤器是由位图实现的且这一数据结构相对其他的内容比较少，故这里就把位图和布隆过滤器一起写下。🌸🌸🌸

有需要本文章源码的友友可以前往：位图源码 / 布隆过滤器源码

位图的概念：

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

面试题：

给40亿个不重复的无符号整数，没排过序。给一个无符号整数，如何快速判断一个数是否在这40亿个数中。【腾讯】

方法1：遍历，时间复杂度O(N)

主要是内存存储不下这么大的数据，故直接遍历不行。

方法2：排序(O(NlogN))，利用二分查找: logN

同样的内存存储不下。

方法3：位图解决

可以解决👍👍👍：数据是否在给定的整形数据中，结果是在或者不在，刚好是两种状态，那么可以使用一个二进制比特位来代表数据是否存在的信息，如果二进制比特位为1，代表存在，为0代表不存在。这样就能极大的利用空间。例如（10亿个字节大概是0.9G，可看做是1G，10亿个比特位大概是119兆，看做128兆）。

🌸位图的前置知识：位运算

下面位图的实现会经常涉及到位运算，故这里讲解一下下面会用到的位运算，如果友友对着部分已经有所了解的话可以跳过❤️❤️❤️。大致可以分为下面三种情况。

（1）确定二进制表示中第x位是0，还是1

这种情况我们可以将1左移k位，最后将 n & (1 << k)即可根据结果是零还是非零（不能==1，因为每个二进制位的权重不一样😭😭😭，这个非常重要）确定二进制表示中第x位是0，还是1。

公式为： n & (1 << k)

（2）将二进制表示的第x位修改成1

不用想了这张图和上面的一样😎为了整齐换了个色。

图是一样的但是运算方法是不一样的这里是 n | (1 << k) 。

公式为： n | (1 << k)

（3）将二进制表示的第x位修改成0

公式为：n & (~(1 << x))

上面三个公式可以说是位运算最基本的公式了，建议大家一定要理解后记住，有一些面试题就是考这个的希望友友一定要熟悉。

🍓位图的实现：

位图的基本参数和构造方法：

在源码中是利用long类型的数组来实现的。

为了方便叙述我们采用byte类型数组进行叙述，其实都一样的无非就是除数不一样而已。

没有给定大小的话默认给出1个字节也就是8个比特位，有传入参数的话要给n / 8 + 1，这样可能会导致多给一个字节的情况例如（n == 16）理论只要给两个byte但是这里多给了一个（没有关系的）。

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;
    }

效果如下：