[C++] 位图-布隆过滤器-海量数据的处理问题

淩亂°似流年 2022-09-09 06:02 131阅读 0赞

### 目录 ###

*  1. 哈希切割
 *   *  1.1 平均分隔(不可取)
     *  1.2 哈希切割(正确)
     *  1.3 找到Top-K的IP
 *  2. 位图
 *  2.1 问题
 *   *  2.2 为什么使用位图
     *  2.3 使用过程
     *  2.4 位图的应用
     *  2.5 位图相关问题解决
 *  3. 布隆过滤器
 *   *  3.1 为什么使用布隆过滤器？
     *  3.2 原理
     *  3.3 插入、查找与删除
     *   *  3.3.1 插入
         *  3.3.2 查找
         *  3.3.3 删除
     *  3.4 优缺点
     *  3.5 问题
 *  4. 代码模拟
 *   *  4.1 位图
     *  4.2 布隆过滤器

# 1. 哈希切割 #

现在有一个100G的大文件，文件里面存的是IP地址，如何设计一个算法找到次数最多的IP地址？

**思路**: 将大文件拆分成众多小文件

## 1.1 平均分隔(不可取) ##

将100G的文件平均切分成100份，每份都是1G，逐个文件统计IP地址出现的次数。  
  但是统计出来次数准确吗，有的IP地址可能存放在不同的文件中，那么统计出具体的一个IP地址出现的次数，还是要对所有切分的文件进行统计，与直接操作大文件无异。所以这种方式不可取。

## 1.2 哈希切割(正确) ##

上面的方法，因为最后统计出来的IP地址可能跨文件，有没有办法让同一个IP地址只会在同一个文件中出现？  
  **哈希切割**，使用哈希桶的思想对文件进行切割。

**过程**：

> 1.预估要分割的份数  
> 2.创建预估出份数的文件  
> 3.将源文件中的IP地址**按照哈希的思想**进行份文件存放。  
>   `ip % 文件总分数 = 要放入的文件`  
> 4.逐个文件统计每个IP出现的次数，因为第3步之后，IP对应的整形数据已经分散到每一个文件中了，并且相同的IP地址在同一个文件中存放着。

## 1.3 找到Top-K的IP ##

> 1.统计次数，已经借助哈希分隔将每个IP出现的次数统计出来了。  
> 2.再借助优先级队列<ip, 次数>，来找到TOP-K。优先级队列元素比较时，需要按照IP地址的次数来进行比较，创建小堆。用<ip，次数>依次对堆顶元素比较，如果出现次数比堆顶次数多，就是用新IP来替换堆顶。  
> 3.优先级队列中剩余的k个元素就是最终需要出现次数最多的元素。

# 2. 位图 #

数据是否在给定的整形数据中，结果是在或者不在，刚好是两种状态，那么可以**使用一个二进制比特位来代表数据是否存在**的信息，如果二进制比特位为1代表存在，为0代表不存在。  
  所谓位图，就是用每一位来存放某种状态，适用于海量数据，数据无重复的场景。通常是用来判断某个数据存不存在的。

# 2.1 问题 #

在现实生活中，大数据的处理十分的常见；比如说，给40亿个不重复的无符号整数，没排过序，如何快速判断一个数是否在这40亿个数中？

解决这个问题，可以使用最快的查找算法哈希，但是必须要将所有数据一次性加载到内存中，40亿个数据，需要多少的内存，40亿*4字节 = 4G*4 = 16G;这种方式容易超出内存限制，无法使用。  
  也可以使用遍历，复杂度为O(n)数据量大时，将会非常耗时，不好用。  
  使用**位图**，用一个比特位来表示一个数据是否存在，一个字节可以存放8个数据的信息，大大减少少了内存的使用量。

## 2.2 为什么使用位图 ##

位图使用一个比特位表示一个数据存在与否，所以一个字节就可以表示8个数据，大大较少了，内存的使用量，对于在大量数据中，查找数据一般都是位图。  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5ZOm5ZOm5ZG15ZG1_size_20_color_FFFFFF_t_70_g_se_x_16_pic_center]

## 2.3 使用过程 ##

> 1.计算需要多少字节(即需要多少个比特位)。
> 
>  *  位图中需要将\[min, max\]逐个范围当中所有数据保存起来
>  *  根据数据范围确定使用多少个比特位. eg: \[1~22\]，使用3个字节就可以全部存储
> 
> 2.将集合中的数据往位图中进行映射
> 
>  *  映射到哪个字节: `data / 8`
>  *  映射到该字节的哪一位 `data % 8`
> 
> 3.根据位图进行查找，`data / 8`找到具体字节 `data % 8` 找到在字节的哪一位存储

