Bloom Filter

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

上一篇:布隆过滤器(Bloom Filter)


下一篇:机器学习数据集