Go语言实现布隆过滤器

1 布隆过滤器原理

布隆过滤器一般用来判断一个数据是否在一个很大的数据集合里面。当然可以用数组，集合，树等数据结构和各种查找法都可以做同样的事情，但是布隆过滤器有更好的时间效率和空间效率。比特币实现SPV节点时使用了布隆过滤器来查询交易。布隆过滤器可以判断一个数在不在集合里，但存在一定的误判率。

布隆过滤器的核心是一个超大的位数组和几个哈希函数。假设位数组的长度为m,哈希函数的个数为k。

 

以上图为例，在这里维数组长度为18，哈希函数个数为3个。首先将维数组所有位全部置0。集合中有的3个数据x,y,z，通过3个哈希函数对每一个数据进行计算，得到该数据的哈希值，这个哈希值对应维数组上面的一个点，然后将对应位数组的位置1。这样3个数据会生成9个点。对于另外一个数据w，查询它 在不在集合中的方法是对w通过3个哈希函数映射到位数组上，判断3个映射位置是否为1。只要有一个位置为0，就能说明w一定不在集合中。反之如果3个点都为1，则说明这个元素可能在集合中。此处不能判断元素一定在集合中，因为存在一定的误判率。比如对于上图中的4,5,6这3个位置都为1，但是它是不同的数据映射到的点。如果有一个数据刚好映射到这3个位置，虽然它不在集合中，但是我们也会误判它。

添加元素

• 将要添加的元素给k个哈希函数进行计算
• 得到位于位数组上面的k个位置
• 将位数组上对应位置1

查询元素

• 将要查询的元素给k个哈希函数
• 得到对应于位数组上的k个位置
• 如果k个位置有一个为0，则肯定不在集合中
• 如果k个位置全部为1，则可能在集合中

2 go语言实现

package main
 
import (
	"github.com/willf/bitset"
	"fmt"
)
const DEFAULT_SIZE = 2<<24
var seeds = []uint{7, 11, 13, 31, 37, 61}
 
type BloomFilter struct {
	set *bitset.BitSet
	funcs [6]SimpleHash
}
 
func NewBloomFilter() *BloomFilter {
	bf := new(BloomFilter)
	for i:=0;i< len(bf.funcs);i++{
		bf.funcs[i] = SimpleHash{DEFAULT_SIZE,seeds[i]}
	}
	bf.set = bitset.New(DEFAULT_SIZE)
	return bf
}
 
func (bf BloomFilter) add(value string){
	for _,f:=range(bf.funcs){
		bf.set.Set(f.hash(value))
	}
}
 
func (bf BloomFilter) contains(value string) bool  {
	if(value == ""){
		return false
	}
	ret := true
	for _,f:=range(bf.funcs){
		ret = ret && bf.set.Test(f.hash(value))
	}
	return ret
}
 
 
type SimpleHash struct{
	 cap uint
	 seed uint
}
 
func (s SimpleHash) hash(value string) uint{
	var result uint = 0
	for i:=0;i< len(value);i++{
		result = result*s.seed+uint(value[i])
	}
	return (s.cap-1)&result
}
 
func main(){
	filter := NewBloomFilter()
	fmt.Println(filter.funcs[1].seed)
	str1 := "hello,bloom filter!"
	filter.add(str1)
	str2 := "A happy day"
	filter.add(str2)
	str3 := "Greate wall"
	filter.add(str3)
	fmt.Println(filter.contains(str1))
	fmt.Println(filter.contains(str2))
	fmt.Println(filter.contains(str3))
	fmt.Println(filter.contains("blockchain technology"))
}

这里位数组用了一个第三方的bitset库，见github：github.com/willf/bitset

打印结果：

11
true
true
true
false