哈希的应用（位图，布隆过滤器）

位图（整型）

1.面试题
给40亿个不重复的无符号整数，没排过序。给一个无符号整数，如何快速判断一个数是否在这40亿个数 中。【腾讯】

1. 遍历，时间复杂度O(N)
2. 排序(O(NlogN))，利用二分查找: logN
3. 位图解决 数据是否在给定的整形数据中，结果是在或者不在，刚好是两种状态，那么可以使用一个二进制比 特位来代表数据是否存在的信息，如果二进制比特位为1，代表存在，为0代表不存在。

位图概念
所谓位图，就是用每一位来存放某种状态，适用于大规模数据，但数据状态又不是很多的情况。通常是用来判断某个数据存不存在的。

#pragma once
#include<vector>
#include<iostream>
using namespace std;
class BitSet
{ 
public:
	BitSet(size_t Bitnum)
		:_Bitnum(Bitnum)
	{ 
		_bits.resize((Bitnum >> 8) + 1, 0);

	}
	void Set(size_t x)//把那个位设置成1，代表存在
	{ 
		//size_t index = x / 8;
		size_t index = x >> 3;
		size_t num = x % 8;

		_bits[index] |= (1 << num);
	}
	void Reset(size_t x)//把那个位设置成0，代表不存在
	{ 
		//size_t index = x / 8;
		size_t index = x >> 3;
		size_t num = x % 8;

		_bits[index] &= (~(1 << num));
	}
	bool Test(size_t x)//存在返回1，不存在返回0
	{ 
		size_t index = x >> 3;
		size_t num = x % 8;

		return _bits[index] & (1 << num);
	}
private:
	vector<char> _bits;//一个char，8个bite
	size_t _Bitnum;
};

void TestBitSet()
{ 
	BitSet bs(10000);
	bs.Set(9999);
	bs.Set(999);
	bs.Set(99);
	bs.Set(9);

	cout << bs.Test(9999) << endl;
	cout << bs.Test(999) << endl;
	cout << bs.Test(99) << endl;
	cout << bs.Test(9) << endl;
}

int main()
{ 
	TestBitSet();
	system("pause");
	return 0;
}

布隆过滤器（任意类型）

优点：节省空间，快（直接找到那个位）

缺点：容易误判，判断在一定是准确的，判断不在不一定准确

我们在使用新闻客户端看新闻时，它会给我们不停地推荐新的内容，它每次推荐时要去重，去掉那些已经看 过的内容。问题来了，新闻客户端推荐系统如何实现推送去重的？ 用服务器记录了用户看过的所有历史记 录，当推荐系统推荐新闻时会从每个用户的历史记录里进行筛选，过滤掉那些已经存在的记录。 如何快速查 找呢？

1. 用哈希表存储用户记录，缺点：浪费空间
2. 用位图存储用户记录，缺点：不能处理哈希冲突
3. 将哈希与位图结合，即布隆过滤器

概念

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

emplate<class K, class HashFunc1, class HashFunc2, class HashFunc3>//一个值映射三个位置
class BloomFilter
{ 
public:
	void Set(const K& key)//不支持Reset，因为布隆过滤器映射了很多个位，把冲突的位置为零，会影响其他冲突的映射
	{ 
		size_t index1 = HashFunc1()(key);
		size_t index2 = HashFunc2()(key);
		size_t index3 = HashFunc3()(key);

		_bs.Set(index1);
		_bs.Set(index2);
		_bs.Set(index3);

	}
	void Test(const K& key)//只要有一个位不在，就能判断他不在
	{ 
		size_t index1 = HashFunc1()(key);
		if (_bs.Test(index1) == false)
		{ 
			return false;
		}
		size_t index2 = HashFunc2()(key);
		if (_bs.Test(index1) == false)
		{ 
			return false;
		}
		size_t index3 = HashFunc3()(key);
		if (_bs.Test(index1) == false)
		{ 
			return false;
		}

		return true;//存在误判
	}
private:
	BitSet _bs;
};

int main()
{ 
	system("pause");
	return 0;
}