C++寻位映射的究极密码：哈希扩展

文章目录

• 1.位图
• • 1.1 位图的结构
  • 1.2 位图映射的比特位标记成1
  • 1.3 位图映射的比特位标记成0
  • 1.4 位图映射判断为1 or 0
  • 2.布隆过滤器
  • • 2.1 布隆过滤器的结构
    • 2.2 布隆过滤器的哈希函数
    • 2.3 布隆过滤器的插入
    • 2.4 布隆过滤器映射判断为true or false
    • 2.5 布隆过滤器的优缺点
    • 3.常见面试题
    • • 3.1 哈希切割
      • • 3.1.1 问题一
        • 3.1.2 问题二
        • 3.2 位图应用
        • • 3.2.1 问题一
          • 3.2.2 问题二
          • 3.2.3 问题三
          • 3.3 布隆过滤器应用
          • • 3.3.1 问题一
            • 3.3.2 问题二
            • 希望读者们多多三连支持
            • 小编会继续更新
            • 你们的鼓励就是我前进的动力！

              位图和布隆过滤器是基于哈希的一种常见应用，通常用来处理大体量数据，提升查找数据的效率

              1.位图

              给40亿个不重复的无符号整数，没排过序。给一个无符号整数，如何快速判断一个数是否在这40亿个数中?

              放在哈希表中去寻找？不，这并不现实，因为哈希表的存储也是需要空间消耗的，况且是 40 亿个数据，如此庞大的数据计算机一般是很难存储

              因此就诞生了位图的概念，位图简单来说就是把每个数按照哈希函数的计算，存储到每个比特位上。数据是否在给定的整形数据中，结果是在或者不在，刚好是两种状态，那么可以使用一个二进制比特位来代表数据是否存在的信息，如果二进制比特位为 1，代表存在，为 0 代表不存在

              

              1.1 位图的结构

              template
              class bitset
              {
              public:
              	bitset()
              	{
              		_a.resize(N / 32 + 1);
              	}
              private:
              	vector _a;
              };
              

              开辟一个 vector 数组 _a，这里我们以 int 作为位图的基本单位，那么就是把每个数据存储到 int 的比特位上

              🔥值得注意的是： resize 的时候无论如何都要加 1，比如 100 个数据，除以 32，等于 3，余 4，那么就需要多一个 int 空间来存储，不能说每次都卡好刚好 32 整除

              1.2 位图映射的比特位标记成1

              // x映射的那个标记成1
              void set(size_t x)
              {
              	size_t i = x / 32;
              	size_t j = x % 32;
              	_a[i] |= (1 
              	size_t i = x / 32;
              	size_t j = x % 32;
              	_a[i] &= (~(1 
              	size_t i = x / 32;
              	size_t j = x % 32;
              	return _a[i] & (1 
              private:
                  bitset
                  size_t operator()(const string& str)
                  {
                      size_t hash = 0;
                      for (auto ch : str)
                      {
                          hash = hash * 131 + ch;
                      }
                      //cout 
                  size_t operator()(const string& str)
                  {
                      size_t hash = 0;
                      for (size_t i = 0; i