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

曾经终败给现在 2024-04-22 12:13 84阅读 0赞

## 一.什么是位图 ##

我们知道数据的最小存储位是比特（bite），每个比特位只能是0或1，我们用1和0来表示在或不在，或是其它类型的状态信息，这种结构称作位图。

当我们面对海量数据时，使用 int 类型来存储数据，会需要巨大的空间，这样成本就太高了，这种时候可以用位图来解决，它可以大幅降低所需空间。

--------------------

## 二.位图的模拟实现 ##

![3da1e1c3f66843f4b52483fef3f608cd.png][]

库里面是有位图这个结构的，可以看到，有一个非类型模板参数，它决定位图的大小。

接下来让我们来模拟实现简易的位图，同样采用非类型模板参数的形式 。

### 思路 ###

位图是需要访问比特位的，但是我们没有任何一个类型的大小是一个比特位，所以我们可以开一个整型数组（当然char也行），一个整型就表示32个比特位，这样我们数组的大小只需要开 N/32+1  就行了。

### 接口 set ###

![2a2f70336aca47ed9a5f022d27858d63.png][]

set 的作用是把该比特位设置成1。

给我们一个数 x ，我们该如何把 x 映射到位图中呢，并把映射到的这个位置改成1（并且不改变其它位置）呢？

*  首先一个字节是32个比特位，先除上个32就能知道 x 在哪个字节。
 *  然后在模上32就能知道是在哪个比特位
 *  比如说80，80/32=2，80%32=16，那么80就在第2个字节的第16个比特位。

接下来使用位运算的知识将这个位置设置成1，并不影响其他位置。

我们知道按位或运算是只要有1就是1，所以按位或上一个0，并不影响原来的值，按位或上一个1结果为1。

![1dc8c70ce5eb4815b2cc3645bb712d16.png][]

void set(size_t x)
    {
    	size_t i = x / 32;   //求出在哪个字节
    	size_t j = x % 32;   //求出在哪个比特位
    
    	bs[i] |= (1 << j);   
    }

### 接口 reset ###

![ad461f8696fc4e6ca9a63fafdf274bf3.png][]

reset 是把该位置的比特位设置成 0 。

这就要用到按位与了。

对于按位与运算，只要有0就是0，按位与上一个1并不影响原来的值。

![f5c41f6a87a84ae7a425bf254031f87a.png][]

void reset(size_t x)
    {
    	size_t i = x / 32;
    	size_t j = x % 32;
    
    	bs[i] &= (~(1 << j));
    }

### 接口 test ###

![d23cf2b7852b46b4b88fdfd63b6d6cd7.png][]

判断一个位置的比特位是 0 还是 1

这里同样还是用按位与，但要注意是对某一个位置按位与上一个1，不用像 reset 一样取个反。

bool test(size_t x)
    {
    	size_t i = x / 32;
    	size_t j = x % 32;
    
    	return bc[i] &(1 << j);   //注意不能写成 &=
    }

--------------------

## 三.位图完整代码 ##

template<size_t N>
    	class Bitset
    	{
    	public:
    		Bitset()
    		{
    			bs.resize(N / 32 + 1);
    		}
    
    		void set(size_t x)
    		{
    			size_t i = x / 32;
    			size_t j = x % 32;
    
    			bs[i] |= (1 << j);
    		}
    
    		void reset(size_t x)
    		{
    			size_t i = x / 32;
    			size_t j = x % 32;
    
    			bs[i] &= (~(1 << j));
    		}
    
    		bool test(size_t x)
    		{
    			size_t i = x / 32;
    			size_t j = x % 32;
    
    			return bs[i] &(1 << j);
    		}
    
    	private:
    		vector<int> bs;
    	};

--------------------

## 四.布隆过滤器 ##

### 概念 ###

*  布隆过滤器是由布隆提出的 一种紧凑型的、比较巧妙的概率型数据结构；
 *  特点是高效地插入和查询，可以用来告诉你 “某样东西一定不存在或者可能存在”；
 *  它是用多个哈希函数，将一个数据映射到位图结构中。此种方式不仅可以提升查询效率，也可以节省大量的内存空间

