【C++】位图/布隆过滤器+海量数据处理

简介: 【C++】位图/布隆过滤器+海量数据处理

前言

题目


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


大多数人上来会想到这两种方法:1. 遍历,时间复杂度O(N)2. 排序(O(NlogN)),利用二分查找: logN

但是第一种效率太低了,需要一个一个遍历比对,第二种排序内存无法装得下40亿个整数数据啊!

可以发现问题是需要判断此无符号整数在不在集合中,我们可以用一个数对应一个比特位来标识,42亿个数据换算比特位进行存储,也就是需要0.5GB,512MB内存申请是没有压力的。


下面来学习一下位图法以及相关应用面试题和布隆过滤器知识。


一 位图


1.位图法介绍


位图法是一种利用每一位来存放某种状态的数据结构,适用于大规模数据的快速查找、判重、排序等。在位图法中,一个int类型的数据占用4个字节,即32个bit位,可以表示0-31的数是否存在。


位图申请内存


在内存中我们肯定是不能按照bit位来申请内存的,这不符合内存管理的机制,最小申请的内存也是1byte(字节),即8个bit位。所以在位图里面我们就开出来一个个的char,用每个char的比特位来直接对应数字。


意思是,在位图中,我们不能单独申请一个bit位来存放一个数字的状态,而是要申请一个char类型的数据,即8个bit位,然后用这8个bit位来表示8个数字是否存在。比如,如果我们要表示数字0-7是否存在,我们就可以申请一个char类型的数据a,然后用a的每一位来对应一个数字。如果a的第0位为1,表示数字0存在;如果a的第1位为1,表示数字1存在;以此类推。


2.位图实现的细节


我们这里讲解位图的三个主要功能函数:

  • set():置位函数,将指定的位设置为1
  • reset():复位函数,将指定位设置为0
  • test(): 访问函数,获取指定的位的值

对于set,想要让某一比特位变为1其他位不变,则可以用1按位或对应的比特位,那就只需让1向高位移动j位,然后用位图中对应的char进行按位或等即可。

这句话的意思是,如果我们想要把一个char类型的数据a的第j位设置为1,我们可以先把1左移j位,得到一个只有第j位为1其他位为0的数b,然后把a和b进行按位或运算,得到一个新的数c,这个数c就是把a的第j位设置为1后的结果。因为按位或运算的规则是,只要有一个为1就为1,所以a的其他位不会被改变,只有第j位会被设置为1。


例如,如果我们想要把a=0010 1000的第3位设置为1,我们可以先把1左移2位,得到b=0000 0100,然后把a和b进行按位或运算,得到c=0010 1000 | 0000 0100 = 0010 1100,这个数c就是把a的第2位设置为1后的结果。


对于reset,想要让某一比特位变为0其他位不变,则可以用0按位与对应的比特位,那就只需让1向高位移动j位,然后按位取反,最后用位图中对应的char进行按位与等即可。


对于test,我们可以让对应比特位按位与1,其他比特位按位与0,这样其他比特位都是0,如果测试的比特位是1,则结果是非0,那就是true,如果测试的比特位是0,则结果是0,那就是false。

// 非类型模板参数
template <size_t N>
class bitset
{
public:
  bitset()
  {
    _bits.resize(N / 8 + 1, 0);
    //可能开的比特位恰好满足数字的个数,也可能最多浪费7个比特位
    //_bits.resize(N << 3 + 1, 0);//位运算符优先级过低,这里先进行+运算,则结果和我们预想的不一致,发生错误。
  }
  void set(size_t x)
  {
    size_t i = x / 8;
    size_t j = x % 8;
    _bits[i] |= 1 << j;
  }
  void reset(size_t x)
  {
    size_t i = x / 8;
    size_t j = x % 8;
    _bits[i] &= ~(1 << j);
  }
  bool test(size_t x)
  {
    size_t i = x / 8;
    size_t j = x % 8;
    return _bits[i] & (1 << j);//这里不是&=,因为test不改变位图,只是判断一下而已
    //有些编译器bool值是四个字节,返回时会发生整型提升,高位补符号位,但这些都不重要,只要是非0就行,判断为真
    //我的编译器bool值是一个字节
  }
private:
  vector<char> _bits;
};

