1。布隆过滤器原理
如何判断一个元素是否在集合中?
一般想法是将集合所有元素保存起来,然后通过查找确定。Hashtable比较合适,O(1)的平均时间复杂度,但Hashtable一个比较大的问题是空间效率,一般存储n个元素,需要2n大小空间。
而Bloom Filter实现同样的功能,使用更小的空间。
原理:
1)一个非常大的bit数组(len=m),2)一组哈希函数(size=k)
bit数组置0,将元素通过k个哈希函数计算,将bit数组相应offset置位为1。查找时,亦将元素通过k个哈希函数,分别检查offset bit位,若任一个为0,则该元素一定不存在集合中。
Bloom Filter只能用来判断不存在的情况。判断存在有false-positive,即如果检查全部是1,也不能确定是否存在。
2。应用
1)防缓存击穿,2)爬虫URL去重,3)垃圾邮件地址过滤
3。Go语言实现
实现2个函数:
type Interface interface {
Add(item []byte) // 元素加入bloom filter
Test(item []byte) bool // 检查元素是否存在
}
定义Bloom Filter数据结构:
// BloomFilter probabilistic data structure definition
type BloomFilter struct {
bitset []bool // 简单起见,使用bool数组代替bitset
k uint // hash函数个数
n uint // bloom filter中已存在元素个数
m uint // bitset长度
hashFuncs[]hash.Hash64 // hash函数数组
}
Add函数:
func (bf *BloomFilter) Add(item []byte) {
hashes := bf.hashValues(item)
i := uint(0)
for {
if i >= bf.k {
break
}
position := uint(hashes[i]) % bf.m
bf.bitset[uint(position)] = true
i+= 1
}
bf.n += 1
}
Test函数:
func (bf *BloomFilter) Test(item []byte) (exists bool) {
hashes := bf.hashValues(item)
i := uint(0)
exists = true
for {
if i >= bf.k {
break
}
position := uint(hashes[i]) % bf.m
if !bf.bitset[uint(position)] {
exists = false
break
}
i+= 1
}
return
}
4。bitset版本
上面版本使用的是伪的bitset,提高内存效率可以使用真正的bitset代替bitset []bool
https://github.com/willf/bitset
bitset []bool -> bitset.BitSet即可
另外支持分布式的Bloom Filter可以使用redis的bitmap实现。
————
前几天有个需求,检查每个用户是否第一次访问某个页面,使用了redis的Hashtable,field存shopid,真的蠢了,应该用bitmap