[C++]哈希应用之位图&布隆过滤器

04-11 1431阅读

🪐🪐🪐欢迎来到程序员餐厅💫💫💫

主厨：邪王真眼

主厨的主页：Chef‘s blog

所属专栏：c++大冒险

总有光环在陨落，总有新星在闪烁

前言：

我们之前学习了哈希表，哈希表通过映射关系，实现了O(1)的复杂度来查找数据，哈希在实践中是一个非常重要的思想，今天要学习的就是哈希思想的两大应用：位图与布隆过滤器

一、位图

1.1 面试题【腾讯】

给 40 亿个不重复的无符号整数，没排过序。给一个无符号整数，如何快速判断一个数是否在这40亿个数中。大家一看到这道题想到的应该是以下方法：

1. 直接遍历，时间复杂度O(N)
2. 先排序(O(NlogN))，在利用二分查找: logN
3.二叉搜索树、map、set、哈希.......
但是不要忽略了一个问题：40亿个整型，存入内存就是大约16G，而且还会有别的内存开销（例如红黑树），所以上述方法是不现实的。

我们仔细想想，对于这道题目而言，一个数据只有两种状态：在/不在。如果我们想要标识两种状态，其实只需要一个比特位就够了，0表示不存在，1表示存在。通过哈希的映射思想，我们可以把每一个数据映射到一个比特位中，这就是位图的概念。

在STL库中，已经为我们提供了位图bitset，我先简单讲解一下bitset的接口，再给大家实现一个位图。

1.2位图的实现

1.2.1成员变量
```
template
class bitset
{
public:
protected:
	vector _bits;
};
```
注意事项：
- 注意这个非类型模板参数N，他其代表位图中要开多少个比特位，而不是字节！！！
  1.2.3构造函数
  
  思路：
  我们先开一个数据类型是int的vector对象，一个int包含32比特位，接着直接对把数据的存在/不存在两种状态存放在对应比特位中，c++的除法是向下取整，所以要开（N/32+1）个int
```
BitSet()
{
	_bits.resize(N /32 + 1);
}
```
  1.2.4set：
  
  作用：把目标比特位的值改为1
  现在传过来一个整数i，我们怎么找到它所对应的比特为呢？其实思路类似于一维数组转二维数组
  i/32得到的是该比特位位于vector对象的的几个元素中，i%32得到的是该比特位处于当前元素的第几个比特位中。
```
size_t i = x / 32; // vector的第i个元素
size_t j = x % 32; // 第i个元素的第j个比特位
```
  但是c++并没有直接修改目标比特位的函数，所以我们要还要思考怎么实现这个功能
  
  这就要用到位移操作符了
  
  我们要把整数i第j个比特位修改为1，可以先把1左移j位得到整数y，在把i与y按位或，注意我们比特位的计算是从0开始的，即一个整型比特位是0到31.
```
1000100 //待修改数据,把第3位修改为1
00000001 //数字1
00001000 //数字1左移3位
------------
10000100
00001000 //按位或
------------
10001100//得到结果
```
  set函数接口如下：
```
void set(size_t x)
{
	assert(x  3));
			else//奇数位字符
				hash ^= (~((hash > 5)));
		}
		return hash;
	}
};
struct HashFuncDJB
{
	size_t operator()(const string& s)
	{
		register size_t hash = 5381;
		for (auto ch : s)
			hash = hash * 33 ^ ch;
		return hash;
	}
};
```
  - 为什么是设计的vector传参是5*N
    知乎有大佬经过计算得到如下图这样的结论：
    
    在选择布隆过滤器的长度和哈希函数的数量时应满足下图公式
    
    
    
    知乎文章在此：布隆过滤器详解
    
    与此我们直到当选择了三个哈希函数时，布隆过滤器的长度应是（N*3/ln 2）,向上取整得5
    
    因此有bitset _bs;
    
    2.3.2插入set
    
    想要插入一个数据，其实就是通过三个哈希函数计算出三个映射位置，并把它们设置为1。
```
void set(const K& key)
{
	size_t hash1=(HF1()(key))%(5*N);
	size_t hash2 = (HF2()(key)) % (5 * N);
	size_t hash3 = (HF3()(key)) % (5 * N);
	_bs.set(hash1);
	_bs.set(hash2);
	_bs.set(hash3);
}
```
    2.3.3查找test
    查找方法：分别计算每个哈希值对应的比特位置存储的是否为零，只要有一个为零，代表该元素一定不在哈希表中，否则可能在哈希表中。注意：布隆过滤器如果说某个元素不存在，该元素一定不存在，如果说元素存在，则该元素可能存在可能不存在，因为哈希查找时存在一定的误判。比如：在布隆过滤器中查找"abc"时，3个哈希函数计算的哈希值为：1、3、7，刚好和其他元素的比特位重叠，此时布隆过滤器告诉该元素存在，但实该元素是不存在的。
```
bool test(const& K key)
{
	size_t hash1 = (HF1()(key)) % (5 * N);
	size_t hash2 = (HF2()(key)) % (5 * N);
	size_t hash3 = (HF3()(key)) % (5 * N);
	return _bs.test(hash1)&&_bs.test(hash2)&&_bs.test(hash3);
}
```
    2.3.4删除reset
    布隆过滤器不支持删除操作：看下图如果我们删除了C语言，那它的三个比特位就会被置为0，那在查找c++就会显示找不到
    2.4 布隆过滤器优点
    - 1. 增加和查询元素的时间复杂度为:O(K), (K为哈希函数的个数，一般比较小)，与数据量大小无关
    - 2. 哈希函数相互之间没有关系，方便硬件并行运算
    - 3. 布隆过滤器不需要存储元素本身，在某些对保密要求比较严格的场合有很大优势
    - 4. 在能够承受一定的误判时，布隆过滤器比其他数据结构有这很大的空间优势
    - 5. 数据量很大时，布隆过滤器可以表示全集，其他数据结构不能
    - 6. 使用同一组散列函数的布隆过滤器可以进行交、并、差运算
      2.5 布隆过滤器缺陷
      - 1. 有误判率，即存在假阳性(False Position)，即不能准确判断元素是否在集合中(补救方法：再建立一个白名单，存储可能会误判的数据)
      - 2. 不能获取元素本身
      - 3. 一般情况下不能从布隆过滤器中删除元素
      - 4. 如果采用计数方式删除，可能会存在计数回绕问题
        2.6布隆过滤器使用场景：
        
        小明买了手机，去注册手机号，选了一个号码
        
        1.把号码输入布隆过滤器，接受返回值
        
        2.返回值是假，说明该号码没被用过
        
        3.返回值是真，说明该号码可能用过，则再去数据库中寻找看是否用过
        这么看来，我们直接节省了一大半的时间（较于直接去数据库看）
        🥰创作不易，你的支持对我最大的鼓励🥰
        
        🪐~ 点赞收藏＋关注 ~🪐