C++|哈希应用-＞布隆过滤器

目录

一、概念

二、模拟实现

三、布隆过滤器扩展应用

---

 

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

一、概念

布隆过滤器是由布隆(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)
		{
			//BKDR
			hash *= 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地址出现的次数进行比较即可。