C++中位圖和布隆過濾器的示例分析

這篇文章主要介紹了C++中位圖和布隆過濾器的示例分析，具有一定借鑒價值，感興趣的朋友可以參考下，希望大家閱讀完這篇文章之后大有收獲，下面讓小編帶著大家一起了解一下。

C++哈希應用的位圖和布隆過濾器

一、位圖

1.位圖的概念

所謂位圖，就是用每一位來存放某種狀態，適用于海量數據，數據無重復的場景。通常是用來判斷某個數據存不存在的。

2.位圖的面試題

給40億個不重復的無符號整數，沒排過序。給一個無符號整數，如何快速判斷一個數是否在這40億個數中。【騰訊】

• 遍歷，時間復雜度O(N)。

• 排序(O(NlogN))，利用二分查找: logN。

• 位圖解決。
  

數據是否在給定的整形數據中，結果是在或者不在，剛好是兩種狀態，那么可以使用一個二進制比特位來代表數據是否存在的信息，如果二進制比特位為1，代表存在，為0代表不存在。比如：

3.位圖的實現

#include<iostream>
#include<vector>
#include<math.h>
namespace yyw
{
 class bitset
 {
 public:
  bitset(size_t N)
  {
   _bits.resize(N / 32 + 1, 0);
   _num = 0;
  }

  //將x位的比特位設置為1
  void set(size_t x)
  {
   size_t index = x / 32;           //映射出x在第幾個整形
   size_t pos = x % 32;             //映射出x在整形的第幾個位置
   _bits[index] |= (1 << pos);
   _num++;
  }

  //將x位的比特位設置為0
  void reset(size_t x)
  {
   size_t index = x / 32;
   size_t pos = x % 32;
   _bits[index] &= ~(1 << pos);
   _num--;
  }

  //判斷x位是否在不在
  bool test(size_t x)
  {
   size_t index = x / 32;
   size_t pos = x % 32;

   return _bits[index] & (1 << pos);
  }

  //位圖中比特位的總個數
  size_t size()
  {
   return _num;
  }
 private:
  std::vector<int> _bits;
  size_t _num;            //映射存儲了多少個數據
 };

 void tes_bitset()
 {
  bitset bs(100);
  bs.set(99);
  bs.set(98);
  bs.set(97);

  bs.set(10);

  for (size_t i = 0; i < 100; i++)
  {
   printf("[%d]:%d\n", i, bs.test(i));
  }

  //40億個數據，判斷某個數是否在數據中
  //bs.reset(-1);
  //bs.reset(pow(2, 32));
 }
}

4.位圖的應用

• 快速查找某個整形數據是否在一個集合中。

• 排序。

• 求兩個集合的交集、并集等。

• 操作系統中磁盤塊標記。

二、布隆過濾器

1.布隆過濾器的提出

我們在使用新聞客戶端看新聞時，它會給我們不停地推薦新的內容，它每次推薦時要去重，去掉那些已經看過的內容。問題來了，新聞客戶端推薦系統如何實現推送去重的？ 用服務器記錄了用戶看過的所有歷史記錄，當推薦系統推薦新聞時會從每個用戶的歷史記錄里進行篩選，過濾掉那些已經存在的記錄。 如何快速查找呢？

• 用哈希表存儲用戶記錄，缺點：浪費空間。

• 用位圖存儲用戶記錄，缺點：不能處理哈希沖突。

• 將哈希與位圖結合，即布隆過濾器。

2.布隆過濾器的概念

布隆過濾器是由布隆（Burton Howard Bloom）在1970年提出的 一種緊湊型的、比較巧妙的概率型數據結構，特點是高效地插入和查詢，可以用來告訴你 “某樣東西一定不存在或者可能存在”，它是用多個哈希函數，將一個數據映射到位圖結構中。此種方式不僅可以提升查詢效率，也可以節省大量的內存空間。

3.布隆過濾器的插入

布隆過濾器底層是位圖：

