Bloom Filter 概念

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

Bloom Filter 原理

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

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

緩存穿透

每次查詢都會(huì)直接打到DB

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

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

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

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

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

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

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

Bloom Filter的缺點(diǎn)

bloom filter之所以能做到在時(shí)間和空間上的效率比較高，是因?yàn)闋奚伺袛嗟臏?zhǔn)確率、刪除的便利性

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

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

常見問題

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

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

go語言實(shí)現(xiàn)

package main
import (
	"fmt"
	"github.com/bits-and-blooms/bitset"
)
//設(shè)置哈希數(shù)組默認(rèn)大小為16
const DefaultSize = 16
//設(shè)置種子，保證不同哈希函數(shù)有不同的計(jì)算方式
var seeds = []uint{7, 11, 13, 31, 37, 61}
//布隆過濾器結(jié)構(gòu)，包括二進(jìn)制數(shù)組和多個(gè)哈希函數(shù)
type BloomFilter struct {
	//使用第三方庫
	set *bitset.BitSet
	//指定長度為6
	hashFuncs [6]func(seed uint, value string) uint
}
//構(gòu)造一個(gè)布隆過濾器，包括數(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個(gè)哈希函數(shù)，每個(gè)哈希函數(shù)有參數(shù)seed保證計(jì)算方式的不同
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 時(shí)，X % length = X & (length - 1)
		return result & (DefaultSize - 1)
	}
}
//添加元素
func (b *BloomFilter) add(value string) {
	for i, f := range b.hashFuncs {
		//將哈希函數(shù)計(jì)算結(jié)果對(duì)應(yīng)的數(shù)組位置1
		b.set.Set(f(seeds[i], value))
	}
}
//判斷元素是否存在
func (b *BloomFilter) contains(value string) bool {
	//調(diào)用每個(gè)哈希函數(shù)，并且判斷數(shù)組對(duì)應(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