位图的应用

  1. 快速查找某个数据是否在一个集合中
  2. 排序 + 去重
  3. 求两个集合的交集、并集等
  4. 操作系统中磁盘块标记


二、布隆过滤器

1.布隆过滤器概念


布隆过滤器是一种概率型数据结构,可以用于判断一个元素是否可能存在于一个集合中,其优点是空间效率高,查询速度快,缺点是有一定的误判率和删除困难。

将哈希与位图结合,即布隆过滤器

布隆过滤器的应用场景有:


解决缓存穿透问题,即避免频繁查询数据库中不存在的数据

邮件过滤,即用布隆过滤器来存储黑名单邮件地址,过滤掉垃圾邮件

网页爬虫,即用布隆过滤器来记录已经爬取过的网址,避免重复爬取

新闻推荐,即用布隆过滤器来记录用户已经浏览过的新闻,避免重复推荐


2.布隆过滤器实现


布隆过滤器的原理是:


创建一个二进制位数组(bitmap)和一组哈希函数

当要添加一个元素时,用哈希函数计算出该元素在位数组中的多个位置,并将这些位置的值设为1

当要查询一个元素时,用哈希函数计算出该元素在位数组中的多个位置,并检查这些位置的值是否都为1,如果都为1,则认为该元素可能存在;如果有任何一个位置为0,则认为该元素一定不存在

当要删除一个元素时,无法直接将位数组中的对应位置设为0,因为这样可能会影响其他元素的判断,所以需要使用一些变形的布隆过滤器来支持删除操作

布隆过滤器的删除

如果采用计数方式来实现reset,也就是布隆过滤器的删除,会存在一些问题。比如你不小心将某一个字符串多次重复删除,此时计数会进行- -,但如果是0- -呢?有可能还会发生越界访问等问题。所以计数方式也有他的缺陷,最好不要强制增加布隆过滤器的reset操作。

struct BKDRHash
{
  size_t operator()(const string& key)
  {
    size_t hash = 0;
    for (auto ch : key)
    {
      hash *= 131;
      hash += ch;
    }
    return hash;
  }
};
struct APHash
{
  size_t operator()(const string& key)
  {
    unsigned int hash = 0;
    int i = 0;
    for (auto ch : key)
    {
      if ((i & 1) == 0)
      {
        hash ^= ((hash << 7) ^ (ch) ^ (hash >> 3));
      }
      else
      {
        hash ^= (~((hash << 11) ^ (ch) ^ (hash >> 5)));
      }
      ++i;
    }
    return hash;
  }
};
struct DJBHash
{
  size_t operator()(const string& key)
  {
    unsigned int hash = 5381;
    for (auto ch : key)
    {
      hash += (hash << 5) + ch;
    }
    return hash;
  }
};
struct JSHash
{
  size_t operator()(const string& s)
  {
    size_t hash = 1315423911;
    for (auto ch : s)
    {
      hash ^= ((hash << 5) + ch + (hash >> 2));
    }
    return hash;
  }
};
//布隆过滤器不仅可以存字符串,也可以存其他类型,只要最后能转换成整型完成取模映射就行,取模是比较常用的哈希函数
//平均存储一个值,开辟X个比特位
template <size_t N, size_t X = 8, class K = string,
class Hashfunc1 = BKDRHash, class Hashfunc2 = APHash, class Hashfunc3 = DJBHash, class Hashfunc4 = JSHash>
class BloomFilter
{
public:
  void set(const K& key)
  {
    size_t hash1 = Hashfunc1()(key) % (X * N);
    size_t hash2 = Hashfunc2()(key) % (X * N);
    size_t hash3 = Hashfunc3()(key) % (X * N);
    size_t hash4 = Hashfunc4()(key) % (X * N);
    _bs.set(hash1);
    _bs.set(hash2);
    _bs.set(hash3);
    _bs.set(hash4);
  }
  bool test(const K& key)
  {
    size_t hash1 = Hashfunc1()(key) % (X * N);
    if (!_bs.test(hash1))
    {
      return false;
    }
    size_t hash2 = Hashfunc2()(key) % (X * N);
    if (!_bs.test(hash2))
    {
      return false;
    }
    size_t hash3 = Hashfunc3()(key) % (X * N);
    if (!_bs.test(hash3))
    {
      return false;
    }
    size_t hash4 = Hashfunc4()(key) % (X * N);
    if (!_bs.test(hash4))
    {
      return false;
    }
    //上面判断不在的情况一定是准确的。
    return true;//这里可能会存在误判,多个哈希位置都和别的字符串冲突了
  }
private:
  std::bitset<N * X> _bs;//如果size_t类型×X过后,size_t类型存不下,也可以选择换long long类型
};


