哈希与位图的结合--布隆过滤器与哈希切分-Toy模板网

这篇具有很好参考价值的文章主要介绍了哈希与位图的结合--布隆过滤器与哈希切分。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

上一章讲了位图，我们知道了在海量数据中查找一个数是否存在，可以用每一个比特位标识。

但是位图只能处理整数，要是字符串或者其它的呢，位图便无法处理了，这个时候便需要用到布隆过滤器了.

布隆过滤器提出

布隆过滤器概念

布隆过滤器的实现以及最优值

哈希切分

布隆过滤器提出

我们在看b站视频时，它会给我们不停地推荐新的内容，它每次推荐时要去重，去掉那些已经看过的内容。问题来了，b站推荐系统如何实现推送去重的？用服务器记录了用户看过的所有历史记录，当b站推荐系统推荐视频时会从每个用户的历史记录里进行筛选，过滤掉那些已经存在的记录。如何快速查找呢？
1. 用哈希表存储用户记录，缺点：浪费空间
2. 用位图存储用户记录，缺点：位图一般只能处理整形，如果内容编号是字符串，就无法处理了。
3. 将哈希与位图结合，即布隆过滤器

布隆过滤器概念

布隆过滤器（Bloom Filter）是一种概率型的数据结构，用于快速判断一个元素是否存在于一个集合中。它基于位图（或称为位数组）和多个哈希函数构成。

布隆过滤器的主要目标是在存储空间相对较小的情况下，实现高效的成员查询。它通过使用多个哈希函数将要查询的元素映射到位图中的多个位上。当一个元素要插入布隆过滤器时，通过多个哈希函数计算出多个索引位置，并将对应位设置为1。当判断一个元素是否存在时，再次通过多个哈希函数计算出多个索引位置，并检查对应位是否都为1。如果有任何一个位为0，则可以确定该元素一定不存在于集合中；如果所有位都为1，则表示该元素可能存在于集合中，但有一定的误判率。

注意，只有判断一个数据存在的时候才会有误判。

因为如果判断一个数据它存在了，但是它可能和别的数据冲突了，即别的数据占的这些位恰好是这个数据的那些位。这样就会造成误判。

我举个例子可以说明一下：

哈希与位图的结合--布隆过滤器与哈希切分,哈希算法,布隆过滤器,C++,哈希切分

而判断一个数据不存在这是绝对不可能误判的，因为不存在说明别的数据都还没有占用这些位，一定没有和这个数据相同的数据存在，因为如果存在了，对应的所有位就都是1了，此时便会判它存在了.

这个误判是不可能去掉的，但是可以降低误判的概率。比如增加多个哈希函数。

这样的话，每个数据对应的位就会多了，这样重合的概率就会更低。

例如之前一个数据对应两个位，现在对应了三个位，是不是重合的概率又降低了呢？

虽然原来我们两个位冲突了，现在又多了一个位，又多了一个机会，此时便相当于降低了误判率。

但是也不能盲目的增加哈希函数，具体会有一个合适的值.

哈希与位图的结合--布隆过滤器与哈希切分,哈希算法,布隆过滤器,C++,哈希切分

如果映射函数的越多，空间消耗就会增多，就失去了原本的优势。

这个会被应用在哪些地方呢？

比如访问一个网站，会有黑名单用户，每个用户访问的时候，都需要判断一下是不是黑名单用户。

我们如果每次都要去数据库中查找，那么经过网络传输等过程会使效率变得非常低下，所以是不被采用的。

这个时候便用到了我们的布隆过滤器，每当有用户访问，先查找存在不存在，有两种情况：

1.存在：如果存在，我们才再次需要去数据库中查找，因为存在会有误判，万一人家不是黑名单用户，你却误判成了黑名单，这当然是不合理的，这个时候才去数据库中查找。

2.不存在：不存在那就说明这个人一定不是黑名单用户了，因为不存在不会有误判，直接返回即可：

哈希与位图的结合--布隆过滤器与哈希切分,哈希算法,布隆过滤器,C++,哈希切分

还有一个我们常见的情景，就是在注册申请一个账号的时候，比如输入昵称的时候，有的后面会立马显示“此昵称已被占用”。这其实就是应用了布隆过滤器。

当你输入一个名字的时候，如果利用布隆过滤器查找，发现存在了，会给你提示已经存在，但是这个名字一定是存在的吗？那不一定，毕竟有可能是误判。

但是你也不会察觉到，占用就占用了呗，然后换一个就行。当然这也对这个公司有好处，报总比不报好，万一就是已经存在的呢，这样就不好了。

但是不存在的话，就不会报，因为它一定不存在了。这也是前面一直所说的.

