C++哈希應(yīng)用的位圖和布隆過濾器

一、位圖

1.位圖的概念

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

2.位圖的面試題

給40億個(gè)不重復(fù)的無符號(hào)整數(shù)，沒排過序。給一個(gè)無符號(hào)整數(shù)，如何快速判斷一個(gè)數(shù)是否在這40億個(gè)數(shù)中?！掘v訊】

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

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

3.位圖的實(shí)現(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位的比特位設(shè)置為1
  void set(size_t x)
  {
   size_t index = x / 32;           //映射出x在第幾個(gè)整形
   size_t pos = x % 32;             //映射出x在整形的第幾個(gè)位置
   _bits[index] |= (1 << pos);
   _num++;
  }

  //將x位的比特位設(shè)置為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);
  }

  //位圖中比特位的總個(gè)數(shù)
  size_t size()
  {
   return _num;
  }
 private:
  std::vector<int> _bits;
  size_t _num;            //映射存儲(chǔ)了多少個(gè)數(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億個(gè)數(shù)據(jù)，判斷某個(gè)數(shù)是否在數(shù)據(jù)中
  //bs.reset(-1);
  //bs.reset(pow(2, 32));
 }
}

4.位圖的應(yīng)用

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

二、布隆過濾器

1.布隆過濾器的提出

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

• 用哈希表存儲(chǔ)用戶記錄，缺點(diǎn)：浪費(fèi)空間。
• 用位圖存儲(chǔ)用戶記錄，缺點(diǎn)：不能處理哈希沖突。
• 將哈希與位圖結(jié)合，即布隆過濾器。

2.布隆過濾器的概念

布隆過濾器是由布?。˙urton Howard Bloom）在1970年提出的 一種緊湊型的、比較巧妙的概率型數(shù)據(jù)結(jié)構(gòu)，特點(diǎn)是高效地插入和查詢，可以用來告訴你 “某樣?xùn)|西一定不存在或者可能存在”，它是用多個(gè)哈希函數(shù)，將一個(gè)數(shù)據(jù)映射到位圖結(jié)構(gòu)中。此種方式不僅可以提升查詢效率，也可以節(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;
  }
 };

 //假設(shè)布隆過濾器元素類型為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);   //三個(gè)位置都設(shè)置為1
   _bs.set(index2);
   _bs.set(index3);
  }
}

4.布隆過濾器的查找

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

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;  //但是這里也不一定是真的在，還有可能存在誤判

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

注意：布隆過濾器如果說某個(gè)元素不存在時(shí)，該元素一定不存在，如果該元素存在時(shí)，該元素可能存在，因?yàn)橛行┕：瘮?shù)存在一定的誤判。

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

5.布隆過濾器的刪除

布隆過濾器不能直接支持刪除工作，因?yàn)樵趧h除一個(gè)元素時(shí)，可能會(huì)影響其他元素。

比如：刪除上圖中"tencent"元素，如果直接將該元素所對(duì)應(yīng)的二進(jìn)制比特位置0，“baidu”元素也被刪除了，因?yàn)檫@兩個(gè)元素在多個(gè)哈希函數(shù)計(jì)算出的比特位上剛好有重疊。

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

缺陷：

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

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

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

位圖

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

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

1.哈希切割

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

2.位圖應(yīng)用

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

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

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

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

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

3.布隆過濾器

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

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

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

最新評(píng)論