Go 語言實現布隆過濾器

布隆過濾器簡介

布隆過濾器（Bloom Filter）是一個基於 hash 的概率性的數據結構，它實際上是一個很長的二進制向量，可以檢查一個元素可能存在集合中，和一定不存在集合中。它的優點是空間效率高，但是有一定 false positive(元素不在集合中，但是布隆過濾器顯示在集合中)。

布隆過濾器原理

布隆過濾器就是一個長度爲m個 bit 的 bit 數組，初始的時候每個 bit 都是 0，另外還有k個 hash 函數。

 

布隆過濾器加入元素

當加入一個元素時，先用k個 hash 函數得到k個 hash 值，將k個 hash 值與 bit 數組長度取模得到個k個位置，將這k個位置對應的 bit 置位 1。

 

在加入了bloom之後，再加入filter。

 

布隆過濾器查詢元素

在布隆過濾器中查詢元素比較簡單，同樣地，先用k個 hash 函數得到k個 hash 值，將k個 hash 值與 bit 數組長度取模得到個k個位置，然後檢查這k個位置的 bit 是否是 1。如果都是 1，布隆過濾器返回這個原始存在。

 

布隆過濾器的 false positive

查詢元素中，有可能k個 hash 值對應的位置都已經置一，但這都是其他元素的操作，實際上這個元素並不在布隆過濾器中，這就是 false positive。看下面這個例子，添加完bloom,filter後，檢查cat是否在 布隆過濾器中。

 

實際上，cat並不在布隆過濾器中。所以說，布隆過濾器返回 true，元素不一定在其中；但是返回 false，元素一定不在布隆過濾器中。

布隆過濾器的 false positive 計算

false positive 計算，有 3 個重要的參數。1. m表示 bit 數組的長度 2. k表示散列函數的個數 3. n表示插入的元素個數

布隆過濾器中，一個元素插入後，某個 bit 爲 0 的概率是

(1−1/m)^k

n 元素插入後，某個 bit 爲 0 的概率是

(1−1/m)^(nk)

false positive 的概率是

(1−(1−1/m)^nk)^k

因爲需要的是k個不同的 bit 被設置成 1，概率是大約是

(1−e^(−kn/m))^k

這個就是 false positive 的概率

Golang 代碼實現

代碼實現在我的 github 倉庫。這個 Golang 實現，支持併發操作，批量加入byte數組，字符串，數字等。

bit 數組的大小選擇

代碼中，bit 數組表示成[]byte數組。由於後續在[]byte定位 hash 需要取餘操作，%操作是一個比較慢的操作，如果數組的長度是 2 的 n 次方，%可以被優化成& (2^n-1)。因此，New()函數初始化的時候，會將[]byte數組的長度拉長到2^n，加快計算。

type Filter struct {
    lock       *sync.RWMutex
    concurrent bool

    m     uint64 // bit array of m bits, m will be ceiling to power of 2
    n     uint64 // number of inserted elements
    log2m uint64 // log_2 of m
    k     uint64 // the number of hash function
    keys  []byte // byte array to store hash value
}

func New(size uint64, k uint64, race bool) *Filter {
    log2 := uint64(math.Ceil(math.Log2(float64(size))))
    filter := &Filter{
        m:          1 << log2,
        log2m:      log2,
        k:          k,
        keys:       make([]byte, 1<<log2),
        concurrent: race,
    }
    if filter.concurrent {
        filter.lock = &sync.RWMutex{}
    }
    return filter
}

// location returns the bit position in byte array
// & (f.m - 1) is the quick way for mod operation
func (f *Filter) location(h uint64) (uint64, uint64) {
    slot := (h / bitPerByte) & (f.m - 1)
    mod := h & mod7
    return slot, mod
}

hash 函數的選擇

因爲需要快速的操作，因此不選擇md5,sha等耗時比較久的 hash 操作。經過比較之後，我選擇使用murmur3的 hash 算法，來對 key 進行 hash。

// baseHash returns the murmur3 128-bit hash
func baseHash(data []byte) []uint64 {
    a1 := []byte{1} // to grab another bit of data
    hasher := murmur3.New128()
    hasher.Write(data) // #nosec
    v1, v2 := hasher.Sum128()
    hasher.Write(a1) // #nosec
    v3, v4 := hasher.Sum128()
    return []uint64{
        v1, v2, v3, v4,
    }
}

輸入一段元素的字節數組，將其 hash 值返回，計算出這個元素的位置。

轉自：

zhuanlan.zhihu.com/p/165130282

本文由 Readfog 進行 AMP 轉碼，版權歸原作者所有。
來源：https://mp.weixin.qq.com/s/OzPLMAaELP1KtBRrIeedBw

猜你喜歡