概述
算法
原理
布隆过滤器优点
布隆过滤器缺点
GO实现
roaring
- Bitmap">
  type Bitmap
- 例子：
bloom
- Functions
- BloomFilter">
  type BloomFilter

概述

布隆过滤器(Bloom Filter)是1970年由布隆提出的。它实际上是一个很长的二进制向量和一系列随机映射函数，布隆过滤器可以用于检索一个元素是否在一个集合中。

如果想要判断一个元素是不是在一个集合里，一般想到的是将所有元素保存起来，然后通过比较确定。链表，树等等数据结构都是这种思路. 但是随着集合中元素的增加，我们需要的存储空间越来越大，检索速度也越来越慢(O(n),O(logn))。不过还有一种叫作散列表(又叫哈希表，Hash table)的数据结构，它可以通过一个Hash函数将一个元素映射成一个位阵列中的一个点，这样一来，我们只要看看这个点是不是1就可以知道集合中有没有它了。这就是布隆过滤器的基本思想。

算法

1、首先需要k个hash函数，每个函数可以把key散列成为1个整数；
2、初始化时，需要一个长度为n比特的数组，每个比特位初始化为0；
3、某个key加入集合时，用k个hash函数计算出k个散列值，并把数组中对应的比特位置为1；
4、判断某个key是否在集合时，用k个hash函数计算出k个散列值，并查询数组中对应的比特位，如果所有的比特位都是1，认为在集合中；

原理

布隆过滤器需要的是一个位数组(这个和位图有点类似)和k个映射函数(和Hash表类似)，在初始状态时，对于长度为m的位数组array，它的所有位都被置为0，如下图所示：

对于有n个元素的集合S={s1,s2……sn}，通过k个映射函数{f1,f2,……fk}，将集合S中的每个元素sj(1<=j<=n)映射为k个值{g1,g2……gk}，然后再将位数组array中相对应的array[g1],array[g2]……array[gk]置为1：

如果要查找某个元素item是否在S中，则通过映射函数{f1,f2…..fk}得到k个值{g1,g2…..gk}，然后再判断array[g1],array[g2]……array[gk]是否都为1，若全为1，则item在S中，否则item不在S中。这个就是布隆过滤器的实现原理。

布隆过滤器优点

它的优点是空间效率和查询时间都远远超过一般的算法，布隆过滤器存储空间和插入 / 查询时间都是常数O(k)。另外, 散列函数相互之间没有关系，方便由硬件并行实现。布隆过滤器不需要存储元素本身，在某些对保密要求非常严格的场合有优势。

布隆过滤器缺点

但是布隆过滤器的缺点和优点一样明显。误算率是其中之一。随着存入的元素数量增加，误算率随之增加。但是如果元素数量太少，则使用散列表足矣。
另外，一般情况下不能从布隆过滤器中删除元素. 我们很容易想到把位数组变成整数数组，每插入一个元素相应的计数器加 1, 这样删除元素时将计数器减掉就可以了。然而要保证安全地删除元素并非如此简单。首先我们必须保证删除的元素的确在布隆过滤器里面. 这一点单凭这个过滤器是无法保证的。另外计数器回绕也会造成问题

GO实现

package main
import (
    "fmt"
    "hash/fnv"
    "github.com/RoaringBitmap/roaring"
)
const DEFAULT_SIZE = 2 << 24
type BloomFilter struct {
    Set   *roaring.Bitmap
    Funcs [6]SimpleHash
}
func NewBloomFilter() *BloomFilter {
    bf := new(BloomFilter)
    for i := 0; i < len(bf.Funcs); i++ {
        bf.Funcs[i] = SimpleHash{seed: i + 1}
    }
    bf.Set = roaring.New()
    return bf
}
func (bf *BloomFilter) Add(value string) {
    for _, f := range bf.Funcs {
        bf.Set.AddInt(f.hash(value))
    }
}
func (bf *BloomFilter) Contains(value string) bool {
    if value == "" {
        return false
    }
    ret := true
    for _, f := range bf.Funcs {
        ret = ret && bf.Set.ContainsInt(f.hash(value))
    }
    return ret
}
type SimpleHash struct {
    seed int
}
// 这个hash不够随机
// 可以hash 字符串前n个字段，后n个字段，这样就随机化多了
func (s *SimpleHash) hash(value string) int {
    h := fnv.New32a()
    _, _ = h.Write([]byte(value))
    res := int(h.Sum32()) * s.seed
    return res
}
func main() {
    filter := NewBloomFilter()
    str1 := "hello,bloom filter!"
    filter.Add(str1)
    str2 := "A happy day"
    filter.Add(str2)
    str3 := "Greate wall"
    filter.Add(str3)
    fmt.Println(filter.Set.GetSizeInBytes())
    fmt.Println(filter.Contains(str1))
    fmt.Println(filter.Contains(str2))
    fmt.Println(filter.Contains(str3))
    fmt.Println(filter.Contains("blockchain technology"))
}
// output
11
80
true
true
true
false

