修改後#布隆過濾器：怎麼在幾十億數據中判斷一個字符串是否存在技术頭條網

前言:

最近看了一篇文章<>，第一次知道“布隆過濾器”，查了些資料，覺得有必要整理一下。

布隆過濾器是什麼？
它有什麼缺點？
布隆過濾器的測試
解決緩存擊穿的問題

一、布隆過濾器是什麼？

布隆過濾器（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<string> bf = BloomFilter.create(Funnels.stringFunnel(Charsets.UTF_8), insertions,0.001);
 //初始化一個存儲string數據的set，初始化大小100w
 Set<string> sets = new HashSet<>(insertions);
 //初始化一個存儲string數據的set，初始化大小100w
 List<string> lists = new ArrayList<string>(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);
 }
 
}
/<string>/<string>/<string>/<string>

測試代碼二

 private static int size = 1000000;//預計要插入多少數據
 private static double fpp = 0.01;//期望的誤判率
 private static BloomFilter<integer> 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);
 }
/<integer>