数据结构——布隆过滤器

布隆过滤器概念

布隆过滤器实现

哈希函数

布隆过滤器类

加入到布隆过滤器

判断在不在

测试一下

为啥不写删除？

测试一下误判率

布隆过滤器概念

布隆过滤器也是一种位图结构，它可以快速的判断字符串在不在位图中。它的优点是节省空间。

我们首先要解决的问题就是如何把字符串映射到位图中，比如现在有"凡人修仙传"、"古典音乐入门"、"音乐剧"这三个字符串，我们怎么把这三个字符串映射到位图中呢？我们需要用字符串哈希算法把这三个字符串转成整形，然后%上空间大小，比如"凡人修仙传"映射到52，"古典音乐入门"映射到17，"音乐剧"映射到79，然后把该位置设置为1，如果要查找就判断映射到的位置是0还是1。

但是最大的问题是啥呢？最大的问题是冲突，假设现在来了一个字符串"歌剧魅影"，计算过后它映射到的位置是79，此时会发生什么事情？由于"音乐剧"映射位置是79，因此79位置的值是1，此时会判断"歌剧魅影"是在的，这是不是就扯淡了，因此最大的问题是可能存在误判。

也就是说这里的一个问题，判断一个字符串存在是可能出现误判的。因为可能会出现上面的情况，位图中根本没有"歌剧魅影"，但是"歌剧魅影"和存在的"音乐剧"映射到了同一个位置，因此我们得出的结果"歌剧魅影"是存在的，但它其实是不存在的。

而判定一个字符串不在是不可能误判的，如果一个字符串不在，它必然就不在，因为它映射到的那个位置为0，那它肯定不存在。

那我们怎么解决存在出现误判的问题呢？这个问题解决不了，哈希表有冲突是怎么解决的，是用链表挂起来，但是挂不起来啊，这里是位图，怎么挂呢。

有一个叫布隆的人呢，它是怎么想的呢，他觉得虽然我们解决不了这个问题，但是我们可以降低误判率，它是怎么降低误判率的呢。

举个栗子，假设你要和素未谋面的网友线下见面，在此之前你从没有见过他，你应该如何让他在线下快速找到你呢？很简单，提供尽可能多的信息，我身高1米8，是个男的，穿着红色上衣，鞋子是黑色的，穿着牛仔裤，戴了一个鸭舌帽，手里拿着一多红色玫瑰花，此时网友是不是就能根据这些信息让它尽可能的不找错人？即使它看到一个带了鸭舌帽，穿着红色上衣但是个女生，也不会把它当做是你，因为你是男的。只要提供的特征越多，它找错人的概率就越少，因为茫茫人海中满足上述所有特征的人几乎特别少，此时可以大大降低它找错人的概率。

但是如果你说你穿着红色上衣，鞋子黑色，它认错人的概率就会大大增加，因为可能有很多人都穿黑色鞋子红色上衣。

回到布隆过滤器，我也提供更多的信息就好了，我把一个字符串用三个哈希算法，映射到3个不同的位置。此时我要判断一个字符串在不在，就要判断3个位置是不是全都是1，只要有一个不是1，它就不在，虽然"歌剧魅影"和"音乐剧"两个位置都冲突了，但是它有一个位置不在，那它就不在，当然有可能3个位置都冲突了，但是这个概率被降低了，我们虽然无法消除误判，但是我们可以降低误判，并且我们可以通过开更多的空间，让误判率尽可能低。

现在不在是不是准确的？不在是准确的，只要一个位置不为0它就不在。

但是在是存在误判的，映射到的3个位置都可能都是别人是一样的，但是这样的概率相比上面的概率是大大降低了的。

应用场景

布隆过滤器之所以叫过滤器是因为它主要是用来过滤用的，我们来看看它的应用场景。

不需要精确的场景

比如快速判断昵称是否注册过，现在游戏的所有昵称都放在数据库里，我要注册昵称就需要当我输入完毕就要显示这个昵称存在不存在，但是数据库效率是很低的，此时就可以用上布隆过滤器，我把所有的昵称放到布隆过滤器里，你输入一个昵称我就来判断你在不在。

假设昵称不存在，那肯定是不存在的。

假设昵称存在，被人用了，没有误判，你用不了，这没啥问题。

如果存在误判，它不存在，没有被人用过，但是实际上判断是存在的，被人用过，你也用不了这个昵称，有没有问题？没问题呀，用户怎么知道这个昵称是存在的，而且这个误判率是可以控制到5%到10%的。

如果我们要做到精确怎么办？

还是用布隆过滤器，如果显示昵称不在，那就直接返回了。

如果显示昵称被人用过存在的时候，我再去数据库查一遍，然后把数据库的结果返回给你，这样就可以保证是不会出现误判的。

此时的布隆过滤器是不是就可以过滤到大量的不在的昵称，不在的就过滤掉了，不用去数据库里查了。此时的效率就得到了很大的提升。

布隆过滤器实现

哈希函数

我们首先需要3个哈希函数，来实现映射，我们可以从大佬们提供的哈希函数里面选3个，我选了前3个评分比较高的。

下面的3个哈希函数都实现成了仿函数，在布隆过滤器中的模版参数中直接传递给这三个类，然后通过匿名函数使用这三个哈希函数，等会看下面的代码就了解了。

各种字符串Hash函数 - clq - 博客园