roaring

这是一个具备压缩功能的bitmap
文档：https://pkg.go.dev/github.com/RoaringBitmap/roaring

type Bitmap

Bitmap表示可以添加整数的压缩位图

type Bitmap struct {
    // contains filtered or unexported fields
}
// AddOffset将offset值添加到位图的每个值上，在这个过程中生成一个新的位图
func AddOffset(x *Bitmap, offset uint32) (answer *Bitmap)
// AddOffset64将offset值添加到位图的每个值上，在这个过程中生成一个新的位图
// 如果offset +元素超出了[0,2^32)的范围，该元素将被删除
func AddOffset64(x *Bitmap, offset int64) (answer *Bitmap)
// 计算两个位图之间的交集并返回结果
func And(x1, x2 *Bitmap) *Bitmap
// AndNot计算两个位图之间的差并返回结果
func AndNot(x1, x2 *Bitmap) *Bitmap
// BitmapOf生成一个新的位图，填充指定的整数
func BitmapOf(dat ...uint32) *Bitmap
// And的快速方法
func FastAnd(bitmaps ...*Bitmap) *Bitmap
// Or的快速方法
func FastOr(bitmaps ...*Bitmap) *Bitmap
// 翻转指定范围内的位，1变0，0变1
func Flip(bm *Bitmap, rangeStart, rangeEnd uint64) *Bitmap
// 翻转指定范围内的位，1变0，0变1
func FlipInt(bm *Bitmap, rangeStart, rangeEnd int) *Bitmap
// Or计算两个位图之间的交集并返回结果
func Or(x1, x2 *Bitmap) *Bitmap
// HeapOr使用堆快速计算多个位图之间的并集
func HeapOr(bitmaps ...*Bitmap) *Bitmap
// Xor计算许位图之间的对称差集
func Xor(x1, x2 *Bitmap) *Bitmap
// HeapXor快速计算许多位图之间的对称差集
func HeapXor(bitmaps ...*Bitmap) *Bitmap
// 下面几个Par方法是并行的计算
func ParAnd(parallelism int, bitmaps ...*Bitmap) *Bitmap
func ParHeapOr(parallelism int, bitmaps ...*Bitmap) *Bitmap
func ParOr(parallelism int, bitmaps ...*Bitmap) *Bitmap
func New() *Bitmap
func NewBitmap() *Bitmap
func (rb *Bitmap) Remove(x uint32)
func (rb *Bitmap) RemoveRange(rangeStart, rangeEnd uint64)
func (rb *Bitmap) Add(x uint32)
func (rb *Bitmap) AddInt(x int) // 将x转为uint32再调用Add
func (rb *Bitmap) AddMany(dat []uint32)
func (rb *Bitmap) AddRange(rangeStart, rangeEnd uint64)
func (rb *Bitmap) And(x2 *Bitmap)
func (x1 *Bitmap) AndAny(bitmaps ...*Bitmap)
func (rb *Bitmap) AndCardinality(x2 *Bitmap) uint64 // 返回相交基数
func (rb *Bitmap) AndNot(x2 *Bitmap)
func (rb *Bitmap) Or(x2 *Bitmap)
func (rb *Bitmap) OrCardinality(x2 *Bitmap) uint64
func (rb *Bitmap) Xor(x2 *Bitmap)
func (rb *Bitmap) CheckedAdd(x uint32) bool  // 添加成功返回true
func (rb *Bitmap) CheckedRemove(x uint32) bool // 移除成功返回true
func (rb *Bitmap) Clear()
func (rb *Bitmap) Clone() *Bitmap
func (rb *Bitmap) Contains(x uint32) bool
func (rb *Bitmap) ContainsInt(x int) bool
func (rb *Bitmap) Flip(rangeStart, rangeEnd uint64)
func (rb *Bitmap) GetCardinality() uint64  // 返回整数数量
//  GetCopyOnWrite获取位图的“写时拷贝”属性
func (rb *Bitmap) GetCopyOnWrite() (val bool)
func (rb *Bitmap) SetCopyOnWrite(val bool)  // 设置“写时拷贝”属性
// GetSerializedSizeInBytes以字节为单位计算位图的序列化大小。
// 它应该对应于调用WriteTo时写入的字节数。
func (rb *Bitmap) GetSerializedSizeInBytes() uint64
// GetSizeInBytes估计位图的内存使用情况。
func (rb *Bitmap) GetSizeInBytes() uint64
// 如果位图从运行压缩中受益，HasRunCompression返回true
func (rb *Bitmap) HasRunCompression() bool
func (rb *Bitmap) Intersects(x2 *Bitmap) bool // 检查两个位图是否相交
// 果位图为空，IsEmpty返回true(比(GetCardinality() == 0)更快)
func (rb *Bitmap) IsEmpty() bool
func (rb *Bitmap) Iterator() IntPeekable
func (rb *Bitmap) ManyIterator() ManyIntIterable
func (rb *Bitmap) MarshalBinary() ([]byte, error)
func (rb *Bitmap) Maximum() uint32
func (rb *Bitmap) Minimum() uint32
func (rb *Bitmap) RunOptimize()  // 执行压缩
func (rb *Bitmap) String() string
func (rb *Bitmap) ToArray() []uint32
func (rb *Bitmap) ToBase64() (string, error)
func (rb *Bitmap) ToBytes() ([]byte, error)
func (rb *Bitmap) UnmarshalBinary(data []byte) error
func (rb *Bitmap) WriteTo(stream io.Writer) (int64, error)

