前言

我最近閱讀了 Alex Xu 寫的 System Design Interview – An insider’s guide，在如何設計網路爬蟲的章節看到可以用 Bloom Filter 追蹤已經造訪過的網址。以前沒有聽過這個演算法。

原理

在實作 Bloom Filter 時，會先建立一個長度為集合元素數量的 boolean 陣列。在加入元素時，以 Hash function 處理元素，再以 Hash value 為 index 將陣列內 boolean 值設為 true。

在檢查元素是否存在時，以 Hash function 處理元素，再檢查陣列內 boolean 值是否為 true。

但是 Hash function 無法保證不會產生重複的 Hash value，所以不同元素有機會將陣列內相同 index 的 boolean 值設為 true。

也就是說，當回傳的 boolean 值為 true 時，不保證元素真的存在。當 boolean 值為 false 時，元素保證真的不存在。

並且也有難以刪除元素的問題。

以 Go 實作簡單的 Bloom Filter

建立一個 boolean 陣列及一個 Hash function

type filter struct {
	bitfield [10]bool
}

var hasher = sha1.New()

將 string 轉為 hash

func createHash(h hash.Hash, input string) int {
	bits := h.Sum([]byte(input))
	buffer := bytes.NewBuffer(bits)
	result, _ := binary.ReadVarint(buffer)
	return int(result)
}

將產生的 hash 對應到 boolean 陣列

為了避免產生的 hash 超出 bitfield 陣列長度，需要以陣列長度取餘數。

func (f *filter) hashPosition(s string) int {
	hs := createHash(hasher, s)
	if hs < 0 {
		hs = -hs
	}
	return hs % len(f.bitfield)
}

建立 Set 及 Get 方法

Set 可以將元素加入 Bloom Filter，Get 可以檢查元素是否存在。

func (f *filter) Set(s string) {
	pos := f.hashPosition(s)
	f.bitfield[pos] = true
}
func (f *filter) Get(s string) bool {
	return f.bitfield[f.hashPosition(s)]
}

使用

func main() {
	f := filter{}
	f.Set("hello")
	fmt.Printf("%#v\n", f.bitfield)
	fmt.Println(f.Get("hello"))
}

$ go run .
[10]bool{false, false, true, false, false, false, false, false, false, false}

範例程式碼

https://github.com/yslinear/go-bloom-filter

參考資料