算法背景

如果想判断一个元素是不是在一个集合里，一般想到的是将集合中所有元素保存起来，然后通过比较确定。链表、树、散列表（又叫哈希表，Hash table）等等数据结构都是这种思路，存储位置要么是磁盘，要么是内存。很多时候要么是以时间换空间，要么是以空间换时间。
在响应时间要求比较严格的情况下，如果我们存在内里，那么随着集合中元素的增加，我们需要的存储空间越来越大，以及检索的时间越来越长，导致内存开销太大、时间效率变低。

此时需要考虑解决的问题就是，在数据量比较大的情况下，既满足时间要求，又满足空间的要求。即我们需要一个时间和空间消耗都比较小的数据结构和算法。Bloom Filter就是一种解决方案。

Bloom Filter 概念

布隆过滤器（英语：Bloom Filter）是1970年由布隆提出的。它实际上是一个很长的二进制向量和一系列随机映射函数。布隆过滤器可以用于检索一个元素是否在一个集合中。它的优点是空间效率和查询时间都远远超过一般的算法，缺点是有一定的误识别率和删除困难。
布隆过滤器的原理是，当一个元素被加入集合时，通过K个散列函数将这个元素映射成一个位数组中的K个点，把它们置为1。检索时，我们只要看看这些点是不是都是1就（大约）知道集合中有没有它了：如果这些点有任何一个0，则被检元素一定不在；如果都是1，则被检元素很可能在。这就是布隆过滤器的基本思想。
Bloom Filter跟单哈希函数Bit-Map不同之处在于：Bloom Filter使用了k个哈希函数，每个字符串跟k个bit对应。从而降低了冲突的概率。

缺点

bloom filter之所以能做到在时间和空间上的效率比较高，是因为牺牲了判断的准确率、删除的便利性
• 存在误判，可能要查到的元素并没有在容器中，但是hash之后得到的k个位置上值都是1。如果bloom filter中存储的是黑名单，那么可以通过建立一个白名单来存储可能会误判的元素。
• 删除困难。一个放入容器的元素映射到bit数组的k个位置上是1，删除的时候不能简单的直接置为0，可能会影响其他元素的判断。可以采用Counting Bloom Filter

hbase何时使用布隆过滤

1. get操作会enable bloomfilter帮助剔除掉不会用到的Storefile
   在scan初始化时（get会包装为scan）对于每个storefile会做shouldSeek的检查，如果返回false，则表明该storefile里没有要找的内容，直接跳过

if (memOnly == false  
            && ((StoreFileScanner) kvs).shouldSeek(scan, columns)) {  
          scanners.add(kvs);  
}

2. shouldSeek方法：如果是scan直接返回true表明不能跳过，然后根据bloomfilter类型检查。

if (!scan.isGetScan()) {  
        return true;  
}  
byte[] row = scan.getStartRow();  
switch (this.bloomFilterType) {  
  case ROW:  
    return passesBloomFilter(row, 0, row.length, null, 0, 0);  
  case ROWCOL:  
    if (columns != null && columns.size() == 1) {  
      byte[] column = columns.first();  
      return passesBloomFilter(row, 0, row.length, column, 0, column.length);  
    }  
    // For multi-column queries the Bloom filter is checked from the  
    // seekExact operation.  
    return true;   
  default:  
    return true;
}