什么是布隆过滤器

gitee

如果你想判断一个元素是否存在一个集合当中。一般的解决方案就是将所有的元素存储起来，然后循环判断。存储的数据结构基本上就是，数组，链表，树，哈希表等。存储位置就是磁盘或者内存。

以上的方案优点是简单。但是如果数据量比较庞大的时候，时间和空间上就不太好满足了。

1. 存储在内存中，性能是很好的。但是内存是有限的。大数据量大概率是存不下的。
2. 存储在磁盘中，数据是能存下了。但是判断时间太慢了。

布隆过滤器（Bloom Filter）就是来解决这个问题的。

原理

布隆过滤器由一组 hash 函数加一个位数组组成。

1. 添加元素，将元素经过一组 hash 函数后的结果映射到位数组相应的位置，修改为 1
2. 判断元素是否存在，同样经过这一组 hash 函数后得到的所有映射的所有位置，是否全部为 1，为 1 则元素存在。

优缺点

优点：节省空间，性能好。

缺点：有概率误判，不能删除已经添加的元素。

为什么会误判？

hash 函数发生冲突的时候，就有可能误判。

例如： hello 经过 hash 之后，映射的位置为 10。而 world 映射也是 10 。此时就冲突了。 如果存储了 hello ,那么 world 也就存储进去了。

误判是没办法解决的毕竟不能知道哪些元素会有 hash 冲突，但是可以增加 hash 函数的数量来降低hash 冲突的概率。一个 hash 函数冲突，总不能好几个 hash 函数全冲突吧。概率无限的被降低了。

还有就是增加存储的位数组的长度，空间变大了，冲突的概率也就变小了。

为什么不能删除？

因为存在误判，如果想删除 hello, 但是 hello 与 world 冲突了。你把 hello 删除了，结果连带着 world 也给删除了。删除元素会增加误判率。

实现布隆过滤器

实现 bitmap

bitmap 使用一个 uint64 切片存储。

假设切片的长度为 4，初始值就是如下所示：

0000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000

假设设置索引 index=2 的位置的值为 1，如下所示：

0000000000000000000000000000000000000000000000000000000000000100
0000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000000000000

新建 bitmap

// bitmap 位数组使用一个 uint64 切片存储
type bitmap struct {
	data []uint64 // 存储数组，每个 uint64 可以存储 64 位
}

// newBitMap 新建一个位图
// size 位图内有多少位
func newBitMap(size int) *bitmap {
	// 计算有几个元素，向上取整
	// size = 0，最少一个元素。也就是最少一个 uint64
	wordCount := (size + 64 - 1) / bitsPerWord
	return &bitmap{data: make([]uint64, wordCount)}
}

设置索引位置

// set 设置位图索引位置为 1
// index 索引
func (b *bitmap) set(index int) {
	// 假设 index = 10
	// wordIndex = 0 , 即当前 index 位，需要修改的元素在第 0 个。
	wordIndex := index / bitsPerWord

	// bitIndex = 10 , 即当前 index 位，在第 0 个元素的第 10 位。
	bitIndex := index % bitsPerWord

	// (1 << bitIndex) => 1 左移 10 位的结果是 0000 ... 0010 0000 0000，此处忽略了好多位，一共是64位，从右侧数第 10 位为 1。十进制表示结果为 1024
	// b.data[wordIndex] 此时为0，二进制就是 64 个 0

	// 0 ｜ 1024 ，二进制表示就是：0000 ... 0000 ｜ 0000 ... 0010 0000 0000,

	// ｜ 操作符的意思就是两个数，只要有一个 1 结果就是 1，其他的情况都是 0

	// 所以 0 ｜ 1024 = 1024

	// 最终结果：数组的第一个元素的二进制为：

	// 0000 ... 0010 0000 0000

	// 实现第 10 个索引位置从 0 修改为 1

	b.data[wordIndex] = b.data[wordIndex] | (1 << bitIndex)
}

清除索引位置

