Bloom Filter 概念

布隆過濾器（英語：Bloom Filter）是1970年由一個叫布隆的小伙子提出的。它實際上是一個很長的二進制向量和一系列隨機映射函數(shù)。布隆過濾器可以用于檢索一個元素是否在一個集合中。它的優(yōu)點是空間效率和查詢時間都遠遠超過一般的算法，缺點是有一定的誤識別率和刪除困難。

Bloom Filter 原理

布隆過濾器的原理是，當(dāng)一個元素被加入集合時，通過K個散列函數(shù)將這個元素映射成一個位數(shù)組中的K個點，把它們置為1。檢索時，我們只要看看這些點是不是都是1就（大約）知道集合中有沒有它了：如果這些點有任何一個0，則被檢元素一定不在；如果都是1，則被檢元素很可能在。這就是布隆過濾器的基本思想。

Bloom Filter跟單哈希函數(shù)Bit-Map不同之處在于：Bloom Filter使用了k個哈希函數(shù)，每個字符串跟k個bit對應(yīng)。從而降低了沖突的概率

緩存穿透

每次查詢都會直接打到DB

簡而言之，言而簡之就是我們先把我們數(shù)據(jù)庫的數(shù)據(jù)都加載到我們的過濾器中，比如數(shù)據(jù)庫的id現(xiàn)在有：1、2、3

那就用id：1 為例子他在上圖中經(jīng)過三次hash之后，把三次原本值0的地方改為1

下次數(shù)據(jù)進來查詢的時候如果id的值是1，那么我就把1拿去三次hash 發(fā)現(xiàn)三次hash的值，跟上面的三個位置完全一樣，那就能證明過濾器中有1的

反之如果不一樣就說明不存在了

那應(yīng)用的場景在哪里呢？一般我們都會用來防止緩存擊穿

簡單來說就是你數(shù)據(jù)庫的id都是1開始然后自增的，那我知道你接口是通過id查詢的，我就拿負數(shù)去查詢，這個時候，會發(fā)現(xiàn)緩存里面沒這個數(shù)據(jù)，我又去數(shù)據(jù)庫查也沒有，一個請求這樣，100個，1000個，10000個呢？你的DB基本上就扛不住了，如果在緩存里面加上這個，是不是就不存在了，你判斷沒這個數(shù)據(jù)就不去查了，直接return一個數(shù)據(jù)為空不就好了嘛。

這玩意這么好使那有啥缺點么？有的，我們接著往下看

Bloom Filter的缺點

bloom filter之所以能做到在時間和空間上的效率比較高，是因為犧牲了判斷的準確率、刪除的便利性

存在誤判，可能要查到的元素并沒有在容器中，但是hash之后得到的k個位置上值都是1。如果bloom filter中存儲的是黑名單，那么可以通過建立一個白名單來存儲可能會誤判的元素。

刪除困難。一個放入容器的元素映射到bit數(shù)組的k個位置上是1，刪除的時候不能簡單的直接置為0，可能會影響其他元素的判斷。可以采用Counting Bloom Filter

常見問題

1、為何要使用多個哈希函數(shù)？

Hash本身就會面臨沖突，如果只使用一個哈希函數(shù)，那么沖突的概率會比較高。例如長度100的數(shù)組，如果只使用一個哈希函數(shù)，添加一個元素后，添加第二個元素時沖突的概率為1%，添加第三個元素時沖突的概率為2%…但如果使用兩個哈希函數(shù)，添加一個元素后，添加第二個元素時沖突的概率降為萬分之4（四種可能的沖突情況，情況總數(shù)100x100）

go語言實現(xiàn)

package main
import (
	"fmt"
	"github.com/bits-and-blooms/bitset"
)
//設(shè)置哈希數(shù)組默認大小為16
const DefaultSize = 16
//設(shè)置種子，保證不同哈希函數(shù)有不同的計算方式
var seeds = []uint{7, 11, 13, 31, 37, 61}
//布隆過濾器結(jié)構(gòu)，包括二進制數(shù)組和多個哈希函數(shù)
type BloomFilter struct {
	//使用第三方庫
	set *bitset.BitSet
	//指定長度為6
	hashFuncs [6]func(seed uint, value string) uint
}
//構(gòu)造一個布隆過濾器，包括數(shù)組和哈希函數(shù)的初始化
func NewBloomFilter() *BloomFilter {
	bf := new(BloomFilter)
	bf.set = bitset.New(DefaultSize)

	for i := 0; i < len(bf.hashFuncs); i++ {
		bf.hashFuncs[i] = createHash()
	}
	return bf
}
//構(gòu)造6個哈希函數(shù)，每個哈希函數(shù)有參數(shù)seed保證計算方式的不同
func createHash() func(seed uint, value string) uint {
	return func(seed uint, value string) uint {
		var result uint = 0
		for i := 0; i < len(value); i++ {
			result = result*seed + uint(value[i])
		}
		//length = 2^n 時，X % length = X & (length - 1)
		return result & (DefaultSize - 1)
	}
}
//添加元素
func (b *BloomFilter) add(value string) {
	for i, f := range b.hashFuncs {
		//將哈希函數(shù)計算結(jié)果對應(yīng)的數(shù)組位置1
		b.set.Set(f(seeds[i], value))
	}
}
//判斷元素是否存在
func (b *BloomFilter) contains(value string) bool {
	//調(diào)用每個哈希函數(shù)，并且判斷數(shù)組對應(yīng)位是否為1
	//如果不為1，直接返回false，表明一定不存在
	for i, f := range b.hashFuncs {
		//result = result && b.set.Test(f(seeds[i], value))
		if !b.set.Test(f(seeds[i], value)) {
			return false
		}
	}
	return true
}
func main() {
	filter := NewBloomFilter()
	filter.add("asd")
	fmt.Println(filter.contains("asd"))
	fmt.Println(filter.contains("2222"))
	fmt.Println(filter.contains("155343"))
}

輸出結(jié)果如下：

true
false
false

到此這篇關(guān)于Redis BloomFilter布隆過濾器原理與實現(xiàn)的文章就介紹到這了,更多相關(guān)Redis BloomFilter內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

最新評論