一、什么是布隆過(guò)濾器

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

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

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

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

二、布隆過(guò)濾器的原理

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

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

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

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

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

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

四、leveldb中的布隆過(guò)濾器

        因?yàn)檫€沒(méi)有實(shí)際使用過(guò)leveldb，所以，個(gè)人在這里覺(jué)得，leveldb的布隆過(guò)濾器是在數(shù)據(jù)庫(kù)查找時(shí)，更快，更省空間。后面具體使用leveldb時(shí)，再來(lái)理解bloom。下面一起來(lái)看代碼分析

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

        

        1. BloomFilterPolicy類

            1.1 BloomFilterPolicy

            構(gòu)造函數(shù)，主要是進(jìn)行初始化，然后確定需要多少個(gè)哈希函數(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過(guò)濾器名稱

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

            1.3 CreateFilter

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

            leveldb在最終的BloomFilter上加了一個(gè)k_，表示使用了多少個(gè)哈希函數(shù)，這樣在查詢時(shí)，就可以直接知道用來(lái)多少個(gè)哈希函數(shù)，而不需要重新用一個(gè)變量來(lái)記錄用來(lái)多少個(gè)哈希函數(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_;		//所有需要?jiǎng)?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位來(lái)保存

	//這兩行主要進(jìn)行字節(jié)對(duì)齊
    size_t bytes = (bits + 7) / 8;		//對(duì)所占的內(nèi)存進(jìn)行8字節(jié)對(duì)齊
    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ù)個(gè)數(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;			//獲取第一個(gè)數(shù)在bits中的位置
		// 將數(shù)據(jù)存入array中
		 /*
         bitpos/8計(jì)算元素在第幾個(gè)字節(jié)；
         (1 << (bitpos % 8))計(jì)算元素在字節(jié)的第幾位；
         例如：
         bitpos的值為3， 則元素在第一個(gè)字節(jié)的第三位上，那么這位上應(yīng)該賦值為1。
         bitpos的值為11，則元素在第二個(gè)字節(jié)的第三位上，那么這位上應(yīng)該賦值為1。
         為什么要用|=運(yùn)算，因?yàn)樽止?jié)位上的值可能為1，那么新值賦值，還需要保留原來(lái)的值。
         */
        array[bitpos/8] |= (1 << (bitpos % 8));	
        h += delta;
      }
    }
  }

            1.4 KeyMayMatch

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

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];		//這里是使用過(guò)濾器尾部保存的哈希函數(shù)個(gè)數(shù)
    if (k > 30) {
		//保留短布隆過(guò)濾器
      // 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;		//判斷是否存在布隆過(guò)濾器中
      h += delta;
    }
    return true;
  }

        

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

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

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

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

廣告

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