目录

一、概念

二、模拟实现

三、布隆过滤器扩展应用

---

 

上一篇章学习了位图的使用，但它只适用于整数，对于要查询字符串是否在不在，位图并不能解决。所以针对这一问题，布隆过滤器可以派上用场，至于布隆过滤器是什么，其实并没有什么神奇的，就是在位图上套了哈希函数罢了，这两者组合起来就是布隆过滤器，而字符串就可以通过哈希函数转换成整数映射到位图当中去。 

一、概念

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

原理分析： 

我们来进行分析，为什么不存在是一定的，而存在是可能的，以及为什么要这样做。

首先来解释为什么要用多个哈希函数。

我们知道，字符串可以通过哈希函数转换成整数，但是哈希冲突是避免不了的，可能存在多个字符串通过哈希函数都得到了一样的整数，所以，为了尽量的减少哈希冲突，可以使用多个哈希函数，让字符串通过多个哈希函数得到多个映射位置，只要不是多个映射位置都相同，就不会冲突，这样大大提高了效率。至于要用几个哈希函数是适合的。

这里有一份研究：（转载详解布隆过滤器的原理，使用场景和注意事项 - 知乎 (zhihu.com)）

其中误报率就是哈希冲突率 

其中k、m、n满足：

 其中k、m、p满足：

我们可以发现，哈希函数用的越多，哈希冲突率就越低，但是哈希函数到3之后，误报率已经很低了，其次，当哈希函数、插入元素固定，所开空间越大，误报率也越低。

用一张图来表示通过哈希函数映射到位图中：

那么综上，即使采用了多个哈希函数，也依然可能会存在哈希冲突，所以在判断东西在不在时，若返回的是存在，这有可能是误判，说明映射的位置依然可能完全相同，而不存在时，说明映射的位置不完全相同，这是正确的结果，为了确保冲突率，我们在模拟实现的时候就采用3个哈希函数。

二、模拟实现

#include "MyBitSet.h"//在上一篇章已实现
struct BKDRHash
{size_t operator()(const string& key){size_t hash = 0;for (auto e : key){//BKDRhash *= 31;hash += e;}return hash;}
};struct APHash
{size_t operator()(const string& key){size_t hash = 0;for (size_t i = 0; i < key.size(); i++){if ((i & 1) == 0){hash ^= ((hash << 7) ^ key[i] ^ (hash >> 3));}else{hash ^= (~((hash << 11) ^ key[i] ^ (hash >> 5)));}}return hash;}
};
struct DJHash
{size_t operator()(const string& key){register size_t hash = 5381;for(auto e : key){hash += (hash << 5) + e;}return hash;}
};
namespace bit
{template<size_t N, class K = string, //默认输入的是字符串class HashFunc1 = BKDRHash,class HashFunc2 = APHash,class HashFunc3 = DJHash>class BloomFilter{public:void set(const K& key){//获取三个映射位置int hash1 = HashFunc1()(key) % N;int hash2 = HashFunc2()(key) % N;int hash3 = HashFunc3()(key) % N;_blf.set(hash1);_blf.set(hash2);_blf.set(hash3);}bool test(const K& key){//key不存在是准确的。int hash1 = HashFunc1()(key) % N;if (_blf.test(hash1) == false)return false;int hash2 = HashFunc2()(key) % N;if (_blf.test(hash2) == false)return false;int hash3 = HashFunc3()(key) % N;if (_blf.test(hash3) == false)return false;//key存在可能有误判return true;}private:bitset<N> _blf;};
}void TestBF1()
{bit::BloomFilter<100> bf;bf.set("猪八戒");bf.set("沙悟净");bf.set("孙悟空");bf.set("二郎神");cout << bf.test("猪八戒") << endl;cout << bf.test("沙悟净") << endl;cout << bf.test("孙悟空") << endl;cout << bf.test("二郎神") << endl;cout << bf.test("二郎神1") << endl;cout << bf.test("二郎神2") << endl;cout << bf.test("二郎神 ") << endl;cout << bf.test("太白晶星") << endl;
}void TestBF2()
{srand(time(0));const size_t N = 100000;bit::BloomFilter<N * 10> bf;std::vector<std::string> v1;//std::string url = "https://www.cnblogs.com/-clq/archive/2012/05/31/2528153.html";std::string url = "猪八戒";for (size_t i = 0; i < N; ++i){v1.push_back(url + std::to_string(i));}for (auto& str : v1){bf.set(str);}// v2跟v1是相似字符串集（前缀一样），但是不一样std::vector<std::string> v2;for (size_t i = 0; i < N; ++i){std::string urlstr = url;urlstr += std::to_string(9999999 + i);v2.push_back(urlstr);}size_t n2 = 0;for (auto& str : v2){if (bf.test(str)) // 误判{++n2;}}cout << "相似字符串误判率:" << (double)n2 / (double)N << endl;// 不相似字符串集std::vector<std::string> v3;for (size_t i = 0; i < N; ++i){//string url = "zhihu.com";string url = "孙悟空";url += std::to_string(i + rand());v3.push_back(url);}size_t n3 = 0;for (auto& str : v3){if (bf.test(str)){++n3;}}cout << "不相似字符串误判率:" << (double)n3 / (double)N << endl;
}

测试：

#include <string>
#include "MyBloomFilter.h"int main()
{TestBF2();return 0;
}

 输出结果：

三、布隆过滤器扩展应用

1.给两个文件，分别由100亿个字符串，只有1G内存，如何找到两个文件交集？

假设每个字符串占50个字节，那么100亿就是5000字节，约等于500G，内存肯定存不下，此时可以采用哈希切分。如图：

 

2.给一个超过100G大小的log file，log中存着IP地址，设计算法找到出现次数最多的IP地址？

与第一题类似，先进行哈希切分，然后通过map统计每个小文件中IP地址出现的次数进行比较即可。