我們有時候需要判斷一個元素是否在給定的標籤集合內，例如我們想對信息去重，過濾垃圾郵箱，許可權檢查等等。當標籤元素數量比較少時，我們用一個哈希表存儲這些標籤元素即可，但當元素數量特別大時，哈希空間佔用非常高，此時就不再適合使用這種數據結構了。不過幸運的是，在大數據許多應用場景下，我們並不需要給出100%準確的判斷，此時，一種叫做 bloom fliter（布隆過濾器）的數據結構可以很好地 tradeoff 空間、時間和準確率。

Bloom Filter

Bloom Filter 本質上是位向量（bit vector）與哈希結合的產物。哈希表可以看做一對一的映射，為了解決哈希衝突，一個元素通過哈希映射成的對象比較大。而布隆過濾器則採取一種 tradeoff 方案，使用 k 個哈希函數將元素分別映射成 k 個佔用空間少的對象——布隆過濾器中這些對象為位向量中的某一位，這些單個對象允許衝突。一個元素只有 k 個哈希映射的位向量位置全部置位才表示此元素出現在集合中。

舉個栗子。假設我們有一個 8 bit 位向量，採用三種哈希函數（h1、h2、h3）進行映射，如下圖所示，a1 通過三個哈希函數映射到了位向量的第 7、5、2 位，a2 映射到了第 5、4、1 位，a3 映射到了第 5、2、1 位。如果新來一個元素映射到了第 7、5、2 位，那麼我們認為這個元素存在於給定集合中。

當然也有可能出現誤檢：一個元素不存在於集合中但是其它元素恰好把該元素映射到的 k 個位置置位了。例如還是上圖，假如一個新的元素通過 3 個哈希函數分別映射到第 5、4、2 個位置，那麼給出的結果是它在給定集合中，但事實上它不在，這時就出現了誤檢。

直覺上這種誤檢概率是很低的（後面我們通過理論分析誤檢率），所以 Bloom Filter 很好地進行了空間和準確率的折衷。而且如果希望消除這種誤檢也很簡單，只需要簡單的增加一個白名單進行剔除即可。

所以一個 bloom filter 應該有以下元素：位向量及其 size、當前集合元素個數、使用的哈希函數個數、白名單列表、存儲所有哈希函數的 vector 以及用於產生這些哈希函數的隨機函數引擎。

布隆過濾器類的構造函數很關鍵，要創建之後需要用到的 k 個哈希哈數，我們這裡採用全域哈希——Universal Hash（後面有時間專門講一講這個）。其函數族公式如下：

根據這個公式我們使用 lambda 表達式生成 k 個哈希函數。此處原輸入對象為字元串，我們調用 c++ 自帶哈希使其變為整數。（此處如果出現碰撞則後面直接 GG，這裡將來可以替換成魯棒性更高的哈希族函數直接對 string 處理）

要給集合中添加一個元素（加入黑名單）：只需將該元素所有哈希對應的位向量相應位置置位即可。

添加白名單隻需給相應的 set 插入一個元素即可。

檢查一個元素是否在結合中（是否在黑名單里），首先看其是否白名單中，若不在白名單中，再檢查該元素的 k 個哈希對應的位置是否全部置位即可。

Bloom Filter 誤檢率

一個 bloom filter 主要有 3 個參數——位向量的位數 m、當前集合中元素的個數 n 和使用的哈希函數個數 k，那麼有如下分析（微信沒有輸入公式功能只能看圖了！）：

故 k 的最優解大致在 ln(2)m/n。當固定 m、n，變化 k 時錯誤率變化如下圖所示

綜上誤檢率、位向量位數、集合中存入的元素和選取的哈希函數個數互相制約，根據不同情況的需求我們可以選定三個參數確定第四個。

總結

本文介紹了布隆過濾器及其應用，給出了代碼實現並分析了其誤檢率，並說明了實際中設計布隆過濾器的指導公式主要方案。本文代碼在哈希函數方面還有待提高，小夥伴們可以開動大腦思考一下。