【C++航海王：追寻罗杰的编程之路】哈希的应用——位图 | 布隆过滤器

#define _CRT_SECURE_NO_WARNINGS 1
 
#include <iostream>
#include <vector>
using namespace std;
 
class bitset
{
public:
  bitset(size_t bitCount)
    : _bit((bitCount >> 5) + 1), _bitCount(bitCount)
  {}
 
  // 将which比特位置1
  void set(size_t which)
  {
    if (which > _bitCount)
      return;
 
    size_t index = (which >> 5);
    size_t pos = which % 32;
    _bit[index] |= (1 << pos);
  }
 
  // 将which比特位置0
  void reset(size_t which)
  {
    if (which > _bitCount)
      return;
 
    size_t index = (which >> 5);
    size_t pos = which % 32;
    _bit[index] &= ~(1 << pos);
  }
 
  // 检测位图中which是否为1
  bool test(size_t which)
  {
    if (which > _bitCount)
      return false;
 
    size_t index = (which >> 5);
    size_t pos = which % 32;
 
    return _bit[index] & (1 << pos);
  }
  // 获取位图中比特位的总个数
  size_t size()const 
  { 
    return _bitCount; 
  }
 
  // 位图中比特为1的个数
  size_t Count()const
  {
    int bitCnttable[256] = {
   0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4, 1, 2, 2, 3, 2, 3, 3, 4, 2,
   3, 3, 4, 3, 4, 4, 5, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 2, 3,
   3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3,
   4, 3, 4, 4, 5, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 2, 3, 3, 4,
   3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5,
   6, 6, 7, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 2, 3, 3, 4, 3, 4,
   4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5,
   6, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 2, 3, 3, 4, 3, 4, 4, 5,
   3, 4, 4, 5, 4, 5, 5, 6, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 3,
   4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 4, 5, 5, 6, 5, 6, 6, 7, 5, 6,
   6, 7, 6, 7, 7, 8 };
 
    size_t size = _bit.size();
    size_t count = 0;
    for (size_t i = 0; i < size; ++i)
    {
      int value = _bit[i];
      int j = 0;
      while (j < sizeof(_bit[0]))
      {
        unsigned char c = value;
        count += bitCnttable[c];
        ++j;
        value >>= 8;
      }
    }
    return count;
  }
 
private:
  vector<int> _bit;
  size_t _bitCount;
};

#define _CRT_SECURE_NO_WARNINGS 1
 
#include <iostream>
using namespace std;
 
struct BKDRHash
{
  size_t operator()(const string& s)
  {
    // BKDR
    size_t value = 0;
    for (auto ch : s)
    {
      value *= 31;
      value += ch;
    }
 
    return value;
  }
};
 
struct APHash
{
  size_t operator()(const string& s)
  {
    size_t hash = 0;
    for (long i = 0; i < s.size(); i++)
    {
      if ((i & 1) == 0)
      {
        hash ^= ((hash << 7) ^ s[i] ^ (hash >> 3));
      }
      else
      {
        hash ^= (~((hash << 11) ^ s[i] ^ (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;
  }
};
 
template<size_t N,
  size_t X = 5,
  class K = string,
  class HashFunc1 = BKDRHash,
  class HashFunc2 = APHash,
  class HashFunc3 = DJBHash>
  class BloomFilter
{
 
public:
  void Set(const K& key)
  {
    size_t len = X * N;
    size_t index1 = HashFunc1()(key) % len;
    size_t index2 = HashFunc2()(key) % len;
    size_t index3 = HashFunc3()(key) % len;
 
    /* cout << index1 << endl;
    cout << index2 << endl;
    cout << index3 << endl<<endl;*/
 
    _bs.set(index1);
    _bs.set(index2);
    _bs.set(index3);
  }
 
  bool Test(const K& key)
  {
    size_t len = X * N;
    size_t index1 = HashFunc1()(key) % len;
    if (_bs.test(index1) == false)
      return false;
 
    size_t index2 = HashFunc2()(key) % len;
    if (_bs.test(index2) == false)
      return false;
 
    size_t index3 = HashFunc3()(key) % len;
    if (_bs.test(index3) == false)
      return false;
 
    return true; // 存在误判的
  }
 
  // 不支持删除，删除可能会影响其他值。
  void Reset(const K& key);
 
private:
  bitset<X* N> _bs;
};