例子：

package main
import (
    "bytes"
    "fmt"
    "github.com/RoaringBitmap/roaring"
)
func main() {
    rb1 := roaring.BitmapOf(1, 2, 3, 4, 5, 100, 1000)
    fmt.Println(rb1.String()) // {1,2,3,4,5,100,1000}
    rb2 := roaring.BitmapOf(3, 4, 1000)
    fmt.Println(rb2.String()) //{3,4,1000}
    rb3 := roaring.New()
    fmt.Println(rb3.String()) //{}
    fmt.Println("Cardinality: ", rb1.GetCardinality()) // Cardinality:  7
    fmt.Println("Contains 3? ", rb1.Contains(3)) // Contains 3?  true
    rb1.And(rb2)
    rb3.Add(1)
    rb3.Add(5)
    rb3.Or(rb1)
    // computes union of the three bitmaps in parallel using 4 workers
    roaring.ParOr(4, rb1, rb2, rb3)
    // computes intersection of the three bitmaps in parallel using 4 workers
    roaring.ParAnd(4, rb1, rb2, rb3)
    // prints 1, 3, 4, 5, 1000
    i := rb3.Iterator()
    for i.HasNext() {
        fmt.Println(i.Next()) // 1,3,4,5,1000
    }
    fmt.Println()
    // next we include an example of serialization
    buf := new(bytes.Buffer)
    rb1.WriteTo(buf) // we omit error handling
    newrb := roaring.New()
    newrb.ReadFrom(buf)
    if rb1.Equals(newrb) { // true
        fmt.Println("I wrote the content to a byte stream and read it back.")
    }
}

bloom

文档：https://pkg.go.dev/github.com/bits-and-blooms/bloom

Functions

// 当存储数量为n，误判率为p时，预估散列大小m与所需的hash函数数
func EstimateParameters(n uint, p float64) (m uint, k uint)
// 返回data在散列中的位置
func Locations(data []byte, k uint) []uint64

type BloomFilter

// From创建了一个新的Bloom过滤器，带有len(_data_) * 64位和_k_哈希函数。数据片不会被重置。
func From(data []uint64, k uint) *BloomFilter
// m为长度，k为hash函数个数
func New(m uint, k uint) *BloomFilter
// n为存储数据量个数，fp为误判率
func NewWithEstimates(n uint, fp float64) *BloomFilter
func (f *BloomFilter) Add(data []byte) *BloomFilter
func (f *BloomFilter) AddString(data string) *BloomFilter
func (f *BloomFilter) Cap() uint // 返回容量m
func (f *BloomFilter) ClearAll() *BloomFilter
func (f *BloomFilter) Copy() *BloomFilter
func (f *BloomFilter) Equal(g *BloomFilter) bool
func (f *BloomFilter) GobDecode(data []byte) error
func (f *BloomFilter) GobEncode() ([]byte, error)
func (f *BloomFilter) K() uint // hash函数个数
func (f *BloomFilter) MarshalJSON() ([]byte, error)
func (f *BloomFilter) UnmarshalJSON(data []byte) error
func (f *BloomFilter) Merge(g *BloomFilter) error
func (f *BloomFilter) ReadFrom(stream io.Reader) (int64, error)
func (f *BloomFilter) WriteTo(stream io.Writer) (int64, error)
func (f *BloomFilter) Test(data []byte) bool
func (f *BloomFilter) TestAndAdd(data []byte) bool
func (f *BloomFilter) TestString(data string) bool
func (f *BloomFilter) TestAndAddString(data string) bool
// BloomFilter是否设置了locs包含的所有位置
func (f *BloomFilter) TestLocations(locs []uint64) bool