布隆過(guò)濾器原理很簡(jiǎn)單：就是把一個(gè)字符串哈希成一個(gè)整數(shù)key，然后選取一個(gè)很長(zhǎng)的比特序列，開(kāi)始都是0，在key把此位置的0變?yōu)?；下次進(jìn)來(lái)一個(gè)字符串，哈希之后的值key，如果在此比特位上的值也是1，那么就說(shuō)明這個(gè)字符串存在了。

如果按照上面的做法，那就和哈希算法沒(méi)有什么區(qū)別了，哈希算法還有重復(fù)的呢。

布隆過(guò)濾器是將一個(gè)字符串哈希成多個(gè)key，我還是按照書(shū)上的說(shuō)吧。

先建立一個(gè)16億二進(jìn)制常量，然后將這16億個(gè)二進(jìn)制位全部置0。對(duì)于每個(gè)字符串，用8個(gè)不同的隨機(jī)產(chǎn)生器（F1,F2,.....,F8）產(chǎn)生8個(gè)信息指紋(f1,f2,....,f8).再用一個(gè)隨機(jī)數(shù)產(chǎn)生器G把這八個(gè)信息指紋映射到1到16億中的8個(gè)自然數(shù)g1,g2,...,g8?，F(xiàn)在把這8個(gè)位置的二進(jìn)制位全部變?yōu)?。這樣一個(gè)布隆過(guò)濾器就建好了。

那么如何檢測(cè)一個(gè)字符串是否已經(jīng)存在了呢？

現(xiàn)在用8個(gè)隨機(jī)數(shù)產(chǎn)生器（F1,F2,...,F8）對(duì)這個(gè)字符串產(chǎn)生8個(gè)信息指紋s1,s2,...,s8，然后將這8個(gè)信息指紋對(duì)應(yīng)到布隆過(guò)濾器的8個(gè)二進(jìn)制位，分別是T1,T2,...,T8.如果字符串存在，那么顯然T1,T2,...,T8對(duì)應(yīng)的二進(jìn)制位都應(yīng)該是1。就是這樣來(lái)判斷字符串是否已經(jīng)存在的。

其實(shí)布隆過(guò)濾器就是對(duì)哈希算法的一個(gè)擴(kuò)展，既然本質(zhì)是哈希，那么就肯定會(huì)有不足，也就是說(shuō)，肯定會(huì)有誤判，一個(gè)字符串明明沒(méi)有出現(xiàn)過(guò)而布隆過(guò)濾器判斷出現(xiàn)了，雖然可能性很小，但是確實(shí)存在。

那么如何減少這種概率呢，首先可以想到的是如果將8個(gè)信息指紋擴(kuò)展到16個(gè)錯(cuò)誤的概率肯定會(huì)降低，但是也要考慮到，這樣的話，那么一個(gè)布隆過(guò)濾器所能存儲(chǔ)的字符串?dāng)?shù)量也降低了1倍；另外就是選取很好的哈希函數(shù)，對(duì)字符串的哈希方法有很多種，其中不乏很好的哈希函數(shù)。

布隆過(guò)濾器主要運(yùn)用在過(guò)濾惡意網(wǎng)址用的，將所有的惡意網(wǎng)址建立在一個(gè)布隆過(guò)濾器上，然后對(duì)用戶的訪問(wèn)的網(wǎng)址進(jìn)行檢測(cè)，如果在惡意網(wǎng)址中那么就通知用戶。這樣的話，我們還可以對(duì)一些常出現(xiàn)判斷錯(cuò)誤的網(wǎng)址設(shè)定一個(gè)白名單，然后對(duì)出現(xiàn)判斷存在的網(wǎng)址再和白名單中的網(wǎng)址進(jìn)行匹配，如果在白名單中，那么就放行。當(dāng)然這個(gè)白名單不能太大，也不會(huì)太大，布隆過(guò)濾器錯(cuò)誤的概率是很小的。有興趣的讀者可以去查閱，布隆過(guò)濾器的錯(cuò)誤率。

下面給出Java版的布隆過(guò)濾器源碼：

import java.util.BitSet; 
 
/** 
 * 
 * @author xkey 
 */ 
public class BloomFilter { 
 
  private static final int DEFAULT_SIZE = 2 << 24;//布隆過(guò)濾器的比特長(zhǎng)度 
  private static final int[] seeds = {3,5,7, 11, 13, 31, 37, 61};//這里要選取質(zhì)數(shù)，能很好的降低錯(cuò)誤率 
  private static BitSet bits = new BitSet(DEFAULT_SIZE); 
  private static SimpleHash[] func = new SimpleHash[seeds.length]; 
 
  public static void addValue(String value) 
  { 
    for(SimpleHash f : func)//將字符串value哈希為8個(gè)或多個(gè)整數(shù)，然后在這些整數(shù)的bit上變?yōu)? 
      bits.set(f.hash(value),true); 
  } 
   
  public static void add(String value) 
  { 
    if(value != null) addValue(value); 
  } 
   
  public static boolean contains(String value) 
  { 
    if(value == null) return false; 
    boolean ret = true; 
    for(SimpleHash f : func)//這里其實(shí)沒(méi)必要全部跑完，只要一次ret==false那么就不包含這個(gè)字符串 
      ret = ret && bits.get(f.hash(value)); 
    return ret; 
  } 
   
  public static void main(String[] args) { 
    String value = "m.fzitv.net"; 
    for (int i = 0; i < seeds.length; i++) { 
      func[i] = new SimpleHash(DEFAULT_SIZE, seeds[i]); 
    } 
    add(value); 
    System.out.println(contains(value)); 
  } 
} 
 
class SimpleHash {//這玩意相當(dāng)于C++中的結(jié)構(gòu)體 
 
  private int cap; 
  private int seed; 
 
  public SimpleHash(int cap, int seed) { 
    this.cap = cap; 
    this.seed = seed; 
  } 
 
  public int hash(String value) {//字符串哈希，選取好的哈希函數(shù)很重要 
    int result = 0; 
    int len = value.length(); 
    for (int i = 0; i < len; i++) { 
      result = seed * result + value.charAt(i); 
    } 
    return (cap - 1) & result; 
  } 
} 

總結(jié)：布隆過(guò)濾器是對(duì)哈希算法的一種創(chuàng)新，而且需要消耗的空間也很小，錯(cuò)誤率很低。總之這種創(chuàng)新的思路很值得學(xué)習(xí)，是一種對(duì)bit這種數(shù)據(jù)類型的運(yùn)用。

以上這篇布隆過(guò)濾器(Bloom Filter)的Java實(shí)現(xiàn)方法就是小編分享給大家的全部?jī)?nèi)容了，希望能給大家一個(gè)參考，也希望大家多多支持腳本之家。

最新評(píng)論