啊啊啊啊好久没打leecode了，数据结构慢慢地开始不记得了...(k恐怖！！！)

今天学习了一个数据结构——位图。

位图：

位图是用来解决大数据去重的问题的。那说到去重，脑子里第一反应就是散列表，但是散列表最大的问题是所占用的空间非常大，如果像是解决网页爬虫中的URL去重功能，一个URL的长度平均是64字节，那所需要的内存也就相当大了。怎么解决这个空间问题呢？这里有一种比较特殊的散列表——位图。

位图的原理是用数组下标来定位数据。举个例子：有一千万个整数，范围在1到一亿之间，如何快速查找某个整数是否在这1千万个整数中呢？

按照位图的思想，需要申请一个一亿长度的bitmap，每个bit位上分别对应1—1亿的整数，这一千万个整数的存在形式对应bitmap中的bit位上的1。当我们查询某个整数是否存在在这1千万个整数中时，只需要把对应的bit取出来，为1，说明1千万个整数中包含这个整数，相反，就不包含这个整数。

有个比较生动形象的介绍，这里安利给大家：

https://mp.weixin.qq.com/s/xxauNrJY9HlVNvLrL5j2hg

用代码实现bitmap：

public class BitMap {

    private char[] bytes;
    private int nbits;

    public BitMap(int nbits)
    {
        this.nbits=nbits;
        this.bytes=new char[nbits/16+1];
    }
    public void set(int k)
    {
        if(k>nbits)return ;
        int byteIndex=k/16;
        int bitIndex=k%16;
        bytes[byteIndex]|=(1<<bitIndex);
    }

    public  boolean get(int k)
    {
        if(k>nbits)
            return false;
        int byteIndex=k/16;
        int bitIndex=k%16;
        return (bytes[byteIndex]&(1<<bitIndex))!=0;
    }



}

真的太太太巧妙了~~由于没有bit类型变量，在Java中一个char为16bit（这很重要），可以看到内存简直缩小了16倍！不过这其实是增多了位运算和除运算，也就是用时间换空间。另外，可以看到位图的优势：空间不随元素个数的增加而增加，他的存储空间计算方式是找到所有元素里面最大的元素（假设为N），所占空间为：

 

可以看出，虽然位图这种数据结构能大大减少内存的使用情况，但是它开辟的空间大小是取决于数的范围大小的。也就是说，位图法所占空间随集合内最大元素的增大而增大。也就是说如果查找的元素很少但是范围特别大，那消耗的空间不容乐观。

出于性能和内存占用的考虑，在这里使用布隆过滤器进行优化：

布隆过滤器：

布隆过滤器可以精确得代表一个集合，可以精确判断某一元素是否在集合中。它实际上是一个很长的二进制矢量和一系列随机映射函数。

布隆过滤器的本质是一个位数组：数组的每个元素都只占用1bit，每个元素只能是0或者1。

除了位数组外，布隆过滤器还有k个哈希函数，当一个元素加入布隆过滤器的时候，会进行如下操作：

1.使用K个哈希函数对元素值进行K次计算，得到K个哈希值（k个哈希函数各自独立）

2.根据得到的哈希值，在位数组中把对应的下标值置为1.

图例：

很明显，数组的容量即使再大，也是有限的。那么随着元素的增加，插入的元素就会越多，位数组中被置为 1 的位置因此也越多，这就会造成一种情况：当一个不在布隆过滤器中的元素，经过同样规则的哈希计算之后，得到的值在位数组中查询，有可能这些位置因为之前其它元素的操作先被置为 1 了。

所以，有可能一个不存在布隆过滤器中的会被误判成在布隆过滤器中。这就是布隆过滤器的一个缺陷。但是，如果布隆过滤器判断某个元素不在布隆过滤器中，那么这个值就一定不在布隆过滤器中。总结就是：

• 布隆过滤器说某个元素在，可能会被误判

• 布隆过滤器说某个元素不在，那么一定不在

False is always false，true is maybe true.                   

——Boom Filter  

计算布隆过滤器的bitarray大小：

大小为m，样本数量为n，失误率为p。

需要k=In2*m/n 个哈希函数 

 

最后，使用布隆过滤器的时候需要注意到题目是要允许一定程度的失误率的哦~