布隆过滤器的引入

我们在使用新闻客户端看新闻时，它会给我们不停地推荐新的内容，它每次推荐时要去重，去掉那些已经看过的内容。问题来了，新闻客户端推荐系统如何实现推送去重的？用服务器记录了用户看过的所有历史记录，当推荐系统推荐新闻时会从每个用户的历史记录里进行筛选，过滤掉那些已经存在的记录。如何快速查找呢？

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

布隆过滤器的概念

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

深入了解布隆过滤器

问题：布隆过滤器，判断一个数据是否存在，“在”存在误判，还是“不在"存在误判?

答案是如果用布隆过滤器判断一个数据是否存在，如果得到的结果是在，那么可能是不准确的，是存在误判的。如果得到的结果是不在，这是准确的结果。假设映射“腾讯”，但是它映射的位置都跟别的数据冲突了（其它数据已经提前映射了这些位置），所以导致它的结果是“在”，结果就误判了。

布隆过滤器的使用场景是什么？

能容忍误判的场景。比如注册时，快速判断昵称是否使用过。如果是判断手机号码这种1对1的数据，也可以尝试使用布隆过滤器，先用布隆过滤器过滤一遍，筛选出不在的，误判的结果再用数据库（磁盘，速度较慢）筛查。
使用布隆过滤器的一般都是字符串。

如何选择哈希函数个数和布隆过滤器长度

如果布隆过滤器长度过小，那么布隆过滤器很快就会被存储完，即比特位都设置为1了，那么再查询数据都会返回“存在”，都误判了，这样过滤的作用就失效了。所以布隆过滤器的长度会直接影响误判率，结论就是布隆过滤器的长度越长误判率越小。

另外，哈希函数的个数就需要控制，个数越多则布隆过滤器的比特位设置成1的速度越快，占用的空间越多，并且布隆过滤器的效率会越低；如果个数太少，误判率就会变高。下面是大佬总结出来的关系图：
在这里插入图片描述
如何选择适合业务的 k 和 m 值呢，这里直接贴一个公式：

在这里插入图片描述
这里我们一起来算一下，In2约等于0.69，如果使用3个哈希函数，即k=3,那么就是3 = (m/n)*0.69，那么m/n的值约在4~5之间，m大概是n的4到5倍左右，也就是说布隆过滤器的长度应该是插入元素个数的4到5倍。

布隆过滤器的实现

//3个哈希函数
struct BKDRHash
{
	size_t operator()(const string& s)
	{
		size_t hash = 0;
		for (auto ch : s)
		{
			hash += ch;
			hash *= 31;
		}
		return hash;
	}
};
struct APHash
{
	size_t operator()(const string& s)
	{
		size_t hash = 0;
		
		for (long i = 0; i < s.size(); i++)
		{
			size_t ch = s[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& s)
	{
		size_t hash = 5381;
		for (auto ch : s)
		{
			hash += (hash << 5) + ch;
		}
		return hash;
	}
};
//假定三个哈希函数,N个比特位,K是我们所要查找的键值
//Hash:将key转换成整型，才能进行映射
//N表示最多会插入的key的个数
//哈希函数的个数，代表一个key值映射几个位，哈希函数越多，误判率越低
//但是哈希函数越多，我们平均消耗的空间也会越多
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 len = N * _X;
		//key值分别通过三个哈希函数进行映射
		size_t hash1 = Hash1()(key) % len;
		_bs.set(hash1);

		size_t hash2 = Hash2()(key) % len;
		_bs.set(hash2);

		size_t hash3 = Hash3()(key) % len;
		_bs.set(hash3);
		
		cout << hash1 << " " << hash2 << " " << hash3 << " " << endl << endl;
	}
	//布隆过滤器的查找
	bool test(const K& key)
	{
		size_t len = N * _X;

		//3个位置key值都存在，才能证明key值存在
		//所以只要有一个位置key不存在，就返回假
		//key值分别通过三个哈希函数进行映射
		size_t hash1 = Hash1()(key) % len;
		if (!_bs.test(hash1))
		{
			return false;
		}

		size_t hash2 = Hash2()(key) % len;
		if (!_bs.test(hash2))
		{
			return false;
		}

		size_t hash3 = Hash3()(key) % len;
		if (!_bs.test(hash3))
		{
			return false;
		}
	}
private:
	static const size_t _X = 4;
	bitset<N*_X> _bs;
};