struct HashStr1
 {
  //BKDR1
  size_t operator()(const std::string& str)
  {
   size_t hash = 0;
   for (size_t i = 0; i < str.size(); i++)
   {
    hash *= 131;
    hash += str[i];
   }
   return hash;
  }
 };

 struct HashStr2
 {
  //RSHash
  size_t operator()(const std::string& str)
  {
   size_t hash = 0;
   size_t magic = 63689; //魔數
   for (size_t i = 0; i < str.size();i++)
   {
    hash *= magic;
    hash += str[i];
    magic *= 378551;
   }
   return hash;
  }
 };

 struct HashStr3
 {
  //SDBHash
  size_t operator()(const std::string& str)
  {
   size_t hash = 0;
   for (size_t i = 0; i < str.size(); i++)
   {
    hash *= 65599;
    hash += str[i];
   }
   return hash;
  }
 };

 //假設布隆過濾器元素類型為K，如果類型為K要自己配置仿函數
 template<class K,class Hash2=HashStr1,class Hash3=HashStr2,class Hash4=HashStr3>
 class bloomfilter
 {
 public:
  bloomfilter(size_t num)
   :_bs(5*num)
   , _N(5*num)
  {

  }
  void set(const K& key)
  {
   size_t index1 = Hash2()(key) % _N;
   size_t index2 = Hash3()(key) % _N;
   size_t index3 = Hash4()(key) % _N;

   _bs.set(index1);   //三個位置都設置為1
   _bs.set(index2);
   _bs.set(index3);
  }
}

4.布隆過濾器的查找

布隆過濾器的思想是將一個元素用多個哈希函數映射到一個位圖中，因此被映射到的位置的比特位一定為1。所以可以按照以下方式進行查找：分別計算每個哈希值對應的比特位置存儲的是否為零，只要有一個為零，代表該元素一定不在哈希表中，否則可能在哈希表中。

bool test(const K& key)
  {
   size_t index1 = Hash2()(key) % _N;
   if (_bs.test(index1) == false)
   {
    return false;
   }

   size_t index2 = Hash2()(key) % _N;
   if (_bs.test(index2) == false)
   {
    return false;
   }

   size_t index3 = Hash4()(key) % _N;
   if (_bs.test(index3) == false)
   {
    return false;
   }

   return true;  //但是這里也不一定是真的在，還有可能存在誤判

   //判斷不在是正確的，判斷在可能存在誤判
  }

注意：布隆過濾器如果說某個元素不存在時，該元素一定不存在，如果該元素存在時，該元素可能存在，因為有些哈希函數存在一定的誤判。

比如：在布隆過濾器中查找"alibaba"時，假設3個哈希函數計算的哈希值為：1、3、7，剛好和其他元素的比特位重疊，此時布隆過濾器告訴該元素存在，但實該元素是不存在的。

5.布隆過濾器的刪除

布隆過濾器不能直接支持刪除工作，因為在刪除一個元素時，可能會影響其他元素。

比如：刪除上圖中"tencent"元素，如果直接將該元素所對應的二進制比特位置0，“baidu”元素也被刪除了，因為這兩個元素在多個哈希函數計算出的比特位上剛好有重疊。

一種支持刪除的方法：將布隆過濾器中的每個比特位擴展成一個小的計數器，插入元素時給k個計數器(k個哈希函數計算出的哈希地址)加一，刪除元素時，給k個計數器減一，通過多占用幾倍存儲空間的代價來增加刪除操作。

缺陷：

• 無法確認元素是否真正在布隆過濾器中。

• 存在計數回繞。

6.布隆過濾器的優點和缺點

• 優點：節省空間，高效，可以標注存儲任意類型

• 缺點;存在誤判，不支持刪除

位圖

• 優點：節省空間

• 缺點：只能處理整形

三、海量數據面試題

1.哈希切割

①給一個超過100G大小的log file, log中存著IP地址, 設計算法找到出現次數最多的IP地址？ 與上題條件相同，如何找到top K的IP？如何直接用Linux系統命令實現？

2.位圖應用

①給定100億個整數，設計算法找到只出現一次的整數？

②給兩個文件，分別有100億個整數，我們只有1G內存，如何找到兩個文件交集？

• 方案1:將其中一個文件1的整數映射到一個位圖中，讀取另外一個文件2中的整數，判斷在在不在位圖，在就是交集。消耗50OM內存

• 方案2:將文件1的整數映射到位圖1中，將文件2的整數映射到位圖2中，然后將兩個位圖中的數按位與。與之后為l1的位就是交集。消耗內存1G。

③位圖應用變形：1個文件有100億個int，1G內存，設計算法找到出現次數不超過2次的所有整數？

• 本題跟上面的第1題思路是一樣的

• 本題找的不超過2次的，也就是要找出現1次和2次的

• 本題還是用兩個位表示一個數，分為出現0次00表示，出現1次的01表示―出現2次的10表示出現3次及3次以上的用11表示

3.布隆過濾器

①給兩個文件，分別有100億個query，我們只有1G內存，如何找到兩個文件交集？分別給出精確算法和近似算法?

②如何擴展BloomFilter使得它支持刪除元素的操作?

感謝你能夠認真閱讀完這篇文章，希望小編分享的“C++中位圖和布隆過濾器的示例分析”這篇文章對大家有幫助，同時也希望大家多多支持億速云，關注億速云行業資訊頻道，更多相關知識等著你來學習!