## 2.4 位图的应用 ##

**快速查找某个数据是否在某一集合中**  
**排序 + 去重**  
**求两个文件的交集、并集**  
**操作系统中磁盘块标记**

## 2.5 位图相关问题解决 ##

**1. 40亿个整型数据，提供一个数据data，设计一个算法快速找出data是否在集合中**

> 1.预算需要多少空间进行元素的存储
> 
>  *  题目没有明确给出数据范围，只能认为所有数据都可能出现
>  *  所以40亿个数据都出现了，一个整型占用4个字节，所以范围就是`0 ~ 2^32`
>  *  ![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5ZOm5ZOm5ZG15ZG1_size_20_color_FFFFFF_t_70_g_se_x_16_pic_center 1]
> 
> 2.将40亿个整型数据向位图中进行映射，读取文件，只需要将文件IO一次，就可以将文件中的所有数据使用位图表示起来
> 
>  *  映射到哪个字节: `data / 8`
>  *  映射到该字节的哪一位 `data % 8`
> 
> 3.检测用户所给的数据是否存在，根据映射关系判断对应比特的状态

**变形应用**

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

**分析**

> 1.数据状态的分析：
> 
>  *  不存在
>  *  只存在一次
>  *  存在多次
> 
> 2.不能使用常规位图，因为常规位图一位只能表示两种状态，可以使用**两个比特位**表示一个数据的状态。
> 
>  *  00: 数据没有出现
>  *  01: 数据出现了一次
>  *  10: 数据出现多次
>  *  11: 不适用
> 
> 3.题目中没有具体给定数据范围，默认就是无符号整型的所有数据，假设整型占4个字节，数据总的个数为 2^32 ,数据只能在这个范围中，因为整数所能表示的范围只有这么大，100亿远远超出了这个整数能表示的范围，所以数据一定存在重复。

**过程**

> 1.预估需要的比特位数: 两个比特位表示一个数据，所以需要1G的空间  
> 2.将数据映射至位图
> 
>  *  对应哪个字节: `data / 4`
>  *  对应字节上的哪个比特位: `data % 4`
> 
> 3.找只出现了一次的数据，只需要将比特位两两进行检测，只要比特位是`01`，就说明该数据只出现了一次。

**3. 给定100亿个整数，设计算法找到只出现不超过两次的所有整数**

思路和上题一模一样，只需要启动没有使用的比特位进行出现2次数据的记录的即可

**4. 给定两个文件，分别有100亿个整数，只有1G内存，如何才能找到两个文件的交集**

**思路**

> 1.使用两个位图将两个文件A，B中的数据分别映射出来，一个位图512M，两个位图刚好512M。因为整数只能表示2^32 个整数，100亿超过了这个范围，所以一个文件中的数据必定有重复，但是我们不用关心，只需要用位图将 2^32 记录下来就行了  
> 2.将A和B的两个位图进行按位`&`，将结果存到A或者B中  
> 3.检测A位图中那些位位1，这个比特位就是两个文件中的交集。

# 3. 布隆过滤器 #

如果现在有非常大量的单词，请设计一个算法查找单次是否在集合中出现过？

**分析**：

> 1.如果使用位图表示数据的状态信息，那么必须将字符串转为整型，两个不同的字符串完全有可能转换成了相同的数据，提高了哈希冲突的概率  
> 2.使用哈希表存储单次，效率高了，但是占用的空间太大了

**使用布隆过滤器，将哈希与位图结合使用**

## 3.1 为什么使用布隆过滤器？ ##

根据上述分析，发现位图和哈希函数都有缺点，布隆过滤器就是为了解决如上缺点诞生的。  
  布隆过滤器是由布隆（Burton Howard Bloom）在1970年提出的 一种紧凑型的、比较巧妙的概率型数据结构，特点是高效地插入和查询，可以用来告诉你 “某样东西一定不存在或者可能存在”，它是用**多个哈希函数，将一个数据映射到位图结构中**。此种方式不仅可以提升查询效率，也可以节省大量的内存空间。  
  本质是**位图+绑定多个哈希**

![在这里插入图片描述][c824b981ac85495388e05707f2613441.PNG_pic_center]

## 3.2 原理 ##

> 1.先通过**多个哈希函数**计算出来其对应的比特位  
> 2.再检测算出来的比特位上是否全是1，只要有一个比特位上是0，那么这个元素就一定不存在

