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

一、位圖

1.位圖的概念

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

2.位圖的面試題

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

• 遍歷，時間復雜度O(N)。
• 排序(O(NlogN))，利用二分查找: logN。
• 位圖解決。
  

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

3.位圖的實現(xiàn)

#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);
  }

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

 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億個數(shù)據(jù)，判斷某個數(shù)是否在數(shù)據(jù)中
  //bs.reset(-1);
  //bs.reset(pow(2, 32));
 }
}

4.位圖的應用

• 快速查找某個整形數(shù)據(jù)是否在一個集合中。
• 排序。
• 求兩個集合的交集、并集等。
• 操作系統(tǒng)中磁盤塊標記。

二、布隆過濾器

1.布隆過濾器的提出

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

• 用哈希表存儲用戶記錄，缺點：浪費空間。
• 用位圖存儲用戶記錄，缺點：不能處理哈希沖突。
• 將哈希與位圖結合，即布隆過濾器。

2.布隆過濾器的概念

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

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; //魔數(shù)
   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要自己配置仿函數(shù)
 template<class K,class Hash1=HashStr1,class Hash2=HashStr2,class Hash3=HashStr3>
 class bloomfilter
 {
 public:
  bloomfilter(size_t num)
   :_bs(5*num)
   , _N(5*num)
  {

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

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

4.布隆過濾器的查找

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

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

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

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

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

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

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

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

5.布隆過濾器的刪除

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

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

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

缺陷：

• 無法確認元素是否真正在布隆過濾器中。
• 存在計數(shù)回繞。

6.布隆過濾器的優(yōu)點和缺點

• 優(yōu)點：節(jié)省空間，高效，可以標注存儲任意類型
• 缺點;存在誤判，不支持刪除

位圖

• 優(yōu)點：節(jié)省空間
• 缺點：只能處理整形

三、海量數(shù)據(jù)面試題

1.哈希切割

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

2.位圖應用

①給定100億個整數(shù)，設計算法找到只出現(xiàn)一次的整數(shù)？

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

• 方案1:將其中一個文件1的整數(shù)映射到一個位圖中，讀取另外一個文件2中的整數(shù)，判斷在在不在位圖，在就是交集。消耗50OM內(nèi)存
• 方案2:將文件1的整數(shù)映射到位圖1中，將文件2的整數(shù)映射到位圖2中，然后將兩個位圖中的數(shù)按位與。與之后為l1的位就是交集。消耗內(nèi)存1G。

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

• 本題跟上面的第1題思路是一樣的
• 本題找的不超過2次的，也就是要找出現(xiàn)1次和2次的
• 本題還是用兩個位表示一個數(shù)，分為出現(xiàn)0次00表示，出現(xiàn)1次的01表示―出現(xiàn)2次的10表示出現(xiàn)3次及3次以上的用11表示

3.布隆過濾器

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

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

到此這篇關于C++哈希應用的位圖和布隆過濾器的文章就介紹到這了,更多相關C++哈希應用位圖與布隆過濾器內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關文章希望大家以后多多支持腳本之家！

最新評論