乐趣区

关于golang:布隆过滤器的原理以及Go语言实现

jiezi

布隆过滤器介绍

判断目标值是否在一个汇合中是比拟常见的业务场景。在 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
}
退出移动版