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

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

1. 位图

腾讯面试题:给40亿个不重复的无符号整数,没排过序。给一个无符号整数,

如何快速判断一个数是否在这40亿个数中。

根据我们现有的知识,该如何处理上面的问题呢?

1. 遍历,时间复杂度O(N)

2. 排序(O(NlogN)),利用二分查找: logN

3. 红黑树 / 哈希表。


还有很多其他的方式,但是这些方式都行不通,


先来口算一下40亿的无符号整数占用多大的内存空间:


1024字节 = 1KB


1024KB = 1MB


1024MB = 1GB


10 0000 0000(九个零 -> 10亿)


10亿个字节 ≈ 1GB。

40亿个字节 ≈ 4GB。

40亿个无符号整数 ≈ 16GB。

而一般的内存根本放不下这么多的数据,无论是上面的哪种方法,都需要存放数据本身,即使是用数组来存放都需要16GB,如果用红黑树(有三叉链,颜色)需要大的内存,哈希表虽然少一点,但是仍然有next指针,还是存放不下。


问题中只要求判断一个数是否在这40亿个数据中,所以可以不存放数据本。

可以采用下面的位图的方式来处理这个问题。

1.1 位图的概念

位图:就是用每一比特位来存放某种状态,适用于海量数据,数据无重复的场景。

通常是用来判断某个数据存不存在的。1字节 = 8 bit。

       位图就是哈希结构,这里我们用直接定址法,1表示在,0表示不在,就能很好处理这个面试题。对于40亿个数据,至少需要40亿个比特位才能标识它们的状态。

       对于这种情况一般选择2^32个比特位:2^32 = 42亿9千多万,40亿个数据完全可以表示的下,此时相当于一个数组,有2^32个元素,每个元素是一个比特位。

使用位图方式占用的内存就小多了:

1个字节等于8个比特位,8 = 2^3,1024 = 2^10。

  • 2^32个比特位 = 2^29个字节 = 2^19KB = 2^9MB = 512MB = 0.5GB
  • 从最开始需要16GB内存空间直接下降到了需要0.5GB的空间。

但是在语言层面上并没有比特位的数组。

  • 2^32个比特位可以用2^27个int类型的数组来表示。
  • 也可以用2^29个char类型的数组来表示。

随便例举一些数字,如上图所示,这里采用char类型为数组的基本单位。


数据范围是1到22,所以需要3个char类型的变量。

下标为1的比特位表示数字1的存在情况,下标为18的比特位表示数字18是否存在。

上图中,存在3个char类的变量,一共24个比特位,整体标号的话是0~23。

0~7使用第一个char类型的变量。

8~15使用第二个char类型变量。

16~23使用第三个char类型变量。

这3个char类型的变量是用一个数组实现的,即char [3]。


这3个char类型变量的地址从左到右依次升高。


每个char类型中比特位却是:低的比特位在右,高的比特位在左。

这是由我们的使用习惯决定的,比如3用二进制表示就是11,6用二进制表示就是100,


低比特位在右,高比特位在左。

不使用int类型数组的原因:(用int也可以)

我们知道,数据在内存中的存储是有大小端的,如果使用int类型的数组,上图就变成:

       一个int就是4个字节,8个比特位只需要一个int类型的数据就够了,并且还多出8个比特位。假设上图中是小端存储方式,并且是处理完的位图,此时将这份代码换到了大端存储方式的机器上:


       此时位图结构就变成了下图中所示,原本表示数字0~7的8个比特位放在了高地址处,变成了表示24 ~31的8个比特位。

e1d70fd31df346149eaac4d0ce4eccfe.png

        原本在小端机上的程序在大端机上极有可能出现BUG。而采用char类型数组就不用考虑大小端的问题,因为一个char类型就是一个字节,每个char都是从低地址到高地址排列。


       上面是在内存中存储的真实样子,我们在使用的时候无需知道位图在内存中样子。这种方式就是一种哈希思想,将数据直接映射到位图上。


如何确定一个数据映射在位图的哪个比特位呢?以整数18为例说明:


       8映射在位图的下标为2的八个比特位中的某一个,也就是第三个char类型变量。具体映射在下标为2的char类型变量中下标为2的比特位上,也就是在这个char类型中第三个比特位上。


确定映射到char类型变量的下标:18 / 8 = 2。

确定映射到比特位的下标:18 % 8 = 2。

       可以根据上面的图确定一下,发现和我们算出来的结果是一样的。求其他数据的映射位置时,只需要将18换成对应数据即可。

1.2 位图的实现

BitSet.h:

#pragma once
 
#include <iostream>
#include <vector>
using namespace std;
 
namespace rtx
{
  template<size_t N>
  class bitset //构造函数开空间,只需开N / 8 + 1
  {
  public:
    bitset()
    {
      //_bits.resize(N / 8 + 1, 0); 
      _bits.resize((N >> 3) + 1, 0); // 即上面注释的,效率快一点点
    }
 
  protected:
    vector<char> _bits;
  };
}

使用非类型模板参数,该参数用来指定位图比特位的个数。

底层使用的是vector,vector中存char类型变量。

在构造函数中需要指定vector的大小,否则vector的大小是0,一个比特位也没有。


非类型模板参数N指定是比特位的个数,而构造函数开辟的是char类型变量的个数,所以需要N / 8。

由于N / 8的结果不是整数时会取整而抛弃小数部分,所以需要在N /8 后再加1,也就是再增加 8 个比特位来确保位图够用。

       CPU在计算除法的时候,其实是很复杂的,而进行移位运算就很简单。N / 8相当于N右移3位。所以我们使用移位运算来代替除法来提高效率,需要注意的是,加法的优先级比移位运算高,所以必须给(N>>3)加括号,否则就是成了 N>>4了。


