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

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

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

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