go语言实现布隆过滤器

概念与使用场景

概念：布隆过滤器（Bloom Filter）由Burton Howard Bloom在1970年提出，用于测试一个元素是否在一个集合中。这种数据结构的特点是空间效率高且查询速度快，但有一定的误报率，并且不支持从集合中删除元素。

使用场景：

爬虫去重：在网络爬虫中，可以用来检测URL是否已经被抓取过，从而避免重复抓取相同的页面。
黑名单：用于快速判断某个IP地址、URL等是否在黑名单中。
防止（Redis）缓存穿透：当有新的key请求时，先通过布隆过滤器检查这个key是否存在。如果不存在则直接返回，不再查询数据库；当然也可以设置其他的处理方式，比如返回默认值或缓存预热。

工作原理

组成：一个很长的二进制向量（Bitmap，也称为位图），以及多个独立的哈希函数。
插入操作：当一个元素被添加到布隆过滤器时，多个哈希函数会被应用到这个元素上，每个哈希函数会产生一个索引，指示位图中的某个位置，对应这些位置的比特位会被设置为1。
查询操作：查询一个元素是否存在时，同样使用相同的哈希函数来计算位图中的位置。如果所有位置上的比特位都是1，则认为该元素可能存在于集合中，如果有任何一个位置的比特位是0，则确定该元素不在集合中。

特性

优点：

极大地节省了存储空间。
查询速度非常快。

缺点：

如果一个元素经多个哈希函数计算出的比特位都是1，就会导致错误地报告一个元素存在于集合中。
误报率随插入元素的数量增加。
不支持删除元素。

具体实现（go语言）

创建一个布隆过滤器的结构体，包含位图、位图长度、哈希种子。可自行确定 hashNum（哈希函数的个数）和 bitCount（位图的长度）参数。
因为go语言最小的类型为byte，位图只能用 byte 切片表示，因此 byte 切片的长度为 bitCount / 8。
进行插入和查询操作时，设经过一次哈希运算后得到的 Bitmap 下标为 index ，index / 8 为 index 在 byte 切片中的位置，index % 8 为 index 在该位置中的偏移量。
哈希函数使用 github.com/dgryski/go-farm 库的 farm.Hash32WithSeed 函数。

实现代码：

import (
    "bufio"
    "encoding/gob"
    "github.com/dgryski/go-farm"
    "math/rand"
    "os"
)

type BloomFilter struct {
    BitMap   []byte
    BitCount int
    Seeds    []uint32
}

// NewBloomFilter
// hashNum为哈希函数的个数,
// bitCount为bitmap的长度
func NewBloomFilter(hashNum, bitCount int) *BloomFilter {
    size := bitCount / 8
    seeds := make([]uint32, hashNum)
    for i := 0; i < hashNum; i++ {
        seeds[i] = uint32(rand.Int())
    }
    return &BloomFilter{
        BitMap:   make([]byte, size),
        BitCount: bitCount,
        Seeds:    seeds,
    }
}

func (bf *BloomFilter) getBit(index uint32) bool {
    a := index / 8
    v := uint(bf.BitMap[a])
    b := uint(1 << (index % 8))
    return v&b == b
}

func (bf *BloomFilter) setBit(index uint32) {
    bf.BitMap[index/8] |= 1 << (index % 8)
}

func (bf *BloomFilter) Add(elem string) {
    for _, seed := range bf.Seeds {
        index := farm.Hash32WithSeed([]byte(elem), seed) % uint32(bf.BitCount)
        bf.setBit(index)
    }
}

func (bf *BloomFilter) Exists(elem string) bool {
    for _, seed := range bf.Seeds {
  index := farm.Hash32WithSeed([]byte(elem), seed) % uint32(bf.BitCount)
        //fmt.Println(index)
        if !bf.getBit(index) {
            return false
        }
    }
    return true
}

// 把布隆过滤器导出到文件
func (bf *BloomFilter) Export(file string) error {
    fout, err := os.OpenFile(file, os.O_CREATE|os.O_WRONLY|os.O_TRUNC, 0o666)
    if err != nil {
        return err
    }
    defer fout.Close()
    writer := bufio.NewWriter(fout)
    defer writer.Flush()
    encoder := gob.NewEncoder(writer)
    return encoder.Encode(*bf)
}

func LoadBloomFilter(file string) (*BloomFilter, error) {
    fin, err := os.Open(file)
    if err != nil {
        return nil, err
    }
    defer fin.Close()
    reader := bufio.NewReader(fin)
    decoder := gob.NewDecoder(reader)
    var bf BloomFilter
    err = decoder.Decode(&bf)
    if err != nil {
        return nil, err
    }
    return &bf, nil
}

附：初始化布隆过滤器时，应该仔细斟酌开辟的空间，以及哈希函数的数量。一般初始化可以开辟10MB的左右的位图空间，使用8到10个哈希函数，这样最大可以存储接近1百万个左右的元素，并且保持较小的误报率。