【数据结构】布隆过滤器的原理讲解及其底层实现和海量数据问题

1.为什么要有布隆过滤器？

在处理大量数据时，传统的数据结构如哈希表、位图等虽然有其优势，但也存在不足。例如，哈希表在存储大量数据时可能占用大量空间，而位图虽然节省空间，但通常只能处理整型数据。布隆过滤器正是在这样的背景下被提出，旨在解决这些问题。
例如我们在看新闻或者刷视频时，手机会给我们不停地推荐新的内容，它每次推荐时要去重，去掉那些已经看过的内容。
手机客户端推荐系统如何实现推送去重的？
用服务器记录了用户看过的所有历史记录，当推荐系统推荐新闻时会从每个用户的历史记录里进行筛选，过滤掉那些已经存在的记录。 如何快速查找呢？

1. 用哈希表存储用户记录，缺点：浪费空间
2. 用位图存储用户记录，缺点：位图一般只能处理整形，如果内容编号是字符串，就无法处理
   了。
3. 将哈希与位图结合，即布隆过滤器

2.布隆过滤器的概念

布隆过滤器（Bloom Filter）是由布隆（Burton Howard Bloom）在1970年提出的一种紧凑型的、比较巧妙的概率型数据结构。这种数据结构以其高效地插入和查询特性而著称，可以用来告诉你 “某样东西一定不存在或者可能存在”，它是用多个哈希函数，将一个数据映射到位图结构中，尽管它并不能保证查询结果的绝对准确性，但能够在很大程度上提高查询效率并节省内存空间

形象来说就是，一般的哈希只能一个元素映射一个位置，这对于字符串之类的结构十分容易造成不同的元素通过相同的哈希函数映射到相同的位置，而布隆过滤器提出一个元素可以映射多个位置，大大降低了冲突的概率。

3.布隆过滤器的实现

3.1 插入

当插入一个元素时，布隆过滤器会使用多个哈希函数将该元素映射到位图的多个位置，并将这些位置的比特位设置为1

#include<iostream>
#include<bitset>
#include<string>
#include<vector>
using namespace std;

struct HashFuncBKDR
{
	// BKDR
	size_t operator()(const string& s)
	{
		size_t hash = 0;
		for (auto ch : s)
		{
			hash *= 131;
			hash += ch;
		}

		return hash;
	}
};

struct HashFuncAP
{
	// AP
	size_t operator()(const string& s)
	{
		size_t hash = 0;
		for (size_t i = 0; i < s.size(); i++)
		{
			if ((i & 1) == 0) // 偶数位字符
			{
				hash ^= ((hash << 7) ^ (s[i]) ^ (hash >> 3));
			}
			else              // 奇数位字符
			{
				hash ^= (~((hash << 11) ^ (s[i]) ^ (hash >> 5)));
			}
		}

		return hash;
	}
};

struct HashFuncDJB
{
	// DJB
	size_t operator()(const string& s)
	{
		size_t hash = 5381;
		for (auto ch : s)
		{
			hash = hash * 33 ^ ch;
		}

		return hash;
	}
};

template<size_t N,
	class K = string,
	class Hash1 = HashFuncBKDR,
	class Hash2 = HashFuncAP,
	class Hash3 = HashFuncDJB>
class BloomFilter
{
public:
	void Set(const K& key)
	{
		size_t hash1 = Hash1()(key) % M;
		size_t hash2 = Hash2()(key) % M;
		size_t hash3 = Hash3()(key) % M;

		_bs->set(hash1);
		_bs->set(hash2);
		_bs->set(hash3);
	}

	bool Test(const K& key)
	{
		size_t hash1 = Hash1()(key) % M;
		if (_bs->test(hash1) == false)
			return false;

		size_t hash2 = Hash2()(key) % M;
		if (_bs->test(hash2) == false)
			return false;

		size_t hash3 = Hash3()(key) % M;
		if (_bs->test(hash3) == false)
			return false;

		return true; // 存在误判(有可能3个位都是跟别人冲突的，所以误判)
	}

private:
	static const size_t M = 10 * N;
	std::bitset<M>* _bs = new std::bitset<M>;
};

3.2 查找

当查询一个元素时，布隆过滤器同样会使用这些哈希函数计算该元素在位图中的位置。如果所有对应位置的比特位都是1，则认为该元素可能存在；如果任何一个位置的比特位是0，则认为该元素一定不存在。
~
布隆过滤器的思想是将一个元素用多个哈希函数映射到一个位图中，因此被映射到的位置的比特位一定为1。
所以可以按照以下方式进行查找：分别计算每个哈希值对应的比特位置存储的是否为零，只要有一个为零，代表该元素一定不在哈希表中，否则可能在哈希表中。
~
注意：布隆过滤器如果说某个元素不存在时，该元素一定不存在，如果该元素存在时，该元素可能存在，因为有些哈希函数存在一定的误判。
比如：在布隆过滤器中查找"alibaba"时，假设3个哈希函数计算的哈希值为：1、3、7，刚好和其他元素的比特位重叠，此时布隆过滤器告诉该元素存在，但实该元素是不存在的。

3.3 删除

布隆过滤器一般不直接支持删除工作，因为在删除一个元素时，可能会影响其他元素

一种支持删除的方法：将布隆过滤器中的每个比特位扩展成一个小的计数器，插入元素时给k个计数器(k个哈希函数计算出的哈希地址)加一，删除元素时，给k个计数器减一，通过多占用几倍存储空间的代价来增加删除操作

4.布隆过滤器的应用（海量数据）

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

内存太大，只能一点点来了，我们可以通过哈希思想将这个大文件通过哈希函数来进行划分，最后划分到能够塞进两个set中去，从而寻找他们的交集


通过哈希函数进行哈希切分，能够成为交集的元素会在同一个文件中

最后在使用两个set进行查交集

整个过程会产生两种极端情况：
1.相同的太多，会被set去重掉，无影响
2.冲突太多，切割后还是太大，我们就需要换个哈希函数进行哈希切分，如果还大的话，以此类推进行多次切分，直到大小合适为止

5.海量数据问题的处理方式

海量数据的特征：数据量过大，内存放不下

1.先思考是否有合适的数据结构可以解决，如：位图、堆、布隆过滤器等等
2.使用大事化小的思路。合理使用哈希切分，减少内存

6. 总结布隆过滤器的优缺点

1.优点

1. 增加和查询元素的时间复杂度为:O(K), (K为哈希函数的个数，一般比较小)，与数据量大小无关
2. 哈希函数相互之间没有关系，方便硬件并行运算
3. 布隆过滤器不需要存储元素本身，在某些对保密要求比较严格的场合有很大优势
4. 在能够承受一定的误判时，布隆过滤器比其他数据结构有这很大的空间优势
5. 数据量很大时，布隆过滤器可以表示全集，其他数据结构不能
6. 使用同一组散列函数的布隆过滤器可以进行交、并、差运算

2.缺点

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