一個名叫布隆的人在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之所以能做到在時間和空間上的效率比較高,是因為犧牲了判斷的準確率、刪除的便利性
儘管容器可能不包含應查找的元素,但由於雜湊操作,這些元素在k 個雜湊位置的值都為1,所以可能會導致誤判。透過建立一個白名單來儲存可能會誤判的元素,當Bloom Filter中儲存的是黑名單時,可以降低誤判率。
刪除困難。一個放入容器的元素映射到bit數組的k個位置上是1,刪除的時候不能簡單的直接置為0,可能會影響其他元素的判斷。可以採用Counting Bloom Filter
1、為何要使用多個雜湊函數?
如果只使用一個雜湊函數,Hash本身就會經常發生衝突。例如長度100的數組,如果只使用一個雜湊函數,添加一個元素後,添加第二個元素時衝突的機率為1%,添加第三個元素時衝突的機率為2%…但如果使用兩個個雜湊函數,加入一個元素後,加入第二個元素時衝突的機率降為萬分之4(四種可能的衝突情況,情況總數100x100)
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中文網其他相關文章!