位图 | Notes

散列表

将网页链接存储在散列表中。散列表需维持较小的装载因子，保证不会出现过多的散列冲突，导致操作的性能下降。需要的内存空间过大时，采用分治的思想，用多台机器进行存储。

位图

有1千万个整数，整数的范围在1到1亿之间。快速查找某个整数是否在这1千万个整数中。

申请一个大小为1亿、数据类型为布尔类型(true/false)的数组。将这1千万个整数作为数组下标，将对应的数组设置成true。
当查询某个整数K是否在这1千万个整数中的时候，只需要将对应的数组值array[K]取出来，看是否等于true。如果等于true，说明1千万整数中包含这个整数K；相反，就表示不包含这个整数K。

布尔类型大小是1个字节，只需要一个二进制位(bit)就可以表示true和false两个值。

位图-借助char类型通过位运算实现

//java中char类型占16bit，也就是2个字节（1字节8bit）
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;
    }
}

将数字A的第K位设置为1：A = A|(1 << (k-1));
将数字A的第K位设置为0：A = A&~(1 << (k-1));
检测数字A的第k位：A&(1 << (k-1)) != 0;

位图通过数组下标来定位数据，访问效率非常高。每个数字用一个二进制位来表示，在数字范围不大的情况下，所需要的内存空间非常节省。

布隆过滤器

布隆过滤器是对位图的一种改进，针对数据范围较大的数据。

数据个数是1千万，数据的范围是1到10亿。仍然使用一个1亿个二进制大小的位图，然后通过哈希函数，对数字进行处理，让它落在这1到1亿范围内。

一个哈希函数可能会存在冲突，用多个哈希函数一块定位一个数据。
使用K个哈希函数，对同一个数字进行求哈希值，会得到K个不同的哈希值，分别记作X₁,X₂,X₃,…,X_k。把k个数字作为位图中的下标，将对应的BitMap[X₁],BitMap[X₂],BitMap[X₃],…,BitMap[X_k]都设置成true，也就是用k个二进制位，来表示一个数字的存在。

当要查询某个数字是否存在的时候，用同样的K个哈希函数，对这个数字求哈希值，分别得到Y₁,Y₂,Y₃,…,Y_k。看这k个哈希值，对应位图中的数值是否都为true，如果都是true，则说明，这个数字存在，如果有其中任意一个不为true，那就说明这个数字不存在。

对于两个不同的数字来说，经过一个哈希函数处理之后，可能会产生相同的哈希值。但是经过K个哈希函数处理之后，k个哈希值都相同的概率就非常低了。尽管采用k个哈希函数之后，两个数字哈希冲突的概率降低了，但是这种处理方式又带来了新的问题，容易误判。

布隆过滤器只会对存在的情况有误判。如果某个数字经过布隆过滤器判断不存在，那就说明这个数字真的不存在，不会发生误判；如果某个数字经过布隆过滤器判断存在，可能误判，有可能并不存在。

布隆过滤器用多个哈希函数对同一个网页链接进行处理，CPU只需要将网页链接从内存中读取一次，进行多次哈希计算，理论上讲这组操作是CPU密集型的。
而在散列表的处理方式中，需要读取散列值相同（散列冲突）的多个网页链接，分别跟判重的网页链接，进行字符串匹配，这个操作涉及很多内存数据的读取，是内存密集型的。
CPU计算比内存访问更快。

当布隆过滤器中，数据个数与位图大小的比例超过某个阈值的时候，就重新申请一个新的位图。后面来的新数据，会被放置到新的位图中。如果要判断某个数据是否在布隆过滤器中已经存在，需要查看多个位图。

扩展

Java-BitSet
Redis-BitMap
Google-Guava-BloomFilter

[1] 漫画：Bitmap算法整合版