開篇思考
- 你能想到哪些方式判斷一個元素是否存在集合中？
- 布隆過濾器并不存儲資料本身，那麼是怎麼做到過濾的？
- 布隆過濾器實作？參數配置？
一般我們用來判斷一個元素是否存在，會想到用 List，Map，Set 等，會将元素先儲存下來，然後進行篩選。
但是這樣的形式都有一個弊端就是一定要儲存資料才行，可是我們僅僅想知道是否存在資料，并不要求擷取實際資料，
這時候就會覺得這種方式實在是浪費空間。
什麼情況下我們隻需要判斷是否存在這個元素呢？
在系統設計的時候，我們會考慮大量并發的形式，但是很多請求可能是在通路不存在的資料，
那麼我們就沒有必要繼續這個請求，可以在 API 網關層就直接過濾掉。
Bloom Filter 布隆過濾器原理
Bloom filter 是由 Howard Bloom 在 1970 年提出的二進制向量資料結構，它具有很好的空間和時間效率，
被用來檢測一個元素是不是集合中的一個成員。
布隆過濾器實作是不儲存資料本身，而是通過 K 個 hash 函數來計算在 byte[] 數組中的存放位置，
并把這個位置的值設定為 1， 而這個 K 到底是多少個呢，要根據公式來算出，待會列出。
除了這個 K 值，我們還要計算 byte[] 數組的長度 m ，下面一并列出計算公式：
- fpp : 誤判率參數，(must be 0 < fpp < 1)
- n ：預估的需要過濾的總數量
- ln ：求對數，不會的把高中老師的名字寫下來
- m ：數組長度
- n ：預估的需要過濾的總數量
下面我們以數字 11 為例來使用，有個網站可以測試布隆過濾器，
線上測試布隆 布隆過濾器的優點、缺點
優點：
- 節省空間，不用儲存所有資料，知識通過 hash 值來計算位置，并通過 byte[] 記錄下來。
- 速度快，時間複雜度低 O(1);
缺點：
- 精度低，假設：a 計算的位置 1 ，3 ；b 計算的位置 5，7；c 計算的位置 1，7，那麼 c 一定存在嗎？
- 不能直接删除，因為想要删除就要把對應的位置置為 0 ，如果這樣做，可能會影響其他值的過濾。
# 布隆過濾器實作
這個其實在 google guava 包中有現成的實作，不用我們自己去實作。我們看看是怎麼實作的；
/**
* 計算 bit 數組的長度公式
* n ： 預估資料量
* p ： 誤差率 0-1
*/
@VisibleForTesting
static long optimalNumOfBits(long n, double p) {
if (p == 0.0D) {
p = 4.9E-324D;
}
return (long)((double)(-n) * Math.log(p) / (Math.log(2.0D) * Math.log(2.0D)));
} /**
* 計算 hash 函數個數的方法
* n ： 預估資料量
* m ： bit 數組長度
*/
@VisibleForTesting
static int optimalNumOfHashFunctions(long n, long m) {
return Math.max(1, (int)Math.round((double)(m / n) * Math.log(2.0D)));
} 動手玩一玩
- expectedInsertions 代表預估數量，越大越準确，在下面的例子中，可以自己随意設定 p 值，過小會發現後面會傳回 true
- fpp ： 誤差率 0-1
import com.google.common.base.Charsets;
import com.google.common.hash.BloomFilter;
import com.google.common.hash.Funnels;
public class BloomFilterTest {
public static void main(String[] args) {
int expectedInsertions = 800000000;
double fpp = 0.00001;
BloomFilter<CharSequence> bloomFilter = BloomFilter.create(Funnels.stringFunnel(Charsets.UTF_8), expectedInsertions, fpp);
int i = 10000;
while (i > 1){
bloomFilter.put("aa" + i);
System.out.println(bloomFilter.mightContain("ab" + i));
i--;
}
}
}
喜歡文章請關注我
程式領域