五分鐘搞懂布隆過濾器，億級數(shù)據(jù)過濾算法值得擁有

在正式講解布隆過濾器之前，先讓我們看看這個業(yè)務(wù)場景：

Redis 是軟件架構(gòu)中常用的組件，最常見的用法是將熱點數(shù)據(jù)緩存到 Redis 中，以減少數(shù)據(jù)庫的壓力；查詢過程中最常見的用法是：查詢 Redis，如果能查詢到則直接返回，如果 Redis 中不存在則繼續(xù)查詢數(shù)據(jù)庫。

這種方式可以減少數(shù)據(jù)庫的訪問次數(shù)，但是“當緩存中沒有，就查詢數(shù)據(jù)庫”，在高并發(fā)的環(huán)境中依然會有風險，比如 90% 的請求數(shù)據(jù)都不在緩存中，那么這些請求就都會落到數(shù)據(jù)庫上，這就是緩存穿透。

那么有沒有什么辦法解決這個問題呢？這就可以使用【布隆過濾器】了，它可以確定“某項數(shù)據(jù)肯定不存在”。

布隆過濾器是一個叫“布隆”的人提出的，它本身是一個很長的二進制向量（想象成數(shù)組）和一系列隨機映射函數(shù)（想象成多個 Hash 函數(shù)），二進制向量中存放的不是0，就是1（在學(xué)習布隆過濾器之前，可以先了解 BitMap 算法，便于理解）。

比如要根據(jù)客戶手機號做為條件查詢客戶信息，通常會把手機號碼設(shè)置成緩存中的 Key，讓我們設(shè)置一個長度為 16 的布隆過濾器。

布隆過濾器初始化都是 0；

對 13800000000 分別進行 hash1()、hash2()、hash3() 運算，得到三個結(jié)果 5、9、12，把對應(yīng)位置設(shè)置成 1；

對 18900000000 分別進行 hash1()、hash2()、hash3() 運算，得到三個結(jié)果 2、8、12，把對應(yīng)位置設(shè)置成 1，現(xiàn)在 2、5、8、9、12 都是 1，其余元素都是 0；

如果我們想要驗證某個電話號碼是否存在，需要怎么做呢？

對 13700000000 分別進行 hash1()、hash2()、hash3() 運算，得到三個結(jié)果 1、9、13，然后去判斷第 1、9、13 位上的值是 0 還是 1，如果不全是 1 的話，就說明 13700000000 不在這個布隆過濾器上；這就確定了“某項數(shù)據(jù)肯定不存在”。

當然我們也可以看出來布隆過濾器有個問題，那就是不能保證數(shù)據(jù)肯定存在，比如對 18000000000 分別進行 hash1()、hash2()、hash3() 運算，得到的結(jié)果是 5、8、9，恰好這三位都是 1，但實際上這條數(shù)據(jù)并不存在，所以布隆過濾器有一定的誤判率；

而且因為多個數(shù)據(jù)經(jīng)過運算后可能會映射到同一個位置（138 和 189 的運算結(jié)果都有 12），所以布隆過濾器很難做到刪除，除非要為每一位增加一個計數(shù)器，刪除的時候需要給計數(shù)器減?1，直到計數(shù)器為 0 時，才將布隆過濾器對應(yīng)位置修改成 0。

• 可以確定一個元素肯定不存在，但是不能確定一個元素肯定存在；

• 二進制向量越長，映射函數(shù)越多，誤判率越低；如果提前可以確定誤判率，也可以反推出來布隆過濾器的長度；

• 可以添加元素，但是不能刪除元素（除非增加計數(shù)器）；

• 在存儲空間和插入查詢的時間復(fù)雜度都有巨大優(yōu)勢。

回到本文開頭的那個業(yè)務(wù)場景，為了防止緩存穿透，可以使用布隆過濾器過濾掉肯定不存在的數(shù)據(jù)，誤判的請求雖然還是會放到到數(shù)據(jù)庫，但已經(jīng)極大地減少了穿透的數(shù)量。

Code 不是目的，Coding 的過程是為了加深理解。

首先我們需要定義一個 bitmap，在 JDK 中，已經(jīng)有對應(yīng)實現(xiàn)的數(shù)據(jù)結(jié)構(gòu)類 java.util.BitSet：

//設(shè)置一個布隆過濾器private int DEFAULT_SIZE = 1 << 30;
private BitSet bitset ;

我們還需要一組映射函數(shù)，這里可以使用加法 hash 函數(shù)，設(shè)置 6 個質(zhì)數(shù)，對應(yīng) 6 個不同的 hash 函數(shù)：

//定義一個質(zhì)數(shù)數(shù)組，長度為6，可以生成6個hash函數(shù)，用于隨機映射private int[] seeds = {3, 7, 13, 31, 37, 61};
private HashFunction[] functions = new HashFunction[seeds.length];

在構(gòu)造函數(shù)中進行初始化，設(shè)置 BitSet 的長度，生成映射函數(shù)：

/*** 初始化*/public BloomFilter() {  bitset = new BitSet(DEFAULT_SIZE);
  for (int i = 0; i < seeds.length; i++) {      functions[i] = new HashFunction(DEFAULT_SIZE, seeds[i]);  }}

/*** 添加一個元素，得到hash運算后的結(jié)果，將對應(yīng)的位置修改成1（true）* @param value*/public void add(String value) {  if (value != null) {      for (HashFunction f : functions) {    bitset.set(f.hash(value), true);      }  }}

判斷元素是否在布隆管理器中，需要對入?yún)⑦M行 6 次 hash 運算，再查看結(jié)果對應(yīng)的位置上是 0 還是 1（true or false），如果其中一位是 0，表示數(shù)據(jù)肯定不存在，如果都是 1，表示數(shù)據(jù)（大概率）可能存在。

/*** 判斷元素是否在布隆過濾器中* @param value* @return*/public boolean contains(String value) {  if (value == null) {      return false;  }
  for (HashFunction f : functions) {    if(!bitset.get(f.hash(value))){      //一個位置上不為1（true），就證明不存在，直接返回false      return false;    }  }
  return true;}

已經(jīng)有很多開源框架幫我們實現(xiàn)了布隆管理器，比如 Google 出品的 Guava 工具庫，其中就有開箱即用的布隆過濾器；

public class BloomFilterTest {  public static void main(String[] args){    int size = 1000000;    //布隆過濾器    BloomFilter bloomFilter = BloomFilter.create(Funnels.integerFunnel(), size, 0.001);        for (int i = 0; i < size; i++) {            bloomFilter.put(i);        }        List list = new ArrayList(1000);        for (int i = size + 1; i < size + 10000; i++) {            if (bloomFilter.mightContain(i)) {                list.add(i);            }        }        System.out.println("誤判數(shù)量：" + list.size());  }}