## 3.3 插入、查找与删除 ##

### 3.3.1 插入 ###

如果要映射一个值到布隆过滤器中，需要使用多个不同的哈希函数生成多个哈希值，并对每个生成的哈希值指向的 bit 位置 1，例如针对值 “baidu” 和三个不同的哈希函数分别生成了哈希值 1、4、7![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5ZOm5ZOm5ZG15ZG1_size_12_color_FFFFFF_t_70_g_se_x_16_pic_center]有可能会出现误判的情况![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5ZOm5ZOm5ZG15ZG1_size_15_color_FFFFFF_t_70_g_se_x_16_pic_center]

### 3.3.2 查找 ###

布隆过滤器的思想是将一个元素用多个哈希函数映射到一个位图中，因此被映射到的位置的比特位一定为1。所以可以按照以下方式进行查找：分别计算每个哈希值对应的比特位置存储的是否为零，**只要有一个为零，代表该元素一定不在哈希表中**，否则可能在哈希表中。

比如：在布隆过滤器中查找"alibaba"时，假设3个哈希函数计算的哈希值为：1、3、7，刚好和其他元素的比特位重叠，此时布隆过滤器告诉该元素存在，但实该元素是不存在的。

### 3.3.3 删除 ###

布隆过滤器**不能直接支持删除工作**，因为在删除一个元素时，可能会影响其他元素。  
  比如：删除上图中"tencent"元素，如果直接将该元素所对应的二进制比特位置0，“baidu”元素也被删除了，因为这两个元素在多个哈希函数计算出的比特位上刚好有重叠。

**如果要删除**  
  将布隆过滤器中的每个比特位扩展成一个小的计数器，插入元素时给k个计数器(k个哈希函数计算出的哈希地址)加一，删除元素时，给k个计数器减一，通过多占用几倍存储空间的代价来增加删除操作。  
  **可能会出现计数环绕，因为处理的都是海量数据，所以可能会出现某一计数的溢出**

## 3.4 优缺点 ##

**优点**

>  *  增加和删除元素的时间复杂度O(K)， k为哈希函数的个数
>  *  哈希函数相互之间并没有关系，可以使用多线程进行处理
>  *  没有存储元素本身，采用对应的二进制进行存储，提高了空间的利用效率，保密性较高
>  *  如果能承受一定误判，那么布隆过滤器空间存储上具有很大的优势
>  *  数据量很大时，布隆过滤器可以表示全集
>  *  使用同一组散列函数的布隆过滤器，可以交、并、差

**缺点**

>  *  有误判率，即存在假阳性(False Position)，即不能准确判断元素是否在集合中(补救方法：再建立一个白名单，存储可能会误判的数据)
>  *  不能获取元素本身
>  *  一般情况下不能从布隆过滤器中删除元素
>  *  如果采用计数方式删除，可能会存在计数回绕问题

## 3.5 问题 ##

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

**近似算法**:

> 使用布隆过滤器. 将一个文件的所有数据放入布隆过滤器, 之后用第二个文件中的数据在布隆过滤器中进行查找，如果找到了说明这个数据是交集. 问题: 有些找到的交集可能不存在.

**精确算法**:

> 使用哈希切分. 将两个文件的数据分别进行哈希切割, 就会得到hash值相同的数据，存放在一个文件中。 分别用切割好的两组文件hash值相同的函数进行比较，就可以得出交集。但是效率有点低。

# 4. 代码模拟 #

## 4.1 位图 ##

#pragma once
    
    #include <assert.h>
    
    typedef unsigned char uch;
    namespace bite
    { 
    	template<size_t N>   // 非类型模板参数---N在类模板当中就是一个产量
    	class bitset
    	{ 
    	public:
    		bitset()
    			: _bst(N / 8 + 1)
    			, _size(0)
    		{ }
    
    		// 将pos位置上的比特位置为1
    		void set(size_t pos)
    		{ 
    			assert(pos <= N);
    
    			// 1. 计算pos对应的是那个字节byte
    			size_t index = pos / 8;
    
    			// 2. 计算pos对应的是那个比特位bit
    			size_t bitPos = pos % 8;
    
    			// 3. 将byte的第bit个比特位置为1
    
    			_bst[index] |= (1 << bitPos);
    			_size++;
    		}
    
    		// 将pop位置上的比特位置为0
    		void reset(size_t pos)
    		{ 
    			assert(pos <= N);
    
    			// 1. 计算pos对应的是那个字节byte
    			size_t index = pos / 8;
    
    			// 2. 计算pos对应的是那个比特位bit
    			size_t bitPos = pos % 8;
    
    			// 3. 将byte的第bit个比特位置为0
    
    			_bst[index] &= ~(1 << bitPos);
    			_size--;
    		}
    
    		// 检测pos位置上的比特位是0还是1
    		bool test(size_t pos)
    		{ 
    			assert(pos <= N);
    
    			// 1. 计算pos对应的是那个字节byte
    			size_t index = pos / 8;
    
    			// 2. 计算pos对应的是那个比特位bit
    			size_t bitPos = pos % 8;
    
    			// 3. 检测byte的第bit个比特为0还是1
    			return 0 != (_bst[index] & (1 << bitPos));
    		}
    
    		// 返回比特位的总数
    		size_t size()const
    		{ 
    			return N;
    		}
    
    		// 返回为1的比特位的总数
    		size_t count()const
    		{ 
    			return _size;
    		}
    	private:
    		vector<uch> _bst;
    		size_t _size;   // 为1的比特位的总数
    	};
    }

