Redis BloomFilter布隆過濾器如何實現

Bloom Filter 概念

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

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之所以能做到在時間和空間上的效率比較高，是因為犧牲了判斷的準確率、刪除的便利性

儘管容器可能不包含應查找的元素，但由於雜湊操作，這些元素在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布隆過濾器如何實現的詳細內容。更多資訊請關注PHP中文網其他相關文章！