1.什么是位图

哈希最常用的应用是unordered系列的容器，但是当面对海量数据，如：

如果要使用unordered_set来解决40亿个整数，一个整数占4四节，总共大约占16个G的内存空间，并且set容器中不止有整型数据还有其他的数据，所以需要另一种解决方法，而一个数在或不在可以用1/0来表示，也就是说只需要一个比特位就可以知道一个数在不在其中，于此诞生了位图

位图就是用每一位来存放某种状态，适用于海量数据且数据无重复的场景，通常是用来判断某个数据存不存在的

判断0~23中哪些数据是存在的只需要用三个整型，也就是24个比特位的空间，同理,0亿个数据也不用16G的内存，用0.5G内存的位图即可判断一个数在不在

2.位图的模拟实现

库中的位图：（模板参数N代表位图的大小）

位图有三个主要的接口函数:

1. set: 将一个数据放入位图中
2. reset:将一个数据从位图中删掉
3. test:检测一个数据在不在位图中

位图本身就是一段连续的空间，所以用char类型数组来充当位图的基本结构

template<size_t N>//N是所有数中的最大值
class bit_set
{
public:
	bit_set()
	{
		_bit.resize(N / 8 + 1, 0);
	}
	void set(size_t x)//将第x位变成1
	{
		size_t i = x / 8;//x/8->在第几个char
		size_t j = x % 8;//x%8->在这个char的第几个比特位
		_bit[i] |= (1 << j);//将x对应的比特位变成1
	}
	void reset(size_t x)
	{
		size_t i = x / 8;
		size_t j = x % 8;
		_bit[i] &= ~(1 << j);//将x对应的比特位变成0
	}
	bool test(size_t x)
	{
		size_t i = x / 8;
		size_t j = x % 8;
		return _bit[i] & (1 << j);//对应位置也是1就返回1
	}
private:
	vector<char> _bit;
};

3.什么是布隆过滤器

位图有一个缺陷，那就是只能判断整型是否存在，遇见字符串等类型的数据就很难处理，如：

布隆过滤器是一种紧凑型的、比较巧妙的概率型数据结构，特点是高效地插入和查询，可以用来告诉你 “某样东西一定不存在或者可能存在”，它是用多个哈希函数将一个数据映射到位图结构中，相比于传统的 List、Set、Map 等数据结构，它更高效、占用空间更少，但是缺点是其返回的结果是概率性的，而不是确切的

如果我们要映射一个值到布隆过滤器中，我们需要使用多个不同的哈希函数生成多个哈希值，并对每个生成的哈希值指向的 bit位修改为1，现在存一个值“tencent”，假设哈希函数返回1、3、6

现在再存一个值“ByteDance”，哈希函数返回 3、4、6

由于两个值的哈希函数都返回了3和6这两个bit位，因此它们被覆盖了
如果查询“DJI”这个值是否存在哈希函数返回了 1、6、7三个值，我们发现7这个bit位上的值为0，说明没有任何一个值映射到这个bit位上，因此我们可以很确定地说“DJI”这个值不存在
如果查询“tencent”这个值是否存在，哈希函数返回了 1、3、6三个值，我们检查发现这三个bit位上的值均为1，那么我们可以说“tencent”存在了么？答案是不可以，只能是“tencent”这个值可能存在

4.选择哈希函数个数和布隆过滤器长度

过小的布隆过滤器很快所有的bit位均为1，那么查询任何值都会可能存在，起不到过滤的作用了
哈希函数的个数也需要权衡，个数越多则布隆过滤器bit位置位1的速度越快，且布隆过滤器的效率越低，但是如果太少的话，那我们的误报率会变高

5.布隆过滤器

布隆过滤器的底层也是位图，所以只需封装一层即可实现一个布隆过滤器

实现布隆过滤器的关键有以下几点
1.一个字符串映射几个bit位?
2.怎么把字符串转换为整型?
因此在网络上有一些字符串转换成整型的算法：

//将这三个不同的仿函数传入类,用于字符串转整型
struct HashBKDR
{
	size_t operator()(const string& key)
	{
		size_t val = 0;
		for (auto ch : key)
		{
			val *= 131;
			val += ch;
		}
		return val;
	}
};

struct HashAP
{
	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 HashDJB
{
	size_t operator()(const string& key)
	{
		size_t hash = 5381;
		for (auto ch : key)
			hash += (hash << 5) + ch;
		return hash;
	}
};

#include <string>
using namespace std;
// N表示准备要映射N个值
template<size_t N,class K = string,
	class Hash1 = HashBKDR, class Hash2 = HashAP, class Hash3 = HashDJB>
class Bloom_Filter
{
public:
	void set(const K& key)
	{
		size_t hash1 = Hash1()(key) % (_ratio * N);
		_bits->set(hash1);
		size_t hash2 = Hash2()(key) % (_ratio * N);
		_bits->set(hash2);
		size_t hash3 = Hash3()(key) % (_ratio * N);
		_bits->set(hash3);
	}

	bool test(const K& key)
	{
		size_t hash1 = Hash1()(key) % (_ratio * N);
		if (!_bits->test(hash1))
			return false; // 准确的
		size_t hash2 = Hash2()(key) % (_ratio * N);
		if (!_bits->test(hash2))
			return false; // 准确的
		size_t hash3 = Hash3()(key) % (_ratio * N);
		if (!_bits->test(hash3))
			return false;  // 准确的
		return true; // 可能存在误判
	}

	void reset(const K& key)//支持删除操作的话,可能会把其他数据对应的映射值删除
	{}
private:
	const static size_t _ratio = 5;//开的空间越大,误判率越小
	std::bitset<_ratio* N>* _bits = new std::bitset<_ratio* N>;//标准库中的位图是在栈上开辟的静态数组,过大会栈溢出
};