天堂在线中文,亚洲丰满熟妇毛片在线播放,久久精品国产一区二区三区不卡

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

一、位圖

1.位圖的概念

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

2.位圖的面試題

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

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

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

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

3.位圖的實現

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

#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.布隆過濾器的提出

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

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

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

2.布隆過濾器的概念

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

3.布隆過濾器的插入

布隆過濾器底層是位圖：

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

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 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.布隆過濾器的查找

布隆過濾器的思想是將一個元素用多個哈希函數映射到一個位圖中，因此被映射到的位置的比特位一定為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;  //但是這里也不一定是真的在，還有可能存在誤判

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

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

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