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 原理与实际》一书