目錄
- 1. 布隆過濾器的概念
- 2. 布隆過濾器應用場景
- 3. 布隆過濾器作業原理
- 4. 布隆過濾器的優缺點
- 5. 布隆過濾器注意事項
- 6. Go實作布隆過濾器
1. 布隆過濾器的概念
布隆過濾器（Bloom Filter） 是由 Howard Bloom在1970年提出的二進制向量資料結構，它具有很好的空間和時間效率，被用來檢測一個元素是不是集合中的一個成員，即判定 “可能已存在和絕對不存在” 兩種情況，如果檢測結果為是，該元素不一定在集合中；但如果檢測結果為否，該元素一定不在集合中,因此Bloom filter具有100%的召回率，
2. 布隆過濾器應用場景
- 垃圾郵件過濾
- 防止快取擊穿
- 位元幣交易查詢
- 爬蟲的URL過濾
- IP黑名單
- 查詢加速【比如基于KV結構的資料】
- 集合元素重復的判斷
3. 布隆過濾器作業原理
布隆過濾器的核心是一個超大的位陣列和幾個哈希函式，假設位陣列的長度為m,哈希函式的個數為k，
下圖表示有三個hash函式，比如一個集合中有x，y，z三個元素，分別用三個hash函式映射到二進制序列的某些位上，假設我們判斷w是否在集合中，同樣用三個hash函式來映射，結果發現取得的結果不全為1，則表示w不在集合里面，
作業流程:
- 第一步：開辟空間：
開辟一個長度為m的位陣列（或者稱二進制向量），這個不同的語言有不同的實作方式，甚至你可以用檔案來實作， - 第二步：尋找hash函式
獲取幾個hash函式，前輩們已經發明了很多運行良好的hash函式，比如BKDRHash，JSHash，RSHash等等，這些hash函式我們直接獲取就可以了， - 第三步：寫入資料
將所需要判斷的內容經過這些hash函式計算，得到幾個值，比如用3個hash函式，得到值分別是1000，2000，3000，之后設定m位陣列的第1000，2000，3000位的值位二進制1， - 第四步：判斷
接下來就可以判斷一個新的內容是不是在我們的集合中，判斷的流程和寫入的流程是一致的，
4. 布隆過濾器的優缺點
1、優點：
- 有很好的
空間和時間效率 存盤空間和插入/查詢時間都是常數，- Hash函式相互之間沒有關系，方便由硬體并行實作，
- 不需要存盤元素本身，在某些對保密要求非常嚴格的場合有優勢，
- 布隆過濾器可以表示
全集，其它任何資料結構都不能，
2、缺點：
誤判率會隨元素的增加而增加不能從布隆過濾器中洗掉元素
5. 布隆過濾器注意事項
布隆過濾器思路比較簡單，但是對于布隆過濾器的隨機映射函式設計，需要計算幾次，向量長度設定為多少比較合適，這個才是需要認真討論的，
如果向量長度太短，會導致誤判率直線上升，
如果向量太長，會浪費大量記憶體，
如果計算次數過多，會占用計算資源，且很容易很快就把過濾器填滿，
6. Go實作布隆過濾器
1. 開源包簡單演示
package main
import (
"fmt"
"github.com/willf/bitset"
"math/rand"
)
func main() {
Foo()
bar()
}
func Foo() {
var b bitset.BitSet // 定義一個BitSet物件
b.Set(1).Set(2).Set(3) //添加3個元素
if b.Test(2) {
fmt.Println("2已經存在")
}
fmt.Println("總數：", b.Count())
b.Clear(2)
if !b.Test(2) {
fmt.Println("2不存在")
}
fmt.Println("總數：", b.Count())
}
func bar() {
fmt.Printf("Hello from BitSet!\n")
var b bitset.BitSet
// play some Go Fish
for i := 0; i < 100; i++ {
card1 := uint(rand.Intn(52))
card2 := uint(rand.Intn(52))
b.Set(card1)
if b.Test(card2) {
fmt.Println("Go Fish!")
}
b.Clear(card1)
}
// Chaining
b.Set(10).Set(11)
for i, e := b.NextSet(0); e; i, e = b.NextSet(i + 1) {
fmt.Println("The following bit is set:", i)
}
// 交集
if b.Intersection(bitset.New(100).Set(10)).Count() == 1 {
fmt.Println("Intersection works.")
} else {
fmt.Println("Intersection doesn't work???")
}
}
2. 封裝的方法：
//----------------------------------------------------------------------------
// @ Copyright (C) free license,without warranty of any kind .
// @ Author: hollson <[email protected]>
// @ Date: 2019-12-06
// @ Version: 1.0.0
//------------------------------------------------------------------------------
package bloomx
import "github.com/willf/bitset"
const DEFAULT_SIZE = 2<<24
var seeds = []uint{7, 11, 13, 31, 37, 61}
type BloomFilter struct {
Set *bitset.BitSet
Funcs [6]SimpleHash
}
func NewBloomFilter() *BloomFilter {
bf := new(BloomFilter)
for i:=0;i< len(bf.Funcs);i++{
bf.Funcs[i] = SimpleHash{DEFAULT_SIZE,seeds[i]}
}
bf.Set = bitset.New(DEFAULT_SIZE)
return bf
}
func (bf BloomFilter) Add(value string){
for _,f:=range(bf.Funcs){
bf.Set.Set(f.hash(value))
}
}
func (bf BloomFilter) Contains(value string) bool {
if value =https://www.cnblogs.com/Hollson/p/= "" {
return false
}
ret := true
for _,f:=range(bf.Funcs){
ret = ret && bf.Set.Test(f.hash(value))
}
return ret
}
type SimpleHash struct{
Cap uint
Seed uint
}
func (s SimpleHash) hash(value string) uint{
var result uint = 0
for i:=0;i< len(value);i++{
result = result*s.Seed+uint(value[i])
}
return (s.Cap-1)&result
}
func main() {
filter := bloomx.NewBloomFilter()
fmt.Println(filter.Funcs[1].Seed)
str1 := "hello,bloom filter!"
filter.Add(str1)
str2 := "A happy day"
filter.Add(str2)
str3 := "Greate wall"
filter.Add(str3)
fmt.Println(filter.Set.Count())
fmt.Println(filter.Contains(str1))
fmt.Println(filter.Contains(str2))
fmt.Println(filter.Contains(str3))
fmt.Println(filter.Contains("blockchain technology"))
}
100W數量級下布隆過濾器測驗，原始碼可參考https://download.csdn.net/download/Gusand/12018239
參考：
推薦：https://www.cnblogs.com/z941030/p/9218356.html
https://www.jianshu.com/p/01309d298a0e
https://www.cnblogs.com/zengdan-develpoer/p/4425167.html
https://blog.csdn.net/liuzhijun301/article/details/83040178
https://github.com/willf/bloom
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/56924.html
標籤：Go
上一篇：CentOS7 如何升級Git
下一篇：搭建輕量級的本地git