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

零、前言

一、位图

1、位图概念

2、位图接口的介绍以及实现

3、位图的应用

二、布隆过滤器

1、布隆过滤器概念和介绍

2、布隆过滤器的操作及实现

3、布隆过滤器的分析

三、海量数据处理

零、前言

本章主要讲解C++中对哈希的应用有关方面的内容，位图，布隆，海量数据处理

一、位图

1、位图概念

位图概念：

位图其实就是哈希的变形，同样通过映射来处理数据，只不过位图本身并不存储数据，而是存储标记

通过一个比特位来标记这个数据是否存在，1代表存在，0代表不存在

位图通常情况下用在数据量庞大，且数据不重复的情景下判断某个数据是否存在

相关面试题描述：

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

注意：

遍历时间复杂度O(N)；排序(O(NlogN))利用二分查找: logN；这两种方式除了效率不够高，还有个问题是内存无法完全同时加载这给40亿个不重复的无符号整数

10亿个整数为40亿字节，而10亿字节为1G，所以40亿个整数需要16G大小空间

位图解决方案：

数据是否在给定的整形数据中，结果是在或者不在，刚好是两种状态

那么可以使用一个二进制比特位来代表数据是否存在的信息，如果二进制比特位为1，代表存在，为0代表不存在

示图：小端平台上

2、位图接口的介绍以及实现

bitset中常用的成员函数如下：

成员函数 功能

set 设置指定位或所有位

reset 清空指定位或所有位

flip 反转指定位或所有位

test 获取指定位的状态

count 获取被设置位的个数

size 获取可以容纳的位的个数

any 如果有任何一个位被设置则返回true

none 如果没有位被设置则返回true

all 如果所有位都被设置则返回true

使用示例：

#include <iostream>

#include <bitset>

using namespace std;

int main()

{

bitset<8> bs;

bs.set(2); //设置第2位

bs.set(4); //设置第4位

cout << bs << endl; //00010100

bs.flip(); //反转所有位

cout << bs << endl; //11101011

cout << bs.count() << endl; //6

cout << bs.test(3) << endl; //1

bs.reset(0); //清空第0位

cout << bs << endl; //11101010

bs.flip(7); //反转第7位

cout << bs << endl; //01101010

bs.reset(); //清空所有位

cout << bs.none() << endl; //1

bs.set(); //设置所有位

cout << bs.all() << endl; //1

return 0;

}

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

注：使用成员函数set、reset、flip时，若指定了某一位则操作该位，若未指定位则操作所有位

位图的简单实现：

对于底层来说一个位代表一个数的映射，那么我们以char类型来开辟对应需要空间，同时用vector进行管理

对于开辟空间，一个char类型有8个位，所以需要个数/8即为需要开辟的大小，但是整数相除为向下取整，所以需要我们多开一个空间出来

实现代码：

template<size_t N>

class bitset

{

public:

bitset()

{

_bits.resize(N / 8 + 1,0);//开辟空间并置为0

//_bits.resize((N >> 3) + 1,0);

}

bool test(size_t x)

{

size_t i = x / 8;//处于的该数组的第几个空间

size_t j = x % 8;//处于的该空间的第几个比特位

return _bits[i] & (1 << j);

}

void set(size_t x)

{

size_t i = x / 8;//处于的该数组的第几个空间

size_t j = x % 8;//处于的该空间的第几个比特位

_bits[i] |= (1 << j);//该位置置为1

}

void reset(size_t x)

{

size_t i = x / 8;//处于的该数组的第几个空间

size_t j = x % 8;//处于的该空间的第几个比特位

_bits[i] &= (~(1 << j));//该位置置为0

}

private:

vector<char> _bits;

};

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

3、位图的应用

快速查找某个数据是否在一个集合中

排序

求两个集合的交集、并集等

操作系统中磁盘块标记

二、布隆过滤器

1、布隆过滤器概念和介绍

布隆过滤器的提出：

我们在使用新闻客户端看新闻时，它会给我们不停地推荐新的内容，它每次推荐时要去重，去掉那些已经看过的内容。问题来了，新闻客户端推荐系统如何实现推送去重的？

用服务器记录了用户看过的所有历史记录，当推荐系统推荐新闻时会从每个用户的历史记录里进行筛选，过滤掉那些已经存在的记录

如何快速查找：

用哈希表存储用户记录，缺点：浪费空间

用位图存储用户记录，缺点：不能处理哈希冲突

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

布隆过滤器概念：

布隆过滤器是由布隆（Burton Howard Bloom）在1970年提出的 一种紧凑型的、比较巧妙的概率型数据结构

特点是高效地插入和查询，可以用来告诉你 “某样东西一定不存在或者可能存在”

它是用多个哈希函数，将一个数据映射到位图结构中的不同位置上，不仅可以提升查询效率，也可以节省大量的内存空间