## 4.2 布隆过滤器 ##

#pragma once
    
    
    #include "BitSet.hpp"
    
    #include "Common.h"
    
    template<class K, size_t N, class K2Int1 = str2Int1, 
                                class K2Int2 = str2Int2, 
    							class K2Int3 = str2Int3, 
    							class K2Int4 = str2Int4, 
    							class K2Int5 = str2Int5>
    class BloomFilter
    { 
    public:
    	BloomFilter()
    		: bt()
    		, _size(0)
    	{ }
    
    	void Insert(const K& data)
    	{ 
    		// 1. 先计算data在位图中对应的5个位置
    		// 2. 再将位图中对应的比特位置为1
    		size_t bitCount = bt.size();
    		size_t index = K2Int1()(data) % bitCount;
    		bt.set(index);
    
    		index = K2Int2()(data) % bitCount;
    		bt.set(index);
    
    		index = K2Int3()(data) % bitCount;
    		bt.set(index);
    
    		index = K2Int4()(data) % bitCount;
    		bt.set(index);
    
    		index = K2Int5()(data) % bitCount;
    		bt.set(index);
    
    		_size++;
    	}
    
    	size_t size()const
    	{ 
    		return _size;
    	}
    
    	bool Find(const K& data)
    	{ 
    		// 1. 先计算data对应的5个位置
    		// 2. 再检测位图中对应的比特位是否为1
    		size_t bitCount = bt.size();
    		size_t index = K2Int1()(data) % bitCount;
    		if (!bt.test(index))
    		{ 
    			return false;
    		}
    
    		index = K2Int2()(data) % bitCount;
    		if (!bt.test(index))
    		{ 
    			return false;
    		}
    
    		index = K2Int3()(data) % bitCount;
    		if (!bt.test(index))
    		{ 
    			return false;
    		}
    
    		index = K2Int4()(data) % bitCount;
    		if (!bt.test(index))
    		{ 
    			return false;
    		}
    
    		index = K2Int5()(data) % bitCount;
    		if (!bt.test(index))
    		{ 
    			return false;
    		}
    
    		// 注意：这个元素可能存在
    		return true;
    	}
    
    private:
    	bite::bitset<N * 5> bt;
    	size_t _size;  // 记录布隆过滤器当中有效元素的个数
    };

[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5ZOm5ZOm5ZG15ZG1_size_20_color_FFFFFF_t_70_g_se_x_16_pic_center]: /images/20220829/88207905595a4aadad13d95268749ceb.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5ZOm5ZOm5ZG15ZG1_size_20_color_FFFFFF_t_70_g_se_x_16_pic_center 1]: /images/20220829/f2365f25d1a340afab5329b3a454fe98.png
[c824b981ac85495388e05707f2613441.PNG_pic_center]: /images/20220829/bc0491a80296493d8a86a244816aedb8.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5ZOm5ZOm5ZG15ZG1_size_12_color_FFFFFF_t_70_g_se_x_16_pic_center]: https://img-blog.csdnimg.cn/a641eb9c31284de7b10ddf7b4bbdbda3.PNG?x-oss-process=image/watermark,type_ZHJvaWRzYW5zZmFsbGJhY2s,shadow_50,text_Q1NETiBA5ZOm5ZOm5ZG15ZG1,size_12,color_FFFFFF,t_70,g_se,x_16#pic_center
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5ZOm5ZOm5ZG15ZG1_size_15_color_FFFFFF_t_70_g_se_x_16_pic_center]: /images/20220829/c7dd14cf283c41eeb766605a1a6afb8f.png