下面来写bitset的接口函数:

set();  该接口的作用是将x映射在位图中的比特位置1,表示该数据存在。

  • 首先将x映射在位图中的位置计算出来。
  • 然后将映射的比特位置1。

怎么将对应的比特位置1?这就要我们以前C语言学的知识:

如上图所示,要将一个char类型中的8个比特位的某一个位置一而不影响其他位,就需要或等一个只有那个位是1其他位都是0的char类型,这样一个char类型可以通过1左移固定位数得到。

    void set(size_t x)
    {
      size_t i = x >> 3; // 将x映射在位图中的位置计算出来。
      size_t j = x % 8; // //映射到char中第几个比特位
 
      _bits[i] |= (1 << j); //将映射的比特位置1。
    }

现在来实现reset();该接口的作用是将x映射在位图中的比特位置0,表示该数据不存在。

和set的思路一样同样先计算处x所在位图中的位置。 然后再进行置0。

怎么将对应比特位置0?上面是或等,这里就要与等一个数。


       这里与等一个只有那个位是0其他位都是1的char类型变量这样一个char类型可以通过1左移固定位数(就是set或等的那个数),然后按位取反得到。

    void reset(size_t x)
    {
      size_t i = x >> 3; // 将x映射在位图中的位置计算出来。
      size_t j = x % 8; // //映射到char中第几个比特位
 
      _bits[i] &= ~(1 << j); //将映射的比特位置0,这里~是按位取反,不要用到!逻辑取反
    }


现在来实现test(); 该接口的作用是在位图中查找数据x是否存在。

  • 首先计算出x映射在位图中的位置。
  • 然后看该比特位是0还是1。


       如上图所示,判断某个比特位是1还是0,需要与一个只有这个位是1其他位都是0的char类型变量,如果这个bit是0,那么与以后的结果就是0,对应的bool值flase,如果这个bit是1,那么与以后的结果就不是0,对应的bool值是true。


bool值本质上是4个字节的整形,所以这里涉及到了整形提升,但是并没有影响。

如果与以后的结果是0,整形提升后的结果仍然是0,bool值就是false。

如果与以后的结果非0,即使符号位是1,整形提升和的结果仍然非0,bool的值就是true。

    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值
    }

位图主要的接口就是这三个,下面来测试一下:

#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;
}
 
int main()
{
  test_bitset();
 
  return 0;
}


STL中的位图:

在STL库中,是存在位图的,但是用的比较少。

上面实现的这3个操作也是有的,当然它还提供了其他的接口,这里就不介绍了。

从C语言到C++_32(哈希的应用)位图bitset+布隆过滤器+哈希切割(中):https://developer.aliyun.com/article/1522346

目录
相关文章
|
3天前
|
C语言 C++ 编译器
【C++语言】冲突-C语言:输入输出、缺省参数、引用、内联函数
【C++语言】冲突-C语言:输入输出、缺省参数、引用、内联函数
【C++语言】冲突-C语言:输入输出、缺省参数、引用、内联函数
|
3天前
|
C语言 C++
【C++语言】冲突-C语言:命名空间
【C++语言】冲突-C语言:命名空间
|
10天前
|
存储 C++ 容器
c++实现哈希桶
这篇文章回顾了闭散列的概念,指出在数据冲突时,闭散列会自动寻找后续未占用的位置插入数据。然而,这种方法可能导致某些元素状态变为删除,从而在查找时产生问题。为了解决这个问题,文章介绍了拉链法(哈希桶)作为改进策略。拉链法在每个哈希表位置上维护一个链表,冲突的数据挂载在相应位置的链表上。文章详细描述了拉链法的插入、查找和删除操作,并提供了相关代码示例。在插入过程中,当负载因子达到1时,哈希表会进行扩容,同时避免了频繁创建和销毁节点,提高了效率。最后,文章通过测试代码展示了拉链法的正确性。
10 0
|
11天前
|
程序员 C语言 C++
C语言学习记录——动态内存习题(经典的笔试题)、C/C++中程序内存区域划分
C语言学习记录——动态内存习题(经典的笔试题)、C/C++中程序内存区域划分
10 0
|
19天前
|
安全 Linux 编译器
从C语言到C++_40(多线程相关)C++线程接口+线程安全问题加锁(shared_ptr+STL+单例)(下)
从C语言到C++_40(多线程相关)C++线程接口+线程安全问题加锁(shared_ptr+STL+单例)
22 0
|
19天前
|
安全 C语言 C++
从C语言到C++_40(多线程相关)C++线程接口+线程安全问题加锁(shared_ptr+STL+单例)(中)
从C语言到C++_40(多线程相关)C++线程接口+线程安全问题加锁(shared_ptr+STL+单例)
20 0
|
19天前
|
Linux 调度 C语言
从C语言到C++_40(多线程相关)C++线程接口+线程安全问题加锁(shared_ptr+STL+单例)(上)
从C语言到C++_40(多线程相关)C++线程接口+线程安全问题加锁(shared_ptr+STL+单例)
23 0
|
19天前
|
存储 算法 C语言
从C语言到C++_39(C++笔试面试题)next_permutation刷力扣
从C语言到C++_39(C++笔试面试题)next_permutation刷力扣
14 5
|
19天前
|
存储 算法 C语言
从C语言到C++_38(C++的IO流+空间适配器)STL六大组件联系(下)
从C语言到C++_38(C++的IO流+空间适配器)STL六大组件联系
28 5
|
2天前
|
编译器 C++
【C++初阶】—— 类和对象 (下)
【C++初阶】—— 类和对象 (下)