哈希应用——布隆过滤器

布隆过滤器的提出

场景一：在注册账号设置昵称的时候，为了保证每个用户昵称的唯一性，系统必须检测你输入的昵称是否被使用过，这本质就是一个key的模型，我们只需要判断这个昵称被用过，还是没被用过。

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

这里有三种解决方案：

1.用哈希表/红黑树存储已经存在的数据，缺点：浪费空间，因为当数据比较多的时候，内存根本吃不消

2.用位图存储已经存在的数据，缺点：位图一般只能处理整型，如果内容编号是字符串，就无法处理了

3.将哈希与位图结合，也就是这次要学习的布隆过滤器

布隆过滤器的概念

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

相比于传统的 List、Set、Map 等数据结构，它更高效、占用空间更少，但是缺点是其返回的结果是概率性的，而不是确切的。

如果我们要映射一个值到布隆过滤器中，我们需要使用多个不同的哈希函数生成多个哈希值，并对每个生成的哈希值指向的 bit 位置 1，例如针对值 “baidu” 和三个不同的哈希函数分别生成了哈希值 1、4、7。

看下图：

此时我们再插入tencent，如果哈希函数返回 3、4、8 的话：

可以看到，这里有一些是重复了的，比如说哈希值为4，两个字符串都有映射到。

假如此时我们查询“dianping”这个字符串，假设得到的哈希值为：1、4、5，那么可以肯定的确认不存在；那么当我们查询“baidu”时，假设得到的哈希值当然为前面的1、4、7，那么能肯定存在吗？答案是不能：因为这三个哈希值都有可能是别的数据映射上去的，比如第一个数据的其中一个值映射到1，另外一个映射到4，还有一个映射到7。所以只能得出可能存在这个结论。

布隆过滤器的三个哈希函数

//第一个
struct BKDRHash
{
	size_t operator()(const string& s)
	{
		size_t value = 0;
		for (auto ch : s)
		{
			value = value * 131 + ch;
		}
		return value;
	}
};

//第二个
struct APHash
{
	size_t operator()(const string& s)
	{
		size_t value = 0;
		for (size_t i = 0; i < s.size(); i++)
		{
			if ((i & 1) == 0)
			{
				value ^= ((value << 7) ^ s[i] ^ (value >> 3));
			}
			else
			{
				value ^= (~((value << 11) ^ s[i] ^ (value >> 5)));
			}
		}
		return value;
	}
};

//第三个
struct DJBHash
{
	size_t operator()(const string& s)
	{
		if (s.empty())
			return 0;
		size_t value = 5381;
		for (auto ch : s)
		{
			value += (value << 5) + ch;
		}
		return value;
	}
};

布隆过滤器的插入

	void Set(const K& key)
	{
		//计算出key对应的三个位
		size_t i1 = Hash1()(key) % N;
		size_t i2 = Hash2()(key) % N;
		size_t i3 = Hash3()(key) % N;

		//设置位图中的这三个位
		_bs.set(i1);
		_bs.set(i2);
		_bs.set(i3);
	}

布隆过滤器的查找

	bool Test(const K& key)
	{
		//依次判断key对应的三个位是否被设置
		size_t i1 = Hash1()(key) % N;
		if (_bs.test(i1) == false)
		{
			return false; //key一定不存在
		}

		size_t i2 = Hash2()(key) % N;
		if (_bs.test(i2) == false)
		{
			return false; //key一定不存在
		}

		size_t i3 = Hash3()(key) % N;
		if (_bs.test(i3) == false)
		{
			return false; //key一定不存在
		}

		return true; //key对应的三个位都被设置，key存在（可能误判）
	}

布隆过滤器的删除

布隆过滤器不能支持删除，因为在删除一个元素时，看可能会影响其他元素。

比如：删除前面的“tencent”元素，如果直接将该元素所对应的二进制比特位置，“baidu”元素也被删除了，因为这两个元素在多个哈希函数计算出的比特位上刚好有重叠。

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

缺陷：
1. 无法确认元素是否真正在布隆过滤器中
2. 存在计数回绕

布隆过滤器的优缺点

优点

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