哈希表——布隆过滤器

一个问题
应用方面
布隆过滤器实现

我们今天继续来了解哈希表的延伸——布隆过滤器。

一个问题

我们之前介绍过了位图，我们将数据进行映射到相应的二进制位上。来帮助我们提高检索的效率。但是我们生活中可不是简简单单存个数字就行了。如果我们要映射的是字符串，那就有点麻烦了。

在这里插入图片描述

其实也可以解决，我们之前不是学过了字符串的哈希算法吗？我们可以把相对应的字符串进行相应的哈希算法，得到的整数值，然后再映射到相应的位置上去。
在这里插入图片描述
看样子问题解决了，但是，假设我现在有一个字符串，经过字符串哈希函数的处理映射之后，发现跟"apple"映射的位置一样的：

这个时候如果我去检查这个位图，位图的结果就是该字符串存在，但实际上该字符串不存在，只是凑巧"apple"的映射和该字符串的映射产生了哈希碰撞，误判了。

那这该怎么办呢？所以，有一个叫布隆的人想到，既然无法避免冲突，那可不可以把这个冲突的概率降低一点，我们多用几个哈希函数处理，一个字符串映射多个位：
在这里插入图片描述
置于为什会降低，其实也很简单，之前我们只有一个哈希函数进行处理，容易冲突。现在我们有三个哈希函数，就算一个冲突了，其他两个还可以有保障。所以降低了冲突的频率。

但是，布隆过滤器只能降低冲突的频率，不能完全避免冲突。这也是它明显的缺点之一。

应用方面

有的同学就要问了，既然布隆过滤器不能彻底解决问题，那它有什么样的价值呢？其实布隆过滤器最大的优势就是优化效率。
大家玩游戏的时候，尤其是一些联网的大型游戏，注册用户时，会经历一个必须的步骤——取用户名。

这个时候，为了保障每个玩家的独一无二性，我们的用户名是不允许重名的。所以我们有时候注册用户，取的用户名，会显示该用户名已被注册。

这中间，就有布隆过滤器的功劳。

首先，我们得知道，我们玩家的用户名，是储存在服务器上的：
在这里插入图片描述
如果没有布隆过滤器，我要保证不重名，我只能到服务器上一条一条比对。这样的效率就太低了。

但是如果我们有一个布隆过滤器，如果该用户名不存在，就直接可以存到服务器上。（因为布隆过滤器不会误判没有在服务器上的用户名）
在这里插入图片描述
但是，如果布隆过滤器返回的是有，就要分两种情况：一是真的存在，二是误判了。
这个时候，我们只能到服务器上去找了。

在这里插入图片描述

布隆过滤器实现

我们来实现一下布隆过滤器：

//BKDR算法
struct BKDRHash
{
	size_t operator()(const string& key)
	{
		// BKDR
		size_t hash = 0;
		for (auto e : key)
		{
			hash *= 31;
			hash += e;
		}

		return hash;
	}
};

//APH算法
struct APHash
{
	size_t operator()(const string& key)
	{
		size_t hash = 0;
		for (size_t i = 0; i < key.size(); i++)
		{
			char ch = key[i];
			if ((i & 1) == 0)
			{
				hash ^= ((hash << 7) ^ ch ^ (hash >> 3));
			}
			else
			{
				hash ^= (~((hash << 11) ^ ch ^ (hash >> 5)));
			}
		}
		return hash;
	}
};

//DJB算法
struct DJBHash
{
	size_t operator()(const string& key)
	{
		size_t hash = 5381;
		for (auto ch : key)
		{
			hash += (hash << 5) + ch;
		}
		return hash;
	}
};


template<size_t N,
	class K = string,
	class HashFunc1 = BKDRHash,
	class HashFunc2 = APHash,
	class HashFunc3 = DJBHash>
class BoolFilter
{
public:
	void Set(const K& key)
	{
		size_t hash1 = HashFunc1()(key) % N;
		size_t hash2 = HashFunc2()(key) % N;
		size_t hash3 = HashFunc3()(key) % N;

		cout << "第一个hash函数的值" << hash1 << endl;
		cout << "第二个hash函数的值" <<hash2 << endl;
		cout << "第三个hash函数的值" <<hash3 << endl << endl;

		_bt.set(hash1);
		_bt.set(hash2);
		_bt.set(hash3);
	}

	bool Test(const K& key)
	{
		// 判断不存在是准确的
		size_t hash1 = HashFunc1()(key) % N;
		if (_bt.check(hash1) == false)
			return false;

		size_t hash2 = HashFunc2()(key) % N;
		if (_bt.check(hash2) == false)
			return false;

		size_t hash3 = HashFunc3()(key) % N;
		if (_bt.check(hash3) == false)
			return false;

		// 存在误判的
		return true;
	}


private:
	My_bitmap::bitmap<N> _bt;
};

我们可以测试一下：

void TestBF1()
{
	BoolFilter<100> bf;
	bf.Set("Lisa");
	bf.Set("Mike");
	bf.Set("孙悟空");
	bf.Set("林黛玉");

	cout << bf.Test("LISA") << endl;
	cout << bf.Test("Lisa") << endl;
	cout << bf.Test("孙悟空") << endl;
	cout << bf.Test("二郎神") << endl;
	cout << bf.Test("林黛玉") << endl;
	cout << bf.Test("太白晶星") << endl;
}