![cab14bbffe8940958cefb8771a504d40.png][]

### 布隆过滤器的插入 ###

布隆过滤器的插入是利用多个哈希函数，将一个数据映射到一个位图的多个位置上，生活中，要插入的数据类型大多是字符串型，所以本篇文章将以插入字符串为例模拟实现布隆过滤器。

[各种字符串哈希函数][Link 1]

void set(const K& key)
    		{
    			size_t hash1 = Hash1(key) % N;
    			bs.set(hash1);
    			size_t hash2 = Hash2(key) % N;
    			bs.set(hash2);
    			size_t hash3 = Hash3(key) % N;
    			bs.set(hash3);
    		}

### 布隆过滤器的查找 ###

分别计算每个哈希值对应的比特位置存储的是否为零，只要有一个为零，代表该元素一定不在哈希表中，否则可能在哈希表中。

注意：布隆过滤器如果说某个元素不存在时，该元素一定不存在，如果该元素存在时，该元素可  
能存在，因为有些哈希函数存在一定的误判。

所以布隆过滤器在实际应用中起到一个过滤器的作用，如果在的话还要到数据库里继续查找，防止误判，提高了效率；如果不在，就一定不存在，就不需要到数据库里取寻找。

### 布隆过滤器的删除 ###

一般情况下布隆过滤器是不支持删除的，因为布隆过滤器存储的时候是一对多，如果删除一个位置，那么很可能会影响其它的数据。

如果非要删除的话，只能再加一个位图来表示每个比特位为1的个数。

## 五.布隆过滤器完整代码 ##

struct BKDRHash
    {
    	size_t operator()(const string& str)
    	{
    		size_t hash = 0;
    		for (auto ch : str)
    		{
    			hash = hash * 131 + ch;     
    		}
    		return hash;
    	}
    };
    
    struct APHash
    {
    	size_t operator()(const string& str)
    	{
    		size_t hash = 0;
    		size_t ch;
    		for (long i = 0; i < str.size(); i++)
    		{
    			ch = str[i];
    			if ((i & 1) == 0)
    			{
    				hash ^= ((hash << 7) ^ ch ^ (hash >> 3));
    			}
    			else
    			{
    				hash ^= (~((hash << 11) ^ ch ^ (hash >> 5)));
    			}
    		}
    		return hash;
    	}
    };
    
    struct DJBHash
    {
    	size_t operator()(const string& str)
    	{
    		if (str.size() == 0)
    			return 0;
    		size_t hash = 5381;
    		for(auto ch:str)
    		{
    			hash += (hash << 5) + ch;
    		}
    		return hash;
    	}
    };
    
    template<size_t N,
    			class K=string,
    			class Hash1= BKDRHash,
    			class Hash2= APHash,
    			class Hash3= DJBHash>
    	class BloomFilter
    	{
    	public:
    		void set(const K& key)
    		{
    			size_t hash1 = Hash1(key) % N;
    			bs.set(hash1);
    			size_t hash2 = Hash2(key) % N;
    			bs.set(hash2);
    			size_t hash3 = Hash3(key) % N;
    			bs.set(hash3);
    		}
    
    		bool test(const K& key)
    		{
    			size_t hash1 = Hash1(key) % N;
    			
    			size_t hash2 = Hash2(key) % N;
    			
    			size_t hash3 = Hash3(key) % N;
    			
    			return bs.test(hash1)&& bs.test(hash2)&& bs.test(hash2)
    		}
    	private:
    		Bitset<N> bs;
    	};

## 六.海量数据处理面试题 ##

### 哈希切割 ###

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

对于大文件，我们可以分成多个小文件，那该怎那么分呢？

首先一定不能均分，均分的效率极低，我们可以利用哈希表的原理来分。

1.  假设一个query的大小是30byte，100亿个query即为300G（1G大约是10亿byte），那么我们把它切成1000个文件，每个文件的大小为300MB左右。
2.  读取文件数据，用哈希函数对1000取模，取模的结果相同的进同一号文件

![414991e2b9464910baa42e7db249f401.png][]

如何找交集？

