【C++高阶(六)】哈希的应用--位图&布隆过滤器

template<size_t N>//N是所有数中的最大值
class bit_set
{
public:
  bit_set()
  {
    _bit.resize(N / 8 + 1, 0);
  }
  void set(size_t x)//将第x位变成1
  {}
  void reset(size_t x)//将第x位由1变0
  {}
  bool test(size_t x)
  {}
private:
  vector<char> _bit;
};

template<size_t N>//N是所有数中的最大值
class bit_set
{
public:
  bit_set()
  {
    _bit.resize(N / 8 + 1, 0);
  }
  void set(size_t x)//将第x位变成1
  {
    //x/8->在第几个char
    //x%8->在这个char的第几个比特位
    size_t i = x / 8;
    size_t j = x % 8;
    _bit[i] |= (1 << j);//将x对应的比特位变成1
  }
  void reset(size_t x)
  {
    size_t i = x / 8;
    size_t j = x % 8;
    _bit[i] &= ~(1 << j);//将x对应的比特位变成0
  }
  bool test(size_t x)
  {
    size_t i = x / 8;
    size_t j = x % 8;
    return _bit[i] & (1 << j);
  }
private:
  vector<char> _bit;
};

//三个不同的字符串映射成整数的函数
struct HashBKDR
{
  size_t operator()(const string& key)
  {
    size_t val = 0;
    for (auto ch : key)
    {
      val *= 131;
      val += ch;
    }
    return val;
  }
};
struct HashAP
{
  size_t operator()(const string& key)
  {
    size_t hash = 0;
    for (size_t i = 0; i < key.size(); i++)
    {
      if ((i & 1) == 0)
        hash ^= ((hash << 7) ^ key[i] ^ (hash >> 3));
      else
        hash ^= (~((hash << 11) ^ key[i] ^ (hash >> 5)));
    }
    return hash;
  }
};
struct HashDJB
{
  size_t operator()(const string& key)
  {
    size_t hash = 5381;
    for (auto ch : key)
      hash += (hash << 5) + ch;
    return hash;
  }
};

// N表示准备要映射N个值
template<size_t N,
  class K = string, class Hash1 = HashBKDR, class Hash2 = HashAP, class Hash3 = HashDJB>
class Bloom_Filter
{
public:
  void set(const K& key)
  {
    size_t hash1 = Hash1()(key) % (_ratio * N);
    _bits->set(hash1);
    size_t hash2 = Hash2()(key) % (_ratio * N);
    _bits->set(hash2);
    size_t hash3 = Hash3()(key) % (_ratio * N);
    _bits->set(hash3);
  }
  bool test(const K& key)
  {
    size_t hash1 = Hash1()(key) % (_ratio * N);
    if (!_bits->test(hash1))
      return false; // 准确的
    size_t hash2 = Hash2()(key) % (_ratio * N);
    if (!_bits->test(hash2))
      return false; // 准确的
    size_t hash3 = Hash3()(key) % (_ratio * N);
    if (!_bits->test(hash3))
      return false;  // 准确的
    return true; // 可能存在误判
  }
  void reset(const K& key)//支持删除操作的话,可能会把其他数据对应的映射值删除
  {}
private:
  const static size_t _ratio = 5;//开的空间越大,误判率越小
  std::bitset<_ratio* N>* _bits = new std::bitset<_ratio * N>;//标准库中的位图是在栈上开辟的静态数组,过大会栈溢出
};