从C语言到C++_32(哈希的应用)位图bitset+布隆过滤器+哈希切割（中)

#pragma once
 
#include <iostream>
#include <vector>
#include <bitset>
using namespace std;
 
namespace rtx
{
  template<size_t N>
  class bitset
  {
  public:
    bitset() //构造函数开空间，只需开N / 8 + 1
    {
      //_bits.resize(N / 8 + 1, 0); 
      _bits.resize((N >> 3) + 1, 0); // 即上面注释的，效率快一点点
    }
 
    void set(size_t x)
    {
      size_t i = x >> 3; // 将x映射在位图中的位置计算出来。
      size_t j = x % 8; // //映射到char中第几个比特位
 
      _bits[i] |= (1 << j); //将映射的比特位置1。
    }
 
    void reset(size_t x)
    {
      size_t i = x >> 3; // 将x映射在位图中的位置计算出来。
      size_t j = x % 8; // //映射到char中第几个比特位
 
      _bits[i] &= ~(1 << j); //将映射的比特位置0，这里~是按位取反，不要用到!逻辑取反
    }
 
    bool test(size_t x)
    {
      size_t i = x >> 3; // 将x映射在位图中的位置计算出来。
      size_t j = x % 8; // //映射到char中第几个比特位
 
      return _bits[i] & (1 << j); //与上除了对应比特位是1，其它位都是0的数，得到对应比特位bool值
    }
 
  protected:
    vector<char> _bits;
  };
 
  template<size_t N>
  class two_bitset
  {
  public:
    void set(size_t x)
    {
      bool inset1 = _bs1.test(x); // 测试当前状态
      bool inset2 = _bs2.test(x);
 
      if (inset1 == false && inset2 == false)
      {
        _bs2.set(x); // 00 -> 01
      }
      else if (inset1 == false && inset2 == true)
      {
        _bs1.set(x); // 01 -> 10
        _bs2.reset(x);
      }                // 10 是出现两次或两次以上，不用变
    }
 
    void print_once_num()
    {
      for (size_t i = 0; i < N; ++i)
      {
        if (_bs1.test(i) == false && _bs2.test(i) == true)
        {
          cout << i << endl; // 打印只出现一次的整数
        }
      }
    }
 
  protected:
    bitset<N> _bs1;
    bitset<N> _bs2;
    //std::bitset<N> _bs1;
    //std::bitset<N> _bs2;
  };
}

#include "BitSet.h"
 
void test_bitset()
{
  rtx::bitset<100> bs; //上面面试题开范围可以这样开：bitset<-1> bs1;
  bs.set(8);
  bs.set(9);
  bs.set(20);
 
  cout << bs.test(8) << endl;
  cout << bs.test(9) << endl;
  cout << bs.test(20) << endl;
  cout << bs.test(30) << endl << endl;
 
  bs.reset(8);
  bs.reset(20);
 
  cout << bs.test(8) << endl;
  cout << bs.test(9) << endl;
  cout << bs.test(20) << endl;
}
 
void test_two_bitset()
{
  int arr[] = { 3, 4, 5, 2, 3, 4, 4, 4, 4, 12, 77, 65, 44, 4, 44, 99, 33, 33, 33, 6, 5, 34, 12 };
 
  rtx::two_bitset<100> bs;
  for (const auto& e : arr)
  {
    bs.set(e);
  }
 
  bs.print_once_num();
}
 
int main()
{
  //test_bitset();
  test_two_bitset();
 
  return 0;
}

1.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;
  }
};
 
template<size_t N, class K = string, class Hash1 = HashBKDR, class Hash2 = HashAP, class Hash3 = HashDJB>
class BloomFilter // N表示准备要映射N个值
{
public:
 
protected:
  const static size_t _ratio = 5; // 根公式算出来，此时哈希函数是3个，所以m = 3n/ln2 约等于4.2 取5
  std::bitset<_ratio* N>* _bits = new std::bitset<_ratio * N>;
  // 库里的bit是放在栈上的，容易栈溢出，所以自己放到堆上（很挫）用自己写的就是放在堆上的
};

  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; // 可能存在误判
  }