1.案例

如何高效判断元素w是否存在于汇合A之中？首先想到的答案是，把汇合A中的元素一个个放到哈希表中，而后在哈希表中查一下w即可。这样的确能够解决小数据量场景下元素存在性断定，但如果A中元素数量微小，甚至数据量远远超过机器内存空间，该如何解决问题呢？

实现一个基于磁盘和内存的哈希索引当然能够解决这个问题。而另一种低成本的形式就是借助布隆过滤器（Bloom Filter）来实现。

布隆过滤器由一个长度为N的01数组array组成。首先将数组array每个元素初始设为0。对汇合A中的每个元素w，做K次哈希，第i次哈希值对N取模失去一个index(i)，即index(i)=HASH_i(w)%N，将array数组中的array[index(i)]置为1。最终array变成一个某些元素为1的01数组。

上面举个例子，如图所示，A={x, y, z}，N=18，K=3。


初始化array=000000000000000000。对元素x，HASH_0(x)%N=1，HASH_1(x)%N=5，HASH_2(x)%N=13。
因而array=010001000000010000。对元素y，HASH_0(y)%N=4，HASH_1(y)%N=11，HASH_2(y)%N=16。
因而array=010011000001010010。对元素z，HASH_0(z)%N=3，HASH_1(y)%N=5，HASH_2(y)%N=11。
因而array=010111000001010010。最终失去的布隆过滤器串为：010111000001010010。

此时，对于元素w，K次哈希值别离为：
HASH_0(w)%N=4
HASH_1(w)%N=13
HASH_2(w)%N=15
能够发现，布隆过滤器串中的第15位为0，因而能够确认w必定不在汇合A中。
因为若w在A中，则第15位必然为1。

如果有另外一个元素t，K次哈希值别离为：
HASH_0(t)%N=5
HASH_1(t)%N=11
HASH_2(t)%N=13
咱们发现布隆过滤器串中的第5、11、13位都为1，然而却没法必定t肯定在汇合A中。

因而，布隆过滤器串对任意给定元素w，给出的存在性后果为两种：

•w可能存在于汇合A中。
•w必定不在汇合A中。

当N取K*|A|/ln2时（其中|A|示意汇合A元素个数），能保障最佳的误判率，所谓误判率也就是过滤器断定元素可能在汇合中但理论不在汇合中的占比。

举例来说，若汇合有20个元素，K取3时，则设计一个N=3×20/ln2=87二进制串来保留布隆过滤器比拟适合。

2.算法实现

布隆过滤器的代码实现很短，如下所示：

public class BloomFilter {    private int k;    private int bitsPerKey;    private int bitLen;    private byte[] result;    public BloomFilter(int k,int bitsPerKey) {        this.k = k;        this.bitsPerKey = bitsPerKey;    }    public byte[] generate(byte[][] keys) {        assert keys != null;        bitLen=keys.length * bitsPerKey;        bitLen=((bitLen+7) / 8) << 3;        bitLen=bitLen < 64 ? 64 : bitLen;        result = new byte[bitLen >> 3];        for ( int i=0; i < keys.length;i++){            assert keys[i] != null;            int h = Bytes.hash(keys[i]);            for (int t=0; t < k; t++){                int idx = (h % bitLen + bitLen) % bitLen;                result[idx / 8] |= (1 << (idx % 8));                int delta=(h >> 17) | (h << 15);                h += delta;            }        }        return result;    }    public boolean contains(byte[] key) {        assert result != null;        int h=Bytes.hash(key);        for (int t=0; t < k; t++) {            int idx = ( h % bitLen + bitLen) % bitLen;            if ((result[idx / 8] & (1 << (idx % 8))) == 0) {                return false;            }            int delta=(h >> 17) | (h << 15);            h += delta;        }        return true;    }}

有两个中央阐明一下：

•在构造方法BloomFilter(int k, int bitsPerKey)中，k示意每个Key哈希的次数，bitsPerkey示意每个Key占用的二进制bit数，若有x个Key，则N=x*bitsPerKey。

•在实现中，对Key做k次哈希时，算出第一次哈希值h之后，可借助h位运算来实现二次哈希，甚至三次哈希。这样性能会比拟好。

3.案例解答

有了布隆过滤器这样一个存在性判断之后，咱们回到最开始提到的案例。把汇合A的元素依照程序分成若干个块，每块不超过64KB，每块内的多个元素都算出一个布隆过滤器串，多个块的布隆过滤器组成索引数据。为了判断元素w是否存在于汇合A中，先对w计算每一个块的布隆过滤器串的存在性后果，若后果为必定不存在，则持续判断w是否可能存在于下一个数据块中。若后果为可能存在，则读取对应的数据块，判断w是否在数据块中，若存在则示意w存在于汇合A中；若不存在则持续判断w是否在下一个数据块中。这样就解决了这个问题。

4. HBase与布隆过滤器

正是因为布隆过滤器只需占用极小的空间，便可给出“可能存在”和“必定不存在”的存在性判断，因而能够提前过滤掉很多不必要的数据块，从而节俭了大量的磁盘IO。HBase的Get操作就是通过使用低成本高效率的布隆过滤器来过滤大量有效数据块的，从而节俭大量磁盘IO。

在HBase 1.x版本中，用户能够对某些列设置不同类型的布隆过滤器，共有3种类型。

• NONE：敞开布隆过滤器性能。
• ROW：依照rowkey来计算布隆过滤器的二进制串并存储。Get查问的时候，必须带rowkey，所以用户能够在建表时默认把布隆过滤器设置为ROW类型。
• ROWCOL：依照rowkey+family+qualif ier这3个字段拼出byte[]来计算布隆过滤器值并存储。如果在查问的时候，Get能指定rowkey、family、qualifier这3个字段，则必定能够通过布隆过滤器晋升性能。然而如果在查问的时候，Get中短少rowkey、family、qualif ier中任何一个字段，则无奈通过布隆过滤器晋升性能，因为计算布隆过滤器的Key不确定。

文章基于《HBase原理与实际》一书