*  读取 Ai 小文件的数据放到set里 ，在读取 Bi 文件的数据，如果在就是交集并且删掉。

如果哈希冲突太多，会导致一个小文件的大小超过1个G，这该如何解决？

此时分两种情况：

1.  相同数据太多
2.  哈希冲突太多

解决方案：

1.  先把Ai的query读到一个set，如果set的 insert 报错抛异常(bad\_alloc)，那么就说明是大多数query都是冲突。如果能够全部读出来，insert 到set里面，那么说明Ai有大量相同的query
2.  如果抛异常，说明有大量冲突，再换一个哈希函数，再进行二次切分。

### 位图应用 ###

### 1. 给定100亿个整数，设计算法找到只出现一次的整数？ ###

这里有100亿个整数，如果用set，红黑树这一类的结构，空间必定不够。

所以就需要用位图解决。

但是一个比特位只能表示两种状态，怎么找到只出现一次的整数呢？

可以用两个链表，这样0和1两两组合就有四种状态：00 01 11 10

我们可以用：

*  00表示出现0次
 *  01表示出现1次
 *  11或10表示出现次数大于1次

可以复用 Bitset 来创建一个有两个位图的双位图结构。

template<size_t N>
    	class TwoBitset
    	{
    	public:
    		void set(size_t x)
    		{
    			if (bs1.test(x) == 0 && bs2.test(x) == 0)  //00
    				bs2.set(x);  //01
    			else if (bs1.test(x) == 0 && bs2.test(x) == 1) //01
    				bs1.set(x);  //11
    			else
    				;
    		}
    
    		bool test(size_t x)
    		{
    			if (bs1.test(x) == 0 && bs2.test(x) == 1)
    				return true;
    			else
    				return false;
    		}
    	private:
    		Bitset<N> bs1;
    		Bitset<N> bs2;
    	};

### 2. 给两个文件，分别有100亿个整数，我们只有1G内存，如何找到两个文件交集？ ###

还是和前面一样使用双位图，如果只把一个文件的数据映射到一个位图，另一个文件的数据用来遍历找交集的话，就会出现重复项。

把两个文件的数据分别映射到两个位图中，由于整形数据是有范围的，实际上在100亿个整数中，有非常多重复的，当两个文件的数据映射完成后，遍历所有整数，如果在两个位图中都在，那么这个数就是一个交集。这要做的好处是不会找到重复的数。

### 3. 位图应用变形：1个文件有100亿个int，1G内存，设计算法找到出现次数不超过2次的所有整数 ###

这题还是和第一题是一样的，只不过是找不超过2次的整数，可以：

*  00 表示出现 0 次
 *  01 表示出现 1 次
 *  10 表示出现 2 次
 *  11 表示出现 2 次以上

--------------------

> **??本篇文章到此就结束了， 若有错误或是建议的话，欢迎小伙伴们指出；?️?**
> 
> **??希望小伙伴们能支持支持博主啊，你们的支持对我很重要哦；??**
> 
> **??谢谢你的阅读。??**

[3da1e1c3f66843f4b52483fef3f608cd.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/22/62b90d1bd43347aabb43caf359e0b6cb.png
[2a2f70336aca47ed9a5f022d27858d63.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/22/67bd387395c240b2a05358854c0f0142.png
[1dc8c70ce5eb4815b2cc3645bb712d16.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/22/039016ed2b3d4d2c85bc8a4afe909f46.png
[ad461f8696fc4e6ca9a63fafdf274bf3.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/22/de1d9162e8294aff8fe7f58a86dad815.png
[f5c41f6a87a84ae7a425bf254031f87a.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/22/b0faa19f0ac94875b0b7c43f5efcf42b.png
[d23cf2b7852b46b4b88fdfd63b6d6cd7.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/22/3e685e1b5e8840fb907c7977b461dba3.png
[cab14bbffe8940958cefb8771a504d40.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/22/914d897703b84b51bbaf986646ea773d.png
[Link 1]: https://www.cnblogs.com/-clq/archive/2012/05/31/2528153.html
[414991e2b9464910baa42e7db249f401.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/22/6bb5ebe9271b4096813a4b5407a87de5.png