一、什么是布隆過濾器

為泰安等地區(qū)用戶提供了全套網(wǎng)頁設(shè)計制作服務(wù)，及泰安網(wǎng)站建設(shè)行業(yè)解決方案。主營業(yè)務(wù)為網(wǎng)站設(shè)計制作、成都網(wǎng)站設(shè)計、泰安網(wǎng)站設(shè)計，以傳統(tǒng)方式定制建設(shè)網(wǎng)站，并提供域名空間備案等一條龍服務(wù)，秉承以專業(yè)、用心的態(tài)度為用戶提供真誠的服務(wù)。我們深信只要達(dá)到每一位用戶的要求，就會得到認(rèn)可，從而選擇與我們長期合作。這樣，我們也可以走得更遠(yuǎn)！

        在數(shù)學(xué)之美中，有一章是關(guān)于布隆過濾器的講解，內(nèi)容如下。

        在字處理軟件中，一個英語單詞是否拼寫正確；在FBI中，一個嫌疑人的名字是否在嫌疑名單上；在網(wǎng)絡(luò)爬蟲里，一個網(wǎng)址是否已訪問過，等等。最直接的方法就是將集合中全部的元素存在計算機(jī)中，遇到一個新元素時，將它和集合中的元素之間比較。一般來說，計算機(jī)中的集合是用哈希表存儲的。好處是快速準(zhǔn)確，缺點(diǎn)是耗費(fèi)存儲空間。當(dāng)集合很小時，這個問題不明顯，當(dāng)集合規(guī)模巨大時，哈希表存儲效率低的問題就顯現(xiàn)出來了。如果使用哈希表存儲Email地址，每一億個Email地址，就需要1.6GB的內(nèi)存。為了解決哈希表的這個問題，就需要一種叫布隆過濾器的數(shù)學(xué)工具。所以，布隆過濾器是個數(shù)據(jù)工具。他的大小只需要哈希表1/8到1/4的大小就能解決同樣的問題。

        因此，布隆過濾器是一種數(shù)學(xué)工具。

二、布隆過濾器的原理

        布隆過濾器實(shí)際上是一個很長的二進(jìn)制向量和一系列隨機(jī)映射函數(shù)。我們通過電子郵件地址的例子來進(jìn)行說明。

        如果需要存儲一億個電子郵件地址，先建立一個16億二進(jìn)制(比特)，即2億字節(jié)的向量，然后將這16億個二進(jìn)制位全部清零。再對每一個電子郵件的地址X，用8個不同的隨機(jī)數(shù)產(chǎn)生器(F1, F2, F3 ..., F8)產(chǎn)生8個信息指紋(f1, f2, f3....., f8)。再用一個隨機(jī)數(shù)產(chǎn)生器G把這8個位置的二進(jìn)制全部設(shè)置為1。對這一億個電子郵件地址都進(jìn)行這樣的處理后，就產(chǎn)生了一個針對布隆過濾器。

        當(dāng)我們需要看一個可疑地址Y是否在黑名單中時，用8個相同的隨機(jī)數(shù)產(chǎn)生器(F1, F2, F3, ..., F8)對這個地址產(chǎn)生8個信息指紋s1, s2, s3, ... s8，然后將這8個指紋對應(yīng)到布隆過濾器的8個二進(jìn)制位，分別是t1, t2, ...., t8。如果Y在黑名單中，那么t1, t2, ...., t8對應(yīng)的8個二進(jìn)制數(shù)肯定是1。

三、布隆過濾器的優(yōu)缺點(diǎn)

        優(yōu)點(diǎn)： 快速，省空間

        缺點(diǎn)： 存在一定的誤識別率

四、leveldb中的布隆過濾器

        因為還沒有實(shí)際使用過leveldb，所以，個人在這里覺得，leveldb的布隆過濾器是在數(shù)據(jù)庫查找時，更快，更省空間。后面具體使用leveldb時，再來理解bloom。下面一起來看代碼分析

        BloomFilterPolicy是繼承自FilterPolicy的，關(guān)于FilterPolicy在后面的學(xué)習(xí)中再詳述，本節(jié)僅討論Bloom.cc。

        

        1. BloomFilterPolicy類

            1.1 BloomFilterPolicy

            構(gòu)造函數(shù)，主要是進(jìn)行初始化，然后確定需要多少個哈希函數(shù)

  explicit BloomFilterPolicy(int bits_per_key)
      : bits_per_key_(bits_per_key) {
    // We intentionally round down to reduce probing cost a little bit
    k_ = static_cast<size_t>(bits_per_key * 0.69);  // 0.69 =~ ln(2)
    if (k_ < 1) k_ = 1;
    if (k_ > 30) k_ = 30;		
  }

            1.2 Name

            返回bloom過濾器名稱

  virtual const char* Name() const {
    return "leveldb.BuiltinBloomFilter2";
  }

            1.3 CreateFilter

            創(chuàng)建BloomFilter，keys是需要存入的key， n是需要存入的個數(shù)， dst是BloomFilter的結(jié)果

            leveldb在最終的BloomFilter上加了一個k_，表示使用了多少個哈希函數(shù)，這樣在查詢時，就可以直接知道用來多少個哈希函數(shù)，而不需要重新用一個變量來記錄用來多少個哈希函數(shù)。

