別眨眼網

前言：

最近看了一篇文章<<如何快速判斷某 URL 是否在 20 億的網址 URL 集合中>>，第一次知道“布隆過濾器”，查了些資料，覺得有必要整理一下。

布隆過濾器是什麼？

它有什麼缺點？

布隆過濾器的測試

解決快取擊穿的問題

一、布隆過濾器是什麼？

百度百科：

布隆過濾器（Bloom Filter）是1970年由布隆提出的。它實際上是一個很長的二進位制向量和一系列隨機對映函式。布隆過濾器可以用於檢索一個元素是否在一個集合中。它的優點是空間效率和查詢時間都比一般的演算法要好的多，缺點是有一定的誤識別率和刪除困難。

圖解：

它本身是一個很長的二進位制向量，既然是二進位制的向量，那麼顯而易見的，存放的不是0，就是1。

現在我們新建一個長度為16的布隆過濾器，預設值都是0，就像下面這樣：

現在需要新增一個數據：

我們透過某種計算方式，比如Hash1，計算出了Hash1（資料）=5，我們就把下標為5的格子改成1，就像下面這樣：

我們又透過某種計算方式，比如Hash2，計算出了Hash2（資料）=9，我們就把下標為9的格子改成1，就像下面這樣

還是透過某種計算方式，比如Hash3，計算出了Hash3（資料）=2，我們就把下標為2的格子改成1，就像下面這樣：

這樣，剛才新增的資料就佔據了布隆過濾器“5”，“9”，“2”三個格子。

可以看出，僅僅從布隆過濾器本身而言，根本沒有存放完整的資料，只是運用一系列隨機對映函式計算出位置，然後填充二進位制向量。

二、它有什麼優缺點？

優點

：可以高效的查詢和插入，它可以告訴你一條資料一定不存在或者可能存在。並且佔用非常少的記憶體空間。

例如：在10億條資料中判斷一條資料的是否存在？

如果用HashSet來處理，他的時間複雜度是O（1），但是他的空間複雜度呢？雜湊值是integer型別，一條資料的雜湊值佔用的空間是4個位元組，一共10億*4/1024/1024/1024約等於3。7G，佔用空間太大了。

如果用布隆過濾器呢，因為integer的最大2147483647，所以我們需要定義一個長度為2147483647的bit型陣列，如我們所知，每個位置只佔一個bit，每個位置只有0和1兩種狀態， 假如一個數據是雜湊是2，我們就可以把陣列座標2的部位標記為1，這個bit陣列將是00100。。。。。000；再來一個資料的雜湊是5，這個bit資料將是：00100100。。。000，以此類推。這樣就可以儲存所有可能的值。8個bit一個位元組，佔用的空間是2147483647/8/1024/1024=256M

缺點：

布隆過濾器期有一定的誤差率，資料越多，誤差率越大。為了減少誤差率，我們可以使用多個不同的雜湊函式生成多個雜湊值，並對每個生成的雜湊值指向的 bit 位置 1。例如上面圖解。

如果要判斷一個數據是否存在，我們只需要判斷他的不同雜湊函式值在 bit 位置中對應的是否為1就可以了，如果有不為1，肯定不存在；如果都為1，可能存在也可能不存在，這是因為雜湊值（又叫雜湊）具有“雜湊衝突”（兩個雜湊值相同，兩個輸入值很可能是相同的，也可能不同）的原因。

布隆過濾器刪除困難，為什麼呢？你想想，你要刪除一個數據，把對應bit位置的資料改為0，假如別的資料的雜湊值也佔用這個位置，不就亂套了。

演算法特點：

1、因使用雜湊判斷，時間效率很高。空間效率也是其一大優勢。2、有誤判的可能，需針對具體場景使用。3、因為無法分辨雜湊碰撞，所以不是很好做刪除操作。

三、布隆過濾器的測試

測試程式碼一

public class BloomFilterTest { private static final int insertions = 1000000； //100w @Test public void bfTest（）{ //初始化一個儲存string資料的布隆過濾器，初始化大小100w，不能設定為0 BloomFilter bf = BloomFilter。create（Funnels。stringFunnel（Charsets。UTF_8）， insertions，0。001）； //初始化一個儲存string資料的set，初始化大小100w Set sets = new HashSet<>（insertions）； //初始化一個儲存string資料的set，初始化大小100w List lists = new ArrayList（insertions）； //向三個容器初始化100萬個隨機並且唯一的字串——-初始化操作 for （int i = 0； i < insertions； i++） { String uuid = UUID。randomUUID（）。toString（）； bf。put（uuid）； sets。add（uuid）； lists。add（uuid）； } int wrong = 0；//布隆過濾器錯誤判斷的次數 int right = 0；//布隆過濾器正確判斷的次數 for （int i = 0； i < 10000； i++） { String test = i%100==0？lists。get（i/100）：UUID。randomUUID（）。toString（）；//按照一定比例選擇bf中肯定存在的字串 if（bf。mightContain（test））{ if（sets。contains（test））{ right ++； }else{ wrong ++； } } } System。out。println（“=================right=====================”+right）；//100 System。out。println（“=================wrong=====================”+wrong）； } }

測試程式碼二

private static int size = 1000000；//預計要插入多少資料 private static double fpp = 0。01；//期望的誤判率 private static BloomFilter bloomFilter = BloomFilter。create（Funnels。integerFunnel（）， size， fpp）； public static void main（String［］ args） { //插入資料 for （int i = 0； i < 1000000； i++） { bloomFilter。put（i）； } int count = 0； for （int i = 1000000； i < 2000000； i++） { if （bloomFilter。mightContain（i）） { count++； System。out。println（i + “誤判了”）； } } System。out。println（“總共的誤判數：” + count）； }

不同的資料結構有不同的適用場景和優缺點，你需要仔細權衡自己的需求之後妥善適用它們，布隆過濾器就是踐行這句話的代表。

四、快取擊穿的問題

什麼是快取擊穿？

正常情況下，我們會把經常用的資料放入快取中，一個請求進來，先去快取中查詢，如果有資料就返回，如果沒有就查詢資料庫，然後再把資料庫中的資料放入快取中。

但是呢，假如資料也沒有資料呢？這樣大量的請求就會不斷的去查詢資料庫，造成資料庫壓力過大甚至崩潰。

為什麼不把所有的資料都放入快取呢？

因為所有資料都放入快取，會消耗大量的空間，也不符合快取的初衷，不能暴力的把所有資料都放入快取。

怎麼解決呢？

可以使用布隆過濾器，快取所有的key相關的資訊，上面已經說過了，布隆過濾不僅效率高，而且佔用空間小。如果布隆過濾器判斷不存在就不用查快取或者資料庫了。