布隆过滤器原理与实现

1. 布隆过滤器(Bloom filter)
2. 假阳性概率分析(Probability of false positives)
- 哈希函数个数 k 的确定
3. 时间/空间复杂度
- 3.1 时间
- 3.2 空间
4. 优缺点
- 4.1 优点
- 4.2 缺点
5. 常见应用场景
6. 实现

1. 布隆过滤器(Bloom filter)

简单的说，布隆过滤器由一个长度为 m 的位数组和 k 个哈希函数组成。数组初始化为0。

当添加一个元素时，分别用 k 个哈希函数计算出该元素的哈希值，这 k 个哈希值作为数组的下标，并将数组中下标对应的值置为1；
当查询一个元素时，同样的，用 k 个哈希函数计算出该元素的哈希值，这 k 个哈希值作为数组的下标。我们去查询数组中对应下标的值，如果存在一个值为0，则表明被查询的元素一定不在集合中；如果对应下标的值都为1，则表明被查询的元素可能在集合中。如果一个元素其实并不存在，但被误认为存在，我们称其为“假阳性（false positive）”

下图展示了一个 m = 18, k = 3 的布隆过滤器。集合中的 x、y、z 三个元素通过 3 个不同的哈希函数散列到数组中。当查询元素 w 时，因为有一个比特为 0，因此判定 w 不在该集合中。

2. 假阳性概率分析(Probability of false positives)

假设一个哈希函数以相等的概率选择每个数组的位置。在数组长度 m 的布隆过滤器中插入一个元素，它的其中一个哈希函数会将某个特定的比特置为 1。因此，在插入元素后，该比特仍然为 0 的概率是：

$1-{frac {1}{m}}.$

现在插 1 个元素，并假定有 k 个哈希函数，各个哈希值彼此不冲突，则该比特仍然为 0 的概率是：

$left(1-{frac {1}{m}} ight)^{k}.$

假设布隆过滤器的数组长度 m 很大(m -> ∞)，那么通过极限公式可推导出：

${displaystyle left(1-{frac {1}{m}} ight)^{k}=left(left(1-{frac {1}{m}} ight)^{m} ight)^{k/m}approx e^{-k/m}.}$

在插入 n 个元素后，该比特位上仍然保持为 0 的概率是：

${displaystyle left(1-{frac {1}{m}} ight)^{kn}approx e^{-kn/m};}$

因此，反过来说，该比特位为 1 的概率是：

${displaystyle 1-left(1-{frac {1}{m}} ight)^{kn}approx 1-e^{-kn/m}.}$

现在，我们用一个不在集合中的元素来检测，那么被误报为存在于集合中的概率（也就是所有哈希函数对应的比特都为 1 的概率），即假阳性概率为：

${displaystyle varepsilon =left(1-left[1-{frac {1}{m}} ight]^{kn} ight)^{k}approx left(1-e^{-kn/m} ight)^{k}.}$

上述的推导并不是完全正确的，因为推导背后假定每一位被设置的概率是独立的。然而事实上并不是独立的，因为误报率会随着数组长度 m 的增大而减小，随着插入元素个数 n 的增大而增大。

更详尽的分析请参考wiki。

哈希函数个数 k 的确定

另外，如果提高 k（即哈希函数的个数）就可以降低误报率。然而，如果 k 太大，那么计算哈希值的代价也会随之增大。为了使误报率最低，我们必须合理的选择 k 的大小。怎么确定 k 的大小呢？假定已经根据空间限制合理选出了 m 的大小，并且根据数据量确定了 n 的大小。也就是已知 m 和 n，可推导出 k ：

具体的推导过程如下（这部分非常重要，理解了才能真正明白为什么参数要这么设定，也才能读懂开源bloom filter的实现）：

3. 时间/空间复杂度

布隆过滤器在时间和空间方面的表现都是非常高效的。假设布隆过滤器的位数组长度为 m，有 k 个哈希函数。

3.1 时间

添加和查询的时间复杂度均为 O(k)，即对于每个元素都要经过 k 次计算得到哈希值（也就是数组的下标）。查看数组对应位置上的值只需要O(1)的时间。

3.2 空间

空间复杂度就是 O(m)。

4. 优缺点

4.1 优点

