Redis?BloomFilter布隆過濾器如何實現

這篇文章主要介紹“Redis BloomFilter布隆過濾器如何實現”，在日常操作中，相信很多人在Redis BloomFilter布隆過濾器如何實現問題上存在疑惑，小編查閱了各式資料，整理出簡單好用的操作方法，希望對大家解答”Redis BloomFilter布隆過濾器如何實現”的疑惑有所幫助！接下來，請跟著小編一起來學習吧！

Bloom Filter 概念

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

Bloom Filter 原理

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

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

緩存穿透

每次查詢都會直接打到DB

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

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

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

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

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

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

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

Bloom Filter的缺點

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

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

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

常見問題

1、為何要使用多個哈希函數？

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

go語言實現

package main
import (
	"fmt"
	"github.com/bits-and-blooms/bitset"
)
//設置哈希數組默認大小為16
const DefaultSize = 16
//設置種子，保證不同哈希函數有不同的計算方式
var seeds = []uint{7, 11, 13, 31, 37, 61}
//布隆過濾器結構，包括二進制數組和多個哈希函數
type BloomFilter struct {
	//使用第三方庫
	set *bitset.BitSet
	//指定長度為6
	hashFuncs [6]func(seed uint, value string) uint
}
//構造一個布隆過濾器，包括數組和哈希函數的初始化
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
}
//構造6個哈希函數，每個哈希函數有參數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 {
		//將哈希函數計算結果對應的數組位置1
		b.set.Set(f(seeds[i], value))
	}
}
//判斷元素是否存在
func (b *BloomFilter) contains(value string) bool {
	//調用每個哈希函數，并且判斷數組對應位是否為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"))
}

輸出結果如下：

true
false
false

到此，關于“Redis BloomFilter布隆過濾器如何實現”的學習就結束了，希望能夠解決大家的疑惑。理論與實踐的搭配能更好的幫助大家學習，快去試試吧！若想繼續學習更多相關知識，請繼續關注億速云網站，小編會繼續努力為大家帶來更多實用的文章！