三、海量数据处理


1. 位图应用

经典面试题及解决方案:


1. 给定一个文件,包含40亿个不重复的无符号整数,给一个无符号整数,如何快速判断这个数是否在文件中?

解决方案:使用一个40亿位的位图,将文件中的每个整数映射到位图中,然后根据给定的整数在位图中查找即可。

2. 给定两个文件,分别包含100亿个整数,只有1G内存,如何找到两个文件的交集?

解决方案:使用哈希切分的方法,将两个文件分别按照哈希函数分成1000个小文件,然后对每一对小文件求交集即可。

3. 给定一个文件,包含100亿个整数,只有1G内存,设计算法找到出现次数不超过2次的所有整数?

解决方案:使用两个位图,分别记录每个整数出现的次数,如果出现0次,则两个位图都为0;如果出现1次,则第一个位图为1,第二个位图为0;如果出现2次或以上,则第一个位图为0,第二个位图为1。最后遍历两个位图,找出第一个位图为1且第二个位图为0的位置即可。


2. 哈希切割


问题

给一个超过100G大小的log file, log中存着IP地址, 设计算法找到出现次数最多的IP地址?

因为问题是100G大小的文件,肯定是无法加载到内存解决的,传统的KV模型如map来是不能解决的,我们这里采用哈希切割的思想来解决此问题。


哈希切割是一种将一个大文件利用哈希的原理,将其分割为若干个小文件的方法,相同数据分到同一个文件。


一种解决方案是:

上来先遍历子文件内容,将每个内容构造成键值对插入到map里面,如果map存不下,则在插入的过程中会出现内存不够的情况,insert会报错,那其实就是new结点失败,new失败是会抛异常的,我们只要捕获这个异常即可,此时说明这个子文件中大多是不同的IP,那么只需要递归哈希切分这个子文件即可。

如果map能够存的下,则正常统计出 出现次数最多的IP即可,无须进行其他任何操作。


e5c5f4a71b1143509f82d1e8428e3604.png


3. 布隆过滤器


给两个文件,分别有100亿个query,我们只有1G内存,如何找到两个文件交集?分别给出精确算法和近似算法。

精确算法:可以使用哈希切割的方法,将两个文件按照query的哈希值分割成若干个小文件,使得每个小文件的大小不超过内存限制。然后对每一对小文件,用散列表或者排序的方法找出其中的交集。最后将所有小文件的交集合并起来,就得到了两个大文件的交集。


31976818290c4bf8ac10bd59234e75e2.png


近似算法:可以使用布隆过滤器的方法,先将一个文件中的所有query插入到一个布隆过滤器中,然后遍历另一个文件中的query,用布隆过滤器检查是否可能存在于第一个文件中。如果可能存在,则加入到候选集合中。最后再对候选集合进行一次精确匹配,就得到了两个大文件的近似交集。


如何扩展BloomFilter使得它支持删除元素的操作?

一种方法是使用计数型布隆过滤器,即在每个位数组位置上不再存储一个比特位,而是存储一个计数器。当插入一个元素时,将其映射到的位数组位置上的计数器加一;当删除一个元素时,将其映射到的位数组位置上的计数器减一。这样就可以实现删除操作,但是会增加空间开销和计算复杂度 。

另一种方法是使用双重布隆过滤器,即维护两个布隆过滤器,一个用于存储插入的元素(A),一个用于存储删除的元素(B)。当插入一个元素时,将其加入到A中;当删除一个元素时,将其加入到B中。当查询一个元素时,先检查它是否在A中,如果不在,则认为不存在;如果在,则再检查它是否在B中,如果在,则认为已经删除;如果不在,则认为存在。这样也可以实现删除操作,但是会增加误判率和维护成本 。


