HBase源码分析5—BloomFilter

15. 2月 2018 hbase, 数据库 1

源码分析的5和6两篇合起来准备一起探讨HBase的底层存储格式,BloomFilter Block也是HFile的一部分。但是BloomFilter这个东西思想上虽然很简单,但是原理上并不简单,所以把BloomFilter这部分单独拎出来讲一下。

BloomFilter介绍

是什么

BloomFilter是一种基于概率的存在检测算法。我们把BloomFilter看做是一个有m个bit位的数组 S[1..m] ,另外我们还拥有 k 个相互独立的哈希函数 H[1..k] 。当向BloomFilter中添加元素 x 时,先计算哈希结果 R=H(x) ,然后将R中的每个结果对应的 S[R[i]] 的位置1。当查询时,同样的计算哈希结果 R=H(x) ,然后查询