用比特数组表示，不用存储数据本身，对空间的节省相比于传统方式占据绝对的优势。
时间效率很高，无论是插入还是查询，只需要简单的经过哈希函数转换，时间复杂度均为 O(k)。

4.2 缺点

存在false positives的情况，对于准确率要求高的场景不太适用。
只能插入和查询，不能删除元素。
- 一般的布隆过滤器不支持delete操作，但是，Counting filters provide a way to implement a delete operation on a Bloom filter without recreating the filter afresh. (备忘，暂时没有深入了解)

5. 常见应用场景

网页爬虫对URL的去重，避免爬取相同的URL地址；
反垃圾邮件，从数十亿个垃圾邮件列表中判断某邮箱是否垃圾邮箱；
海量数据判重；
防止缓存穿透，将存在的数据放到布隆过滤器中，当访问不存在的数据时迅速返回，避免穿透进入数据库查询。
...

6. 实现

完整代码可参考这里。

package bloomfilter

import (
	"fmt"
	"github.com/spaolacci/murmur3"
	"github.com/willf/bitset"
	"math"
)

type BloomFilter struct {
	m uint // size of bloom filter
	k uint // number of hash functions
	b *bitset.BitSet
}

func max(x, y uint) uint {
	if x > y {
		return x
	} else {
		return y
	}
}

// 通过哈希函数产生4个基础哈希值
func baseHashes(data []byte) [4]uint64 {
	a1 := []byte{1} // to grab another bit of data
	hasher := murmur3.New128()
	hasher.Write(data) // #nosec
	v1, v2 := hasher.Sum128()
	hasher.Write(a1) // #nosec
	v3, v4 := hasher.Sum128()
	return [4]uint64{
		v1, v2, v3, v4,
	}
}

// location returns the ith hashed location using the four base hash values
func location(h [4]uint64, i uint) uint64 {
	ii := uint64(i)
	return h[ii%2] + ii*h[2+(((ii+(ii%2))%4)/2)]
}

// 通过对哈希值求余，确保位置落在[0,m)范围内
func (bf *BloomFilter) location(h [4]uint64, i uint) uint {
	return uint(location(h, i) % uint64(bf.m))
}

// 根据元素个数n，错误率p，计算出合适的布隆过滤器的参数
// 这里的 Log(2) 就是数学表示中的 ln(2)
// 这里的公式计算推导参考博客，或者参考https://en.wikipedia.org/wiki/Bloom_filter
func EstimateParameters(n uint, p float64) (m uint, k uint) {
	m = uint(math.Ceil(-1 * float64(n) * math.Log(p) / math.Pow(math.Log(2), 2)))
	k = uint(math.Ceil(math.Log(2) * float64(m) / float64(n)))
	return
}

func New(m, k uint) *BloomFilter {
	return &BloomFilter{
		m: max(m, 1), // 这么做是为了避免错误输入，保证了m至少为正数
		k: max(k, 1), // 同上
		b: bitset.New(m),
	}
}

func NewWithEstimates(n uint, p float64) *BloomFilter {
	m, k := EstimateParameters(n, p)
	return New(m, k)
}

// 对于每个插入的数据项，分别计算出k个哈希值，作为位数组的下标
func (bf *BloomFilter) Add(data []byte) *BloomFilter {
	h := baseHashes(data)
	for i:=uint(0); i < bf.k; i++ {
		bf.b.Set(bf.location(h, i)) //利用第i个哈希值确定对应的需要标记的位置
	}
	return bf
}

// Test returns true if the data is in the BloomFilter, false otherwise.
// If true, the result might be a false positive. If false, the data
// is definitely not in the set.
func (bf *BloomFilter) Test(data []byte)  bool {
	h := baseHashes(data)
	for i := uint(0); i < bf.k; i++ {
		if !bf.b.Test(bf.location(h,i)) { // 如果遇到某一位为0，则必定不存在
			return false
		}
	}
	return true
}

func main() {
	//b := bitset.New(10)
	//b.Set(4)
	//fmt.Println(b.Test(4)) // true
	//fmt.Println(b.Test(5)) // false
	//fmt.Println(b.Test(100)) // false

	filter := New(uint(1024), uint(3))
	filter.Add([]byte("ZJU"))
	fmt.Println(filter.Test([]byte("ZJU"))) // true
	fmt.Println(filter.Test([]byte("ZJNU"))) // false
}

参考：