高效处理大规模数据集的概率型数据结构—— 布隆过滤器 [C++入门]

void set(const K& key)
{
  size_t len = N * _X;
  size_t hash1 = Hash1()(key) % len;
  _bs.set(hash1);

  size_t hash2 = Hash2()(key) % len;
  _bs.set(hash2);

  size_t hash3 = Hash3()(key) % len;
  _bs.set(hash3);

}

bool contains(const K& key) const {
    size_t len = N * _X;
    size_t hash1 = Hash1()(key) % len;
    size_t hash2 = Hash2()(key) % len;
    size_t hash3 = Hash3()(key) % len;

    // 判断位数组中对应位置的值是否都为1
    if (_bs.test(hash1) && _bs.test(hash2) && _bs.test(hash3)) {
        return true;  // 可能存在于集合中
    }

    return false;  // 一定不存在于集合中
}

#include <vector>
#include <string>
#include <time.h>
using namespace std;

    //位图
template<size_t N>
class bitset
{
public:
  bitset()
  {
    _bits.resize(N / 8 + 1, 0);
  }

  void set(size_t x)
  {
    size_t i = x / 8;
    size_t j = x % 8;
    _bits[i] |= (1 << j);
  }

  void reset(size_t x)
  {
    size_t i = x / 8;
    size_t j = x % 8;

    _bits[i] &= ~(1 << j);
  }

  bool test(size_t x)
  {
    size_t i = x / 8;
    size_t j = x % 8;

    return _bits[i] & (1 << j);
  }

private:
  vector<char> _bits;
};


struct BKDRHash
{
  size_t operator()(const string& s)
  {
    size_t hash = 0;
    for (auto ch : s)
    {
      hash += ch;
      hash *= 31;
    }

    return hash;
  }
};

struct APHash
{
  size_t operator()(const string& s)
  {
    size_t hash = 0;
    for (long i = 0; i < s.size(); i++)
    {
      size_t ch = s[i];
      if ((i & 1) == 0)
      {
        hash ^= ((hash << 7) ^ ch ^ (hash >> 3));
      }
      else
      {
        hash ^= (~((hash << 11) ^ ch ^ (hash >> 5)));
      }
    }
    return hash;
  }
};


struct DJBHash
{
  size_t operator()(const string& s)
  {
    size_t hash = 5381;
    for (auto ch : s)
    {
      hash += (hash << 5) + ch;
    }
    return hash;
  }
};

// N最多会插入key数据的个数
template<size_t N,
  class K = string,
  class Hash1 = BKDRHash,
  class Hash2 = APHash,
  class Hash3 = DJBHash>
class BloomFilter            //布隆过滤器
{
public:
  void set(const K& key)
  {
    size_t len = N * _X;
    size_t hash1 = Hash1()(key) % len;
    _bs.set(hash1);

    size_t hash2 = Hash2()(key) % len;
    _bs.set(hash2);

    size_t hash3 = Hash3()(key) % len;
    _bs.set(hash3);

    //cout << hash1 << " " << hash2 << " " << hash3 << " " << endl << endl;
  }

  bool test(const K& key)
  {
    size_t len = N * _X;

    size_t hash1 = Hash1()(key) % len;
    if (!_bs.test(hash1))
    {
      return false;
    }

    size_t hash2 = Hash2()(key) % len;
    if (!_bs.test(hash2))
    {
      return false;
    }

    size_t hash3 = Hash3()(key) % len;
    if (!_bs.test(hash3))
    {
      return false;
    }

    // 在      不准确的，存在误判
    // 不在    准确的

    return true;
  }
private:
  static const size_t _X = 6;
  bitset<N* _X> _bs;
};