概念
布隆過濾器（Bloom Filter）是1970年由布隆提出的。它實際上是一個很長的二進制向量和一系列隨機映射函數(shù)。布隆過濾器可以用于檢索一個元素是否在一個集合中。它的優(yōu)點是空間效率和查詢時間都比一般的算法要好的多，缺點是有一定的誤識別率和刪除困難。
和HashMap對比
我們常用HashMap來檢索一個元素是否在一個集合中，但是當(dāng)這個集合很大時，比如上億、十億的場景，這就會給我們帶來空間上的問題；這個時候用到布隆過濾器（Bloom Filter）就可以很好的幫助我們解決這個問題。
基本思想
- 布隆過濾器里有一個初始狀態(tài)都為0的數(shù)組；
- 集合中的元素經(jīng)過
N個散列函數(shù)計算出元素在數(shù)組當(dāng)中的位置，并且將數(shù)組中對應(yīng)位置的0改成1； - 如果此時需要判斷元素X是否存在，那么元素X也會經(jīng)過這N個散列函數(shù)的運算而得到數(shù)組中的若干個位置，如果得到的若干個位置中的值
均為1，那么則證明元素X很可能存在與集合當(dāng)中，反之則證明元素X一定不存在于集合當(dāng)中。
注意：這若干個位置均為1，也只能表明可能存在，并非一定存在。
原因：
- 如果根據(jù)同一個哈希函數(shù)得到的哈希值不同，那么這兩個哈希值的原始輸入值肯定不同。
- 如果根據(jù)同一個哈希函數(shù)得到的兩個哈希值相等，兩個哈希值的原始輸入值有可能相等，有可能不相等。
優(yōu)缺點
優(yōu)點
在空間和時間方面，都有著巨大的優(yōu)勢。因為不是存完整的數(shù)據(jù)，是一個二進制向量，能節(jié)省大量的內(nèi)存空間，時間復(fù)雜度方面，由于計算時是根據(jù)散列函數(shù)計算查詢的，那么假設(shè)有N個散列函數(shù)，那么時間復(fù)雜度就是O(N)；同時在存儲元素時存儲的不是元素本身，而是二進制向量，所以在一些對保密性要求嚴格的場景有一定優(yōu)勢。
缺點
存在一定的誤判（存進布隆過濾器里的元素越多，誤判率越高）；不能刪除布隆過濾器里的元素，隨著使用的時間越來越長，因為不能刪除，存進里面的元素越來越多，導(dǎo)致占用內(nèi)存越來越多，誤判率越來越高，最后不得不重置。
應(yīng)用場景
- 網(wǎng)頁爬蟲對 URL 去重，避免爬取相同的 URL 地址；
- 反垃圾郵件，從數(shù)十億個垃圾郵件列表中判斷某郵箱是否垃圾郵箱；
- Google Chrome 使用布隆過濾器識別惡意 URL；
- Medium 使用布隆過濾器避免推薦給用戶已經(jīng)讀過的文章；
- Google BigTable，Apache HBbase 和 Apache Cassandra 使用布隆過濾器減少對不存在的行和列的查找；
- 解決緩存穿透：利用布隆過濾器我們可以預(yù)先把數(shù)據(jù)查詢的主鍵，比如用戶ID或文章ID緩存到過濾器中。當(dāng)根據(jù)ID進行數(shù)據(jù)查詢的時候，我們先判斷該ID是否存在，若存在的話，則進行下一步處理。若不存在的話，直接返回，這樣就不會觸發(fā)后續(xù)的數(shù)據(jù)庫查詢。需要注意的是緩存穿透不能完全解決，我們只能將其控制在一個可以容忍的范圍內(nèi)。
