C++进阶篇5---番外-位图和布隆过滤器

namespace zxws
{
	template <size_t N = 100>
	class twobitset
	{
	public:
		void set(size_t x)
		{
			size_t i = x / 32;
			size_t j = x % 32;
			if (bs1.test(x) == false && bs2.test(x) == false)//00->01
			{
				bs1.set(x);
			}
			else if (bs1.test(x) == true && bs2.test(x) == false)//01->10
			{
				bs1.reset(x);
				bs2.set(x);
			}
		}
        void test(size_t x)
		{
			return bs1.test(x) == true && bs2.test(x) == false;//01--代表只出现一次
		}
	private:
		bitset<N>bs1;
		bitset<N>bs2;
	};
}

题2：找文件交集，这个就很明显了，两个位图分别存放两个文件中的数字，然后比特位之间&一下，比特位上为1的就是交集

题3：这题其实和第1题一样，都是查看数字出现次数，要求不出现两次，即有没出现，出现1次，出现2次和出现2次以上四个状态，两个位图正好够了，实现同题1

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

实现原理图

一般来说用三个哈希函数就差不多了

上图是网上的研究数据显示结果，仅供参考(k，m，n满足上诉关系时，不容易发生哈希冲突)

布隆过滤器的作用范围还是很广泛的，尤其是在不怎么关心某一个东西是否真的存在的场景下，举个例子，比如说取用户ID，当你取的id没人用时，OK你创建成功，当你取的id显示有人用时，如果是真的有人用了，那我们就换一个，如果没人用，它误判了，那我们也就是不能用这个id而已，没有啥太大影响，这时布隆过滤器就非常合适

当然如果说用户投诉说明明没人用这个id，却不让用，要求我们修复bug，这时我们只要让在布隆过滤器过滤后显示为存在的数据再去数据库中校验一下即可，

当然也有人会觉得反正都要去数据库校验还要布隆过滤器干嘛，注意：1.布隆过滤器它为啥叫过滤器，关键就是它只能确定不存在的数据，不能确定存在的数据。2.网络上通讯会比较耗时，如果每一个id的确认都需要与服务器上的数据库校验，就会浪费时间

实现如下

//哈希函数就自行去网上找哪些不容易产生哈希冲突的就行
template <size_t N, 
	class K=string, 
	class HashFunc1=HashFun<K>, 
	class HashFunc2=DGBHash<K>, 
	class HashFunc3=APHash<K> >
class BloomFiler {
public:
	void set(const K& key)
	{
		size_t hash1 = HashFunc1()(key) % N;
		size_t hash2 = HashFunc2()(key) % N;
		size_t hash3 = HashFunc3()(key) % N;

		_bs.set(hash1);
		_bs.set(hash2);
		_bs.set(hash3);
	}

	bool test(const K& key)
	{
		size_t hash1 = HashFunc1()(key) % N;
		size_t hash2 = HashFunc2()(key) % N;
		size_t hash3 = HashFunc3()(key) % N;
		if (_bs.test(hash1) == false
			|| _bs.test(hash2) == false
			|| _bs.test(hash3) == false)
			return false;

		return true;
	}
private:
	bitset<N*5>_bs;
};

两个问题：

1. 给两个文件，分别有100亿个query，我们只有1G内存，如何找到两个文件交集？分别给出精确算法和近似算法(具体下面一个专题讲)

2. 如何扩展BloomFilter使得它支持删除元素的操作？一般来说是不能支持的，因为删除一个元素的映射会影响其他元素的哈希映射(因为它们会出现冲突)，但是我们可以给它们加一个引用计数，这样就能在删除它的同时不影响其他元素的映射

优点

1. 增加和查询元素的时间复杂度为:O(K), (K为哈希函数的个数，一般比较小)，与数据量大小无关

2. 哈希函数相互之间没有关系，方便硬件并行运算

3. 布隆过滤器不需要存储元素本身，在某些对保密要求比较严格的场合有很大优势

4. 在能够承受一定的误判时，布隆过滤器比其他数据结构有这很大的空间优势

5. 数据量很大时，布隆过滤器可以表示全集，其他数据结构不能

6. 使用同一组散列函数的布隆过滤器可以进行交、并、差运算

三、哈希分割---哈希思想的扩展