布隆過濾器 (Bloom Filter)#

布隆過濾器是一種空間效率極高的概率型資料結構，用於快速判斷元素「是否可能存在」。

與快取的關係#

核心特性

• 說「不在」：100% 準確
• 說「在」：可能誤判（False Positive）

工作原理#

結構#

• 一個長度為 m 的二進位陣列，初始全為 0
• K 個獨立的雜湊函式

寫入操作#

將元素經過 K 個雜湊函式計算，得到 K 個位置，將對應位元設為 1。

查詢操作#

將元素經過相同的 K 個雜湊函式計算：

• 若任一位置為 0 ➡️ 肯定不存在
• 若所有位置都為 1 ➡️ 可能存在（需二次確認）

參考實作#

底層就是一個位圖（LongArray bitset）加上 K 個雜湊。實務上常用「雙雜湊組合」技巧，只算兩個雜湊值就能便宜地衍生出 K 個位置。

class BloomFilter(private val m: Int, private val k: Int) {
    // 長度為 m 的位圖，底層用 LongArray（每個 Long 存 64 個 bit）
    private val bits = LongArray(m / 64 + 1)

    // 用兩個雜湊組合出 k 個位置（Kirsch–Mitzenmacher 技巧）
    private fun positions(value: String): IntArray {
        val h1 = value.hashCode()
        val h2 = (h1 ushr 16) or (h1 shl 16)
        return IntArray(k) { i ->
            Math.floorMod(h1 + i * h2, m)   // floorMod 確保非負索引
        }
    }

    fun add(value: String) {
        for (pos in positions(value)) {
            bits[pos ushr 6] = bits[pos ushr 6] or (1L shl (pos and 63))
        }
    }

    // 回傳 false → 一定不存在；回傳 true → 可能存在（可能誤判）
    fun mightContain(value: String): Boolean =
        positions(value).all { pos ->
            (bits[pos ushr 6] and (1L shl (pos and 63))) != 0L
        }
}

優缺點#

優點#

• 極高空間效率：不儲存原始資料，只存 0/1
• 極快查詢速度：位元運算，O(K) 時間複雜度

缺點#

• 刪除困難：多個元素可能共享同一位元
• 存在誤識別率：需要後端二次確認

布隆過濾器無法刪除元素。如需支援刪除，可考慮使用 Counting Bloom Filter（每個位置用計數器代替單一位元）。

實際應用#

比特幣網路 (SPV 節點)#

輕量級用戶端使用布隆過濾器快速判斷交易是否在某區塊中：

• Filter 返回「不存在」➡️ 跳過該區塊
• Filter 返回「存在」➡️ 下載區塊詳細確認

防止快取穿透#

在 Redis 前加一層布隆過濾器：

• Key 不在 Filter ➡️ 直接返回空（攔截惡意查詢）
• Key 在 Filter ➡️ 查詢 Redis/DB

分散式系統#

判斷資料是否在某節點上，減少無謂的網路請求。

參數設計#

誤判率與以下因素相關：

• m：位陣列長度（越大誤判率越低）
• k：雜湊函式數量（需適當平衡）
• n：預期插入元素數量

常用經驗公式：

• 最佳 k = (m/n) * ln(2)
• 10 億元素，10 倍大小位圖（100 億位元 ≈ 1.2GB），誤判率約 1%

誤判率的數學#

前面給的是經驗公式，這裡把假陽性率「從哪裡來」推一遍，會更有感覺。

設位陣列長度為 $m$、雜湊函式有 $k$ 個、已插入 $n$ 個元素。每次寫入會把 $k$ 個位置設為 1，這些位置可視為從 $m$ 個 bit 中均勻隨機抽取。那麼經過全部寫入後，某個特定 bit 仍然是 0 的機率是：

$$ P(\text{bit} = 0) = \left(1 - \frac{1}{m}\right)^{kn} \approx e^{-kn/m} $$

查詢一個「實際不存在」的元素時，它會被映射到 $k$ 個位置；只有當這 $k$ 個位置碰巧全是 1 時才會誤判。因此假陽性率約為：

$$ P_{\text{false positive}} \approx \left(1 - e^{-kn/m}\right)^k $$

直覺與數字感#

誤判的本質是：「別人剛好把你查的這幾個 bit 都設成 1 了」。而要讓 $k$ 個隨機位置同時都被別人撞中，機率是把每個位置「被設為 1」的機率連乘 $k$ 次——指數一壓，數值就掉得很快。這就是為什麼只要每個元素多分幾個 bit，誤判率就能壓到極低。

重點是這條曲線「指數級」往下走：花一點點空間（每元素十幾個 bit），就能換到極低的誤判率。布隆過濾器之所以實用，靠的正是這種「空間 ➡️ 準確度」的高效兌換比。

關鍵的不對稱性：只會誤報，永不漏報#

前面的「核心特性」已點到這件事，這裡把它的原因與用法含意講清楚——這是理解布隆過濾器最重要的一點。

不對稱性：布隆過濾器可能有 false positive（說「在」、其實不在），但絕不會有 false negative（說「不在」就一定不在）。

原因很單純：一個元素被寫入時，它對映的那幾個 bit 一定被設成了 1，而且之後永遠不會被改回 0（這也是它難以刪除的代價）。所以真正存在的元素，查詢時那幾個 bit 必然都是 1，絕不可能被判成「不在」。

這個不對稱性直接決定了它的適用場景：把它當成「快速否決」的第一道關卡。

• 它說「不存在」➡️ 可信，可以直接跳過、不必再查後端。
• 它說「存在」➡️ 存疑，需要再向真正的資料來源（DB、磁碟、區塊）查證一次。

換句話說，布隆過濾器擅長的是「用極小代價排除掉大量肯定沒有的情況」，把昂貴的精確查詢留給少數真正可能命中的請求。前面「防止快取穿透」「SPV 節點跳過區塊」都是這個模式的應用。

真實案例：用 bit + 雜湊把字典塞進極小記憶體#

布隆過濾器這套思想，最早其實是被「記憶體不夠用」逼出來的。

在記憶體還以 KB 計的年代，有人要替一套拼字檢查器解決一個棘手問題：要把七萬多個英文單字塞進大約 64 KB 的空間，好讓程式能即時判斷「使用者打的這個字到底是不是合法單字」。

若老老實實存下每個單字，光字串本身就遠遠超過 64 KB。他們的做法，正是日後布隆過濾器的雛形：開一個 bit 陣列，對每個單字算出多個雜湊值，把對應的 bit 設為 1；查詢時同樣算雜湊、看那幾個 bit 是否都為 1。代價是極低機率的漏判（把生字誤判成合法字），但換來的是把整本字典壓進原本不可能容納的空間。

這就是「用一點點錯誤率，換巨大空間」這個交易的鼻祖。它和今天我們在 Redis 前擋快取穿透、在區塊鏈節點裡跳過無關區塊，本質上是同一招——只是當年的瓶頸是記憶體，今天的瓶頸是後端查詢成本。

這套技巧的兩塊基石，本書都有獨立章節可對照：

• 位圖：用單一 bit 表示「有無」、把空間壓到極致的底層手法。
• 雜湊演算法：把任意元素均勻打散到固定範圍位置，是這裡「多個雜湊值」的來源。