哈希与位图的结合--布隆过滤器与哈希切分,哈希算法,布隆过滤器,C++,哈希切分

布隆过滤器的实现以及最优值

由于C++STL库中并没有布隆过滤器，所以得靠我们自己手动实现。

首先由于布隆过滤器的数据类型不再只是整数，所以我们要利用模板。

可以定义K为数据的类型，那么我们每次需要给位图开多大空间呢？

总不能一上来开41亿，比如就100个数据，开这么大就有点浪费了，所以再给出一个非类型模板参数N，代表数据的个数，然后在成员变量中定义一个_ratio表示倍数，每次开N*_ratio的空间即可。

可能有同学会有疑问，之前位图不是说开多少空间取决于数据范围吗？这个怎么不用？

因为位图采用的是直接定址法，它这个数据是多少，它就会对应在位图的相应位置，所以数据范围的大小决定了开多少空间。

而布隆过滤器是对每个数据采用了哈希映射，而且是多个哈希映射，这样当然不需要多么大的空间了。比如一个数据1，和99999999，采用了哈希映射后，1对应的位图中是1,2,3，而99999999对应的位图是1,3,4、这个只是一个假设，目的是理解为什么不用根据数据范围来开空间。

然后毋庸置疑，就是对应的哈希函数模板，那么具体定义多少个哈希映射函数呢？

不仅如此，布隆过滤器(内部其实就是一个位图)的长度也影响了误判率，那么长度为多少合适呢？

这个有一套数学理论和实验证明，这里我们只看一下最终结果和公式：

“很显然，过小的布隆过滤器很快所有的 bit 位均为 1，那么查询任何值都会返回“可能存在”，起不到过滤的目的了。布隆过滤器的长度会直接影响误报率，布隆过滤器越长其误报率越小。

另外，哈希函数的个数也需要权衡，个数越多则布隆过滤器 bit 位置位 1 的速度越快，且布隆过滤器的效率越低；但是如果太少的话，那我们的误报率会变高”

哈希与位图的结合--布隆过滤器与哈希切分,哈希算法,布隆过滤器,C++,哈希切分

k 为哈希函数个数，m 为布隆过滤器长度，n 为插入的元素个数，p 为误判率

那么具体该如何选择k和m的值是最优的呢？

有两个公式：

哈希与位图的结合--布隆过滤器与哈希切分,哈希算法,布隆过滤器,C++,哈希切分

根据这两个公式可以选出最优的m和k的值。

然后下面就是布隆过滤器的代码，代码不唯一的，具体根据m和k的值进行调整。

//N表示准备要映射N个值.
template<size_t N,class K,
class Hash1,class Hash2,class Hash3>
class BloomFilter
{
public:
	void Set(const K& key)
	{
		size_t hash1 = Hash1()(key) % (_ratio * N);
		_bits.set(hash1);
		size_t hash2 = Hash2()(key) % (_ratio * N);
		_bits.set(hash2);
		size_t hash3 = Hash3()(key) % (_ratio * N);
		_bits.set(hash3);
	}
	bool Test(const K& key)
	{
		size_t hash1 = Hash1()(key) % (_ratio * N);
		if (!bits.test(hash1))
			return false;
		size_t hash2 = Hash2()(key) % (_ratio * N);
		if (!bits.test(hash2))
			return false;
		size_t hash3 = Hash3()(key) % (_ratio * N);
		if (!bits.test(hash3))
			return false;
		return true;//可能存在误判
	}
private:
	const static size_t _ratio = 5;
	bitset<_ratio*N> _bits;
};

这是主体部分的代码，可以看到以上代码中用了3个哈希函数，具体每个哈希算法怎么实现，则由自己进行决定。也可以在网上搜索一些哈希相关的算法。

然后我们定义3个类，每个类中重载()运算符，然后进行哈希算法的实现。最后创建对象时，把这三个类传入即可。

下面讲解两道布隆过滤器相关的题目：

1、如何扩展BloomFilter使得它支持删除元素的操作？

首先我们要知道，布隆过滤器一般情况下是不能被删除的。大家想一想，为什么？

因为位图中的某一个位可能是两个字符串的位，即它们有公共比特位，例如这张图：

哈希与位图的结合--布隆过滤器与哈希切分,哈希算法,布隆过滤器,C++,哈希切分

如果我们想删除百度，即将百度的对应的位全部置为0，b站也会受到影响，最后只剩下1个位了。

这样在查找的时候，便也查找不到b站了，所以对其他数据也造成影响了。

那么我们能不能强行改造一下呢？

当然是可以的，我们另创建一个位来保存每个位置1的个数count，若每次删除，则将count减1。

如果count为0说明此时已经没有数据再占用这个位了，便可以置为0了，否则，count--即可.