[[349127]]

這一篇是我重寫的，之前寫過一篇發(fā)現(xiàn)面試的時候問的問題雖然大概能解決，但是有幾個點沒有整理到位，所以自己給自己列出了很多面試常見的問題，準(zhǔn)備一篇一篇去解決。本文整體思路是延續(xù)之前的那篇文章，在此基礎(chǔ)之上添加了幾個點而已。

布隆過濾器主要是在redis中問的比較多，因此像這種數(shù)據(jù)結(jié)構(gòu)類的，主要是考原理以及使用場景。下面一點一點開始逐步介紹。

一、認(rèn)識布隆過濾器

1、概念

布隆過濾器其實就是加快判定一個元素是否在集合中出現(xiàn)的方法。比如說在一個大字典中，要查找某個單詞是否存在，于是我們就可以使用布隆過濾器，快速高效省時省力。

這里有一個考察點，那就是布隆過濾器只能判定一個元素不在集合里面，不能判斷存在，什么意思呢!就是說一個蘋果不在籃子里，這個我可以通過布隆過濾器知道，但是一定在籃子里嘛?這個通過布隆過濾器我是不能判定的。

下面通過原理就能理解這個了。

2、原理

先舉一個例子，在我們身邊充斥著各種各樣的XX網(wǎng)站，為了不毒害我們祖國的花朵，于是國家網(wǎng)警就開始對這些網(wǎng)站進(jìn)行割除過濾，問題來了，這些網(wǎng)站的地址其實是不停的更換的，這些垃圾網(wǎng)站和正常網(wǎng)站加起來全世界據(jù)統(tǒng)計也有幾十億個。因此就會帶來如下的問題：

(1)網(wǎng)站數(shù)量太多，存儲起來比較麻煩。一個地址最起碼有32個字節(jié)，一億個地址就需要1.6G的內(nèi)存。

(2)一個一個比較，太費時間了。

因此布隆過濾器被設(shè)計出來了，他是如何做到高效的呢?本質(zhì)上其實就是一個HASH映射器。他的底層其實是一個超大的二進(jìn)制向量和一系列隨機映射函數(shù)?，F(xiàn)在我們按照之前的那個例子，我們存儲1億個垃圾網(wǎng)站地址。

(1)第一步：建立一個32億二進(jìn)制(比特)，也就是4億字節(jié)的向量。全部置0。

img

(2)第二步：網(wǎng)警用八個不同的隨機數(shù)產(chǎn)生器(F1,F2, …,F8) 產(chǎn)生八個信息指紋(f1, f2, …, f8)。

(3)第三步：用一個隨機數(shù)產(chǎn)生器 G 把這八個信息指紋映射到 1 到32億中的八個自然數(shù) g1, g2, …,g8。

(4)第四步：把這八個位置的二進(jìn)制全部設(shè)置為一。

img

OK，有一天網(wǎng)警查到了一個可疑的網(wǎng)站，想判斷一下是否是XX網(wǎng)站，于是就開始檢查了。通過同樣的方法將XX網(wǎng)站通過哈希映射到32億個比特位數(shù)組上的8個點。如果8個點的其中有一個點不為1，則可以判斷該元素一定不存在集合中。

注意：現(xiàn)在你可能會發(fā)現(xiàn)一個問題，如果兩個XX網(wǎng)站通過上面的步驟映射到了相同的8個點上，或者是有一部分點是重合的，這時候該怎么辦?于是就出現(xiàn)了誤報，也就是說A網(wǎng)站在12345678個點上全部置1，B網(wǎng)站通過同樣的方式在23456789上全部置1，這時候B網(wǎng)站來了是不能確定是否包含的。這個邏輯相信各位都理解。這個是最基礎(chǔ)的面試問題。

3、誤報率

這一小節(jié)是稍微高級一點點，某中廠問到了一次，于是這一次就添加了進(jìn)來。

通過上面的解釋相信都大概了解的差不多了，其實就是hash函數(shù)映射，由于有hash沖突產(chǎn)生了誤報率，誤報率也就是判斷失敗的情況。

既然是由于hash沖突，那我把布隆過濾器的二進(jìn)制向量調(diào)到很大，這樣不就解決了嘛，但是由于數(shù)據(jù)量比較大，因此現(xiàn)在就要考慮一下誤報率和存儲效率之間選擇一個折中值了。有一個計算公式如下：公式來源于github

假設(shè)位數(shù)組的長度為m，哈希函數(shù)的個數(shù)為k。檢測某一元素是否在該集合中的誤報率是：

[公式]

如何使得誤報率最小，數(shù)學(xué)問題，求導(dǎo)就可以了。

4、使用場景

(1)google的guava包中有對Bloom Filter的實現(xiàn)

(2)通常使用布隆過濾器去解決redis中的緩存穿透，解決方案是redis中bitmap的實現(xiàn)，

(3)釣魚網(wǎng)站、垃圾郵件檢測

大體就這些，可能還有很多!!!

二、代碼實現(xiàn)布隆過濾器

上面只是給出了其原理，下面我們代碼實現(xiàn)一下。

public   class  MyBloomFilter { 
    // 2 << 25表示32億個比特位 
     private static final int DEFAULT_SIZE =  2 << 25 ; 
     private static final int[] seeds = new int [] {3,5,7,11,13,19,23,37 }; 
     //這么大存儲在BitSet 
     private  BitSet  bits = new BitSet(DEFAULT_SIZE); 
     private  SimpleHash[] func  = new  SimpleHash[seeds.length]; 
 
     public   static   void  main(String[] args) { 
        //可疑網(wǎng)站 
        String value = "www.愚公要移山.com" ; 
        MyBloomFilter filter = new MyBloomFilter(); 
        //加入之前判斷一下 
        System.out.println(filter.contains(value)); 
        filter.add(value); 
        //加入之后判斷一下 
        System.out.println(filter.contains(value)); 
    } 
    //構(gòu)造函數(shù) 
     public  MyBloomFilter() { 
         for  ( int  i  =   0 ; i  <  seeds.length; i ++ ) { 
            func[i]  =   new  SimpleHash(DEFAULT_SIZE, seeds[i]); 
        } 
    } 
     //添加網(wǎng)站 
     public   void  add(String value) { 
         for  (SimpleHash f : func) { 
            bits.set(f.hash(value),  true ); 
        } 
    } 
     //判斷可疑網(wǎng)站是否存在 
     public   boolean  contains(String value) { 
         if  (value  ==   null ) { 
             return   false ; 
        } 
         boolean  ret  =   true ; 
         for  (SimpleHash f : func) { 
            //核心就是通過“與”的操作 
            ret  =  ret  &&  bits.get(f.hash(value)); 
        } 
         return  ret; 
    } 
} 

還有一個SimpleHash，我們看一下

public   static   class  SimpleHash { 
        private  int  cap; 
        private  int  seed; 
 
        public  SimpleHash( int  cap,  int  seed) { 
            this .cap  =  cap; 
            this .seed  =  seed; 
       } 
        public   int  hash(String value) { 
            int  result  =   0 ; 
            int  len  =  value.length(); 
            for  ( int  i  =   0 ; i  <  len; i ++ ) { 
               result  =  seed  *  result  +  value.charAt(i); 
           } 
            return  (cap  -   1 )  &  result; 
       } 
   } 

這就是布隆過濾器的實現(xiàn)。

本文轉(zhuǎn)載自微信公眾號「愚公要移山」，可以通過以下二維碼關(guān)注。轉(zhuǎn)載本文請聯(lián)系愚公要移山公眾號。