struct  BKDRHash
{size_t operator()(const string& s){size_t hash = 0;for (auto ch : s){hash = hash * 131 + ch;  }return hash;}
};struct SDBMHash
{size_t operator()(const string& s){size_t hash = 0;for (auto ch : s){hash = 65599 * hash + ch;//hash = (size_t)ch + (hash << 6) + (hash << 16) - hash;  }return hash;}
};struct RSHash
{size_t operator()(const string& s){size_t hash = 0;size_t magic = 63689;for (auto ch : s){hash = hash * magic + ch;magic *= 378551;}return hash;}
};

布隆过滤器类

布隆过滤器是一个位图，因此类里面一定要有一个位图，幸运的是C++的STL提供了位图类bitset，我们直接包含#include<bitset>即可使用，它的使用也很简单，set函数将一个位置标记为1，test函数判断一个位置在不在。

第一个模版参数是一个非类型模版参数，需要我们传递布隆过滤器的大小，第二个参数默认是string类型，因为本来就是处理字符串的呀，后面Hash1、Hash2、Hash3就是我们上面的三个哈希函数。

template<size_t N,class K = string, class Hash1 = BKDRHash,class Hash2 = SDBMHash,class Hash3 = RSHash>
class BloomFilter
{
public:void Set(const K& key);  //加入到布隆过滤器bool Test(const K& key); //判断在不在private:bitset<N> _bf;
};

加入到布隆过滤器

我们只需要调用3个仿函数，计算出3个映射的值，然后对其%N，这里N是布隆过滤器的大小，如果不对N取模会溢出的，然后调用bitset的set方法加入到位图中即可。

  void Set(const K& key){size_t hash1 = Hash1()(key) % N;size_t hash2 = Hash2()(key) % N;size_t hash3 = Hash3()(key) % N;_bf.set(hash1);_bf.set(hash2);_bf.set(hash3);}

判断在不在

同样计算出所在的位置，然后使用test判断在不在，如果一个位置不在就直接返回false，三个都存在说明它存在，返回true即可，但这里可能是存在误判的。

    bool Test(const K& key){size_t hash1 = Hash1()(key) % N;// 如果第一个位置不在，说明不存在直接返回if (_bt.test(hash1) == false)return false;size_t hash2 = Hash2()(key) % N;if (_bt.test(hash2) == false)return false;size_t hash3 = Hash3()(key) % N;if (_bt.test(hash3) == false)return false;// 走到这里说明三3个位置都存在，返回真,但存在误判return true;}

测试一下

#include "BloomFilter.h"int main()
{BloomFilter<13> bf;bf.Set("凡人修仙传");bf.Set("古典音乐入门");bf.Set("音乐剧");cout << bf.Test("凡人修仙传") << endl;cout << bf.Test("古典音乐入门") << endl;cout << bf.Test("音乐剧") << endl;cout << bf.Test("歌剧魅影") << endl;return 0;
}

我们可以看一下打印结果。

这个地方我在Set函数里打印了计算出来的哈希值，方便观察，我们可以看到，"凡人修仙传"、"古典音乐入门"、"音乐剧"这三个字符串的哈希值都是有相互冲突的，并且"音乐剧"里面有两个一样的哈希值，但是3个哈希值都一样的概率还是很低的，并且我们Test了"歌剧魅影"可以发现它并不存在。

为啥不写删除？

我们的代码里是没有写删除的，这是为啥呢？假设我把"音乐剧"删除了，会发生啥情况，删除之后"凡人修仙传"也不在了，因为它们两个有一个哈希值是相同的，你把一个字符串删除了会影响其它的字符串，因此布隆过滤器是绝对不能支持删除的。

如果我们要让误判率尽可能的低，我们可以多搞几个哈希函数，并且布隆过滤器的空间开多一点。

测试一下误判率

下面的代码就是构造了一对相似的字符串，v1和v2里的字符串是相似的，前缀都一样，就是后缀不同，然后将v1里的字符串全都加入布隆过滤器，然后判断v2里的字符在不在布隆过滤器，如果在说明误判，然后计数+1，最后用误判的个数除以字符串的总个数，就可以相似字符串的误判率。

又构造一对不同的字符串，它们完全不同，v1和v3是不同的，v1加入布隆过滤器，判断v3在不在，如果在说明误判，计数+1，最后用误判的个数除以字符串的总个数，就可以不相似字符串的误判率。

#include "BloomFilter.h"
#include <vector>void TestBloomFilter()
{const size_t N = 100000;BloomFilter<N * 4> bf;vector<string> v1;string url = "https://mp.csdn.net/mp_blog/creation/editor?spm=1011.2124.3001.6192";// 构造 N 个字符串for (size_t i = 0; i < N; i++){v1.push_back(url + to_string(i));}// 将v1中的字符串加入布隆过滤器for (auto& str : v1){bf.Set(str);}// v2和v1是相似字符串(前缀一样)，但不一样vector<string> v2;for (size_t i = 0; i < N; i++){v2.push_back(url + to_string(9999999 + i));}size_t n2 = 0;// 遍历 v2，看看v2中的字符串在布隆过滤器中在不在for (auto& str : v2){if (bf.Test(str)) // 误判++n2;}cout << "相似字符集误判率: " << (double)n2 / double(N) << endl;// 不相似字符集vector<string> v3;for (size_t i = 0; i < N; i++){string url = "bilibili.com";url += to_string(i);v3.push_back(url);}size_t n3 = 0;for (auto& str : v3){if (bf.Test(str)) // 误判++n3;}cout << "不相似字符集误判率: " << (double)n3 / double(N) << endl;}int main()
{TestBloomFilter();return 0;
}

字符串的个数是N，我们看看当布隆过滤器空间是4倍的N的时候，误判是多少。

我们可以看到，相似字符串和不相似字符串的误判率都是差不多的，一个8%一个7%。