# 布隆過濾器 ## 場景 假設你現在要處理這樣一個問題，你有一個網站并且擁有`很多`訪客，每當有用戶訪問時，你想知道這個ip是不是第一次訪問你的網站。 ### hashtable 可以么 一個顯而易見的答案是將所有的 IP 用 hashtable 存起來，每次訪問都去 hashtable 中取，然后判斷即可。但是題目說了網站有`很多`訪客， 假如有10億個用戶訪問過，假設 IP 是 IPV4， 那么每個 IP 的長度是 4 byte，那么你一共需要4 \* 1000000000 = 4000000000Bytes = 4G 。 如果是判斷 URL 黑名單，由于每個 URL 會更長（可能遠大于上面 IPV4 地址的 4 byte），那么需要的空間可能會遠遠大于你的期望。 ### bit 另一個稍微難想到的解法是bit， 我們知道bit有 0 和 1 兩種狀態，那么用來表示**存在**與**不存在**再合適不過了。 假如有 10 億個 IP，就可以用 10 億個 bit 來存儲，那么你一共需要 1 \* 1000000000 = (4000000000 / 8) Bytes = 128M, 變為原來的1/32, 如果是存儲URL這種更長的字符串，效率會更高。 問題是，我們怎么把 IPV4 和 bit 的位置關聯上呢？ 比如`192.168.1.1` 應該是用第幾位表示，`10.18.1.1` 應該是用第幾位表示呢？ 答案是使用哈希函數。 基于這種想法，我們只需要兩個操作，set(ip) 和 has(ip)，以及一個內置函數 hash(ip) 用于將 IP 映射到 bit 表。 這樣做有兩個非常致命的缺點： 1. 當樣本分布極度不均勻的時候，會造成很大空間上的浪費 > 我們可以通過優化散列函數來解決 1. 當元素不是整型（比如URL）的時候，BitSet就不適用了 > 我們還是可以使用散列函數來解決， 甚至可以多hash幾次 ### 布隆過濾器 布隆過濾器其實就是`bit + 多個散列函數`。k 次 hash(ip) 會生成多個索引，并將其 k 個索引位置的二進制置為 1。 如果經過 k 個索引位置的值都為 1，那么認為其**可能存在**(因為有沖突的可能)。 如果有一個不為1，那么**一定不存在**（一個值經過散列函數得到的值一定是唯一的），這也是布隆過濾器的一個重要特點。也就是說布隆過濾器回答了：**可能存在** 和 **一定不存在** 的問題。  從上圖可以看出， 布隆過濾器本質上是由**一個很長的二進制向量**和**多個哈希函數**組成。 由于沒有 hashtable 的100% 可靠性，因此這本質上是一種**可靠性換取空間的做法**。除了可靠性，布隆過濾器刪除起來也比較麻煩。 ### 布隆過濾器的應用 1. 網絡爬蟲 判斷某個URL是否已經被爬取過 1. K-V數據庫 判斷某個key是否存在 比如 Hbase 的每個 Region 中都包含一個 BloomFilter，用于在查詢時快速判斷某個 key 在該 region 中是否存在。 1. 釣魚網站識別 瀏覽器有時候會警告用戶，訪問的網站很可能是釣魚網站，用的就是這種技術 > 從這個算法大家可以對 tradeoff(取舍) 有更入的理解。