布隆过滤器介绍

判断目标值是否在一个汇合中是比拟常见的业务场景。在Go语言中通常应用map来实现给性能。然而当汇合比拟大时，应用map会耗费大量的内存。 这种状况下可应用BitMap来代替map。BitMap尽管可能在肯定状况下缩小的内存的耗费，然而BitMap也存在以下局限性：

  • 当样本分布极度不平均的时候，BitMap会造成很大空间上的节约。
    若数据的类型Int64，并且数据分布的跨度比拟大，则也无奈满足对内存的要求。
  • 当元素不是整型的时候，BitMap就不实用了。
    BitMap只能保留整形数据，对于字符串类型的数据则不适合应用。

BitMap只能解决整形数据，对于字符串则不能说实用。若可能把字符串映射为整形，就能够应用BitMap来存储字符串的状态了。 hash函数能够将字符串映射为整形数据，然而hash函数映射为整形是存在hash抵触。为了缩小hash抵触，能够应用多个hash函数来将一个字符串映射为多个整数，并将映射后的整数存在BitMap中。在查问字符串时，应用同样的hash函数来计算hash值，并应用同样的hash值来查问BitMap，若其中有一个hash值没有命中，则该url不存在。

上述思路就是布隆过滤器的外围思路。布隆过滤器是由布隆（Burton Howard Bloom）在1970年提出的，它实际上是由一个很长的二进制向量和一系列随机映射函数组成，布隆过滤器能够用于检索一个元素是否在一个汇合中。它的长处是空间效率和查问工夫都远远超过个别的算法，毛病是有肯定的误识别率:即布隆过滤器报告某个值存在于BitMap中中，然而实际上该值可能并不在汇合中。然而布隆过滤器若报告某个值不在BitMap中，则该值必定不在汇合中。

缩小布隆过滤器误识别率的办法
布隆过滤器误辨认的起因在于hash抵触，因而缩小hash抵触能够升高布隆过滤器误识别率。hash抵触和BitMap数组的大小以及hash函数的个数以及每个hash函数自身的好坏无关。能够采纳以下办法升高hash抵触的概率：

  • 多个hash，增大随机性，缩小hash碰撞的概率。
  • 扩充数组范畴，使hash值均匀分布，进一步缩小hash碰撞的概率。

布隆过滤器的Go语言实现

接下来咱们给出布隆过滤器的Go语言实现，目前代码曾经上传到github中，下载地址

定义

首先给出布隆过滤器构造的定义：

type BloomFilter struct {    bset *BitMap    size uint}

其中：

  • BitMap的实现在bitmap.go文件中
  • size是BitMap二进制位的数量

创立BloomFilter构造

func NewBloomFilter(size_val ...uint) *BloomFilter {    var size uint = 1024*1024    if len(size_val) > 0 && size_val[0] > 0 {        size = size_val[0]    }    bf := &BloomFilter{}    bf.bset = NewBitMap(size)    bf.size = size    return bf}

BloomFilter应用的hash函数

var seeds = []uint{3011, 3017, 3031}func (bf *BloomFilter)hashFun(seed uint, value string) uint64 {    hash := uint64(seed)    for i := 0; i < len(value); i++ {        hash = hash*33 + uint64(value[i])    }    return hash}

将数据增加到BloomFilter

func (bf *BloomFilter)Set(value string) {    for _, seed := range seeds {        hash := bf.hashFun(seed, value)        hash = hash % uint64(bf.size)        bf.bset.Set(uint(hash))    }}

判断元素是否存在

func (bf *BloomFilter)Check(value string) bool {    for _, seed := range seeds {        hash := bf.hashFun(seed, value)        hash = hash % uint64(bf.size)        ret := bf.bset.Check(uint(hash))        if !ret {            return false        }    }    return true}