布隆過濾器(Bloom Filter)

布隆過濾器用來判斷一個(gè) key 是否存在于已知集合中.

算法流程:

  1. 構(gòu)建一個(gè)長度為 n 的數(shù)組,每個(gè)比特位初始化為 0
  2. 需要 k 個(gè) hash 函數(shù),每個(gè)函數(shù)可以把 key 散列為一個(gè)整數(shù)
  3. 插入m 個(gè)已知的 key,循環(huán)進(jìn)行下面的操作
    a. 分別用 k 個(gè) hash 函數(shù)對key 進(jìn)行散列
    b. 將散列值對應(yīng)的二進(jìn)制位置為 1
  4. 查找 key 是否存在
    a. 分別用 k 個(gè) hash 函數(shù)對key 進(jìn)行散列
    b. 查看對應(yīng)的二進(jìn)制位是否都為 1

特點(diǎn)

  1. 只需要少量的存儲空間(n)
  2. 通過布隆過濾器后也有一定的概率不存在這個(gè) key
  3. 無法刪除
  4. 判斷key 是否 一定不存在 或 可能存在

典型應(yīng)用場景:
分布式緩存中,如果 redis 緩存沒有命中就需要訪問數(shù)據(jù)庫,但如果請求不存在的數(shù)據(jù)(也就是緩存穿透),那么每次攻擊都會(huì)請求數(shù)據(jù)庫,使得數(shù)據(jù)庫的壓力過大.可以在數(shù)據(jù)庫和 redis 中構(gòu)建一個(gè)布隆過濾器,需要訪問數(shù)據(jù)庫時(shí)先要通過布隆過濾器,這就可以解決緩存穿透問題.

False positives

假設(shè) Hash 函數(shù)以等概率選擇并設(shè)置 Bit Array中的某一位,m 是該數(shù)組的大小,k 是 hash 函數(shù)的個(gè)數(shù)

某一特定位在一次操作后為'0'的概率是

1 - \frac{1}{m}

某一特定位在k 次hash 操作后為'0'
(1 - \frac{1}{m})^k

插入了 n 個(gè)元素,某一特定位仍然為'0'
(1 - \frac{1}{m})^{kn}

該位為 '1'的概率為
1- [1 - \frac{1}{m}]^{kn}

某一元素被錯(cuò)誤的認(rèn)為在集合中的概率
(1- [1 - \frac{1}{m}]^{kn})^k

可以看出隨著 m 的增加,False positives 的概率會(huì)下降,隨著插入元素 n 的增加,False positives 的概率會(huì)上升

?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
【社區(qū)內(nèi)容提示】社區(qū)部分內(nèi)容疑似由AI輔助生成，瀏覽時(shí)請結(jié)合常識與多方信息審慎甄別。
平臺聲明：文章內(nèi)容（如有圖片或視頻亦包括在內(nèi)）由作者上傳并發(fā)布，文章內(nèi)容僅代表作者本人觀點(diǎn)，簡書系信息發(fā)布平臺，僅提供信息存儲服務(wù)。

相關(guān)閱讀更多精彩內(nèi)容

友情鏈接更多精彩內(nèi)容