virtual void CreateFilter(const Slice* keys, int n, std::string* dst) const {
    // Compute bloom filter size (in both bits and bytes)
    size_t bits = n * bits_per_key_;		//所有需要創(chuàng)建的key的總位數(shù)

    // For small n, we can see a very high false positive rate.  Fix it
    // by enforcing a minimum bloom filter length.
    if (bits < 64) bits = 64;	//最小需要64位來保存

	//這兩行主要進(jìn)行字節(jié)對齊
    size_t bytes = (bits + 7) / 8;		//對所占的內(nèi)存進(jìn)行8字節(jié)對齊
    bits = bytes * 8;					//總共需要的位數(shù)
	
    const size_t init_size = dst->size();		
    dst->resize(init_size + bytes, 0);		//將所有的位都置為0
    dst->push_back(static_cast<char>(k_));  // Remember # of probes in filter， 將總的哈希函數(shù)個數(shù)存入最后
    char* array = &(*dst)[init_size];		
    for (int i = 0; i < n; i++) {
      // Use double-hashing to generate a sequence of hash values.
      // See analysis in [Kirsch,Mitzenmacher 2006].
      uint32_t h = BloomHash(keys[i]);
      const uint32_t delta = (h >> 17) | (h << 15);  // Rotate right 17 bits
      for (size_t j = 0; j < k_; j++) {
        const uint32_t bitpos = h % bits;			//獲取第一個數(shù)在bits中的位置
		// 將數(shù)據(jù)存入array中
		 /*
         bitpos/8計算元素在第幾個字節(jié)；
         (1 << (bitpos % 8))計算元素在字節(jié)的第幾位；
         例如：
         bitpos的值為3， 則元素在第一個字節(jié)的第三位上，那么這位上應(yīng)該賦值為1。
         bitpos的值為11，則元素在第二個字節(jié)的第三位上，那么這位上應(yīng)該賦值為1。
         為什么要用|=運(yùn)算，因為字節(jié)位上的值可能為1，那么新值賦值，還需要保留原來的值。
         */
        array[bitpos/8] |= (1 << (bitpos % 8));	
        h += delta;
      }
    }
  }

            1.4 KeyMayMatch

            查詢是否存在函數(shù)， key是需要查詢的， bloom_filter則是需要使用對比的過濾器

virtual bool KeyMayMatch(const Slice& key, const Slice& bloom_filter) const {
    const size_t len = bloom_filter.size();
    if (len < 2) return false;

    const char* array = bloom_filter.data();
    const size_t bits = (len - 1) * 8;

    // Use the encoded k so that we can read filters generated by
    // bloom filters created using different parameters.
    const size_t k = array[len-1];		//這里是使用過濾器尾部保存的哈希函數(shù)個數(shù)
    if (k > 30) {
		//保留短布隆過濾器
      // Reserved for potentially new encodings for short bloom filters.
      // Consider it a match.
      return true;
    }

    uint32_t h = BloomHash(key);		
    const uint32_t delta = (h >> 17) | (h << 15);  // Rotate right 17 bits
    for (size_t j = 0; j < k; j++) {
      const uint32_t bitpos = h % bits;		//查找
      if ((array[bitpos/8] & (1 << (bitpos % 8))) == 0) return false;		//判斷是否存在布隆過濾器中
      h += delta;
    }
    return true;
  }

        

            以上就是leveldb中bloom的主要代碼與分析，可以考慮，以后在自己寫代碼時，如果存在有大量數(shù)據(jù)需要查詢，讀取時，可以先通過布隆過濾器來看是否存在，然后再進(jìn)行讀取。而且布隆過濾器是一種數(shù)學(xué)方法，從側(cè)面說明了數(shù)學(xué)與計算機(jī)之間的緊密聯(lián)系，因此，有時間還是需要對數(shù)學(xué)進(jìn)行深入學(xué)習(xí)。

        更多分享，盡在交流QQ群：199546072

分享文章：leveldb登山之路——bloom
網(wǎng)站URL：http://www.chinadenli.net/article42/igpcec.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供ChatGPT、網(wǎng)站內(nèi)鏈、搜索引擎優(yōu)化、外貿(mào)建站、App開發(fā)、自適應(yīng)網(wǎng)站

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請盡快告知，我們將會在第一時間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場，如需處理請聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時需注明來源： 創(chuàng)新互聯(lián)