结束


目录
打赏
0
1
1
0
18
分享
相关文章
【C++航海王:追寻罗杰的编程之路】哈希的应用——位图 | 布隆过滤器
【C++航海王:追寻罗杰的编程之路】哈希的应用——位图 | 布隆过滤器
45 1
从C语言到C++_32(哈希的应用)位图bitset+布隆过滤器+哈希切割(下)
从C语言到C++_32(哈希的应用)位图bitset+布隆过滤器+哈希切割
54 1
从C语言到C++_32(哈希的应用)位图bitset+布隆过滤器+哈希切割(中)
从C语言到C++_32(哈希的应用)位图bitset+布隆过滤器+哈希切割
65 1
|
8月前
|
从C语言到C++_32(哈希的应用)位图bitset+布隆过滤器+哈希切割(上)
从C语言到C++_32(哈希的应用)位图bitset+布隆过滤器+哈希切割
63 1
【C++】哈希(位图、布隆过滤器)
【C++】哈希(位图、布隆过滤器)
|
3天前
|
【C++面向对象——类与对象】Computer类(头歌实践教学平台习题)【合集】
声明一个简单的Computer类,含有数据成员芯片(cpu)、内存(ram)、光驱(cdrom)等等,以及两个公有成员函数run、stop。只能在类的内部访问。这是一种数据隐藏的机制,用于保护类的数据不被外部随意修改。根据提示,在右侧编辑器补充代码,平台会对你编写的代码进行测试。成员可以在派生类(继承该类的子类)中访问。成员,在类的外部不能直接访问。可以在类的外部直接访问。为了完成本关任务,你需要掌握。
35 18
【C++面向对象——类与对象】CPU类(头歌实践教学平台习题)【合集】
声明一个CPU类,包含等级(rank)、频率(frequency)、电压(voltage)等属性,以及两个公有成员函数run、stop。根据提示,在右侧编辑器补充代码,平台会对你编写的代码进行测试。​ 相关知识 类的声明和使用。 类的声明和对象的声明。 构造函数和析构函数的执行。 一、类的声明和使用 1.类的声明基础 在C++中,类是创建对象的蓝图。类的声明定义了类的成员,包括数据成员(变量)和成员函数(方法)。一个简单的类声明示例如下: classMyClass{ public: int
30 13
【C++面向对象——继承与派生】派生类的应用(头歌实践教学平台习题)【合集】
本实验旨在学习类的继承关系、不同继承方式下的访问控制及利用虚基类解决二义性问题。主要内容包括: 1. **类的继承关系基础概念**:介绍继承的定义及声明派生类的语法。 2. **不同继承方式下对基类成员的访问控制**:详细说明`public`、`private`和`protected`继承方式对基类成员的访问权限影响。 3. **利用虚基类解决二义性问题**:解释多继承中可能出现的二义性及其解决方案——虚基类。 实验任务要求从`people`类派生出`student`、`teacher`、`graduate`和`TA`类,添加特定属性并测试这些类的功能。最终通过创建教师和助教实例,验证代码
20 5
【C++面向对象——群体类和群体数据的组织】实现含排序功能的数组类(头歌实践教学平台习题)【合集】
1. **相关排序和查找算法的原理**:介绍直接插入排序、直接选择排序、冒泡排序和顺序查找的基本原理及其实现代码。 2. **C++ 类与成员函数的定义**:讲解如何定义`Array`类,包括类的声明和实现,以及成员函数的定义与调用。 3. **数组作为类的成员变量的处理**:探讨内存管理和正确访问数组元素的方法,确保在类中正确使用动态分配的数组。 4. **函数参数传递与返回值处理**:解释排序和查找函数的参数传递方式及返回值处理,确保函数功能正确实现。 通过掌握这些知识,可以顺利地将排序和查找算法封装到`Array`类中,并进行测试验证。编程要求是在右侧编辑器补充代码以实现三种排序算法
18 5
AI助理

你好,我是AI助理

可以解答问题、推荐解决方案等