// clear 将位图索引位置设置为 0
// index 索引
func (b *bitmap) clear(index int) {
	wordIndex := index / bitsPerWord
	bitIndex := index % bitsPerWord

	
	// 0000 ... 0010 0000 0000 & ^0000 ... 0010 0000 0000
	// ^0000 ... 0010 0000 0000 取反
	// 0000 ... 0010 0000 0000 & 1111 ... 1101 1111 1111

	// & 都为 1 才为 1

	// 0000 ... 0000 0000 0000

	b.data[wordIndex] = b.data[wordIndex] & ^(1 << bitIndex)

判断索引位置是否为 1

// Test 判断位图索引位置是否为 1
func (b *bitmap) Test(index int) bool {
	// index = 10
	// wordIndex = 1
	wordIndex := index / bitsPerWord
	// bitIndex = 10
	bitIndex := index % bitsPerWord

	// & 都为 1 才为 1
	
	// 1024 & 1024
	
	// 0000 ... 0010 0000 0000 & 0000 ... 0010 0000 0000
	
	// 第 10 位都为 1，其他位依然为 0，结果仍然是 1024
	return b.data[wordIndex]&(1<<bitIndex) != 0
}

实现并发安全

前面的 bitmap 其实是并发不安全的，要实现并发安全也很简单。使用 sync.Mutex 即可。

func (b *bitmap) set(index uint64) {
	wordIndex := index / bitsPerWord
	bitIndex := index % bitsPerWord
	
	b.Lock()
	defer b.Unlock()
	b.data[wordIndex] = b.data[wordIndex] | (1 << bitIndex)
}

func (b *bitmap) clear(index uint64) {
	wordIndex := index / bitsPerWord
	bitIndex := index % bitsPerWord

	b.Lock()
	defer b.Unlock()
	b.data[wordIndex] = b.data[wordIndex] & ^(1 << bitIndex)
}

实现布隆过滤器

代码很简单，直接看就行，注释很完善。

type HashFunc func([]byte) uint64

type BloomFilter struct {
	bm *bitmap // 存储数据
	hashFuncs []HashFunc // 一组 hash 函数
}

// NewBloom 初始化布隆过滤器
// n 预期数据量
// p 误判率
// m 存储空间大小
// k hash 函数个数
func NewBloom(n int, p float64) *BloomFilter {
	// m k 的计算方式，参考 Java Guava 库的布隆过滤器实现。
	// 计算最佳 m 值
	m := -float64(n) * math.Log(p) / (math.Log(2) * math.Log(2))

	// 计算最佳 k 值
	// 一般都是布隆过滤器自行实现
	// k := math.Max(1, math.Round(m/float64(n)*math.Log(2)))

	hashFuncs := []HashFunc{
		fnv_1, sha256_1,
	}

	return &BloomFilter{
		bm: newBitMap(int(m)),
		hashFuncs: hashFuncs,
	}
}

// Check 验证元素是否存在
func (bf *BloomFilter) Check(item string) bool {
	for _, f := range bf.hashFuncs {
		hashcode := f([]byte(item))
		index := hashcode % bf.bm.size()

		// 判断 bitmap 中是否存在
		flag := bf.bm.test(index)
		if !flag {
			return false
		}
	}
	
	return true
}

// Add 添加元素
func (bf *BloomFilter) Add(item string) {
	for _, f := range bf.hashFuncs {
		hashcode := f([]byte(item))

		index := hashcode % bf.bm.size()

		// 判断 bitmap 中是否存在
		flag := bf.bm.test(index)
		if !flag {
			bf.bm.set(index)
		}
	}
}


// AddHashFunc 新增 hash 函数
func (bf *BloomFilter) AddHashFunc(f HashFunc) {
	bf.hashFuncs = append(bf.hashFuncs, f)
}

func fnv_1(data []byte) uint64 {
	h := fnv.New64a()
	h.Write(data)
	return h.Sum64()
}

func sha256_1(data []byte) uint64 {
	h := sha256.New()
	h.Write(data)
	return binary.BigEndian.Uint64(h.Sum(nil)[:8])
}