【哈希】位图/布隆过滤器

位图

前言

在实现位图结构之前我们先看一个问题：

给出40亿个不重复的无符号整型，并且是无序的。然后给一个无符号整数，怎样快速判断这个数是否在40亿个数之中。

方法一：对40亿个数据进行遍历。我们会发现，时间复杂度为O(N)，对于40亿的数据量来说时间复杂度太高了。

方法二：排序(O(N*logN))，然后二分查找(O(logN))。现在相比于方法一时间复杂度进行了优化。但是，一个无符号整型需要4Byte，40亿个大概需要16G的内存，所以还是不能够解决问题。

下面我们对位图进行介绍，位图就能很好得解决内存不够的这个问题：

位图概念

所谓位图，就是用比特位来标识一个状态，适用于海量数据、且无重复的使用场景。通常用来判断某个数据是否存在。

位图结构

前面提到的问题中，一个无符号整数所需要的内存是4Byte，那么我们能不能用更小的空间来存储一个数字呢？答案肯定是能，我们可以用一个bit位来标识这个数存不存在，一个数所占空间为4Byte，每个位上都是0或者1，那么我们就能用这个bit位上的数字来标识一个数的状态：

位图实现

template<size_t N>
//N为位图中要存放数据的个数
class bitset
{
public:
	bitset()
	{
		_bit.resize(N / 8 + 1, 0);
		//为了防止存储数据个数小于8时开辟的空间为0，所以要加上1
	}

	//将x存放入位图中
	void set(size_t X)
	{
		size_t hashi = X / 8; // hashi为这个数要放在编号为第几个字节位
		size_t num = X % 8;   // num为这个数据需要存放在第hashi字节中的位数
		_bit[hashi] |= (1 << num);
	}

	//修改x在位图中的状态
	void reset(size_t X)
	{
		size_t hashi = X / 8;
		size_t num = X % 8;
		_bit[hashi] &= ~(1 << num);
	}
	
	//查询x是否在位图中
	bool test(size_t X)
	{
		size_t hashi = X / 8;
		size_t num = X % 8;
		return _bit[hashi] & (1 << num);
	}
private:
	vector<char> _bit;
    //注意：这里实现的位图结构中vector中存放的是char
};

通过用例测试一下位图：

位图优缺点

优点：速度快、节省空间。

缺点：只能映射整型。浮点型、string等类型不能存储映射。

布隆过滤器

前言

在我们使用小说app时，系统会根据我们的喜好来推送内容。但是，如何防止推送我们已经浏览过的小说呢？在推送内容的时候一定会去掉那些我们已经看过的小说。那么又是如何进行去重地呢？app推送内容时一定会根据我们的历史浏览记录来进行去重。然后过滤已经查看过的内容。问题来了，现在要推送一部小说，如何快速确定这部小说是否在历史浏览记录中呢？

1、用哈希存储用户记录缺点：浪费空间

2、用位图存储用户记录位图一般用来处理整型，但小说内容编号是字符串，位图就处理不了了。

3、将哈希与位图结合，即布隆过滤器来处理这个问题

布隆过滤器概念

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

布隆过滤器结构

比如现在向过滤器中插入几个关键字：”红楼梦“、”西游记“、”封神演义“、”三国演义“。假如现在我们有三种映射关系。

从这张图可知，布隆过滤器只能告诉我们某个东西一定不存在或者可能存在。布隆过滤器的结构底层也是位图，但是在存储和访问过程中，还有哈希函数的存在。比如上图，有三个哈希函数，每一个字符串都有自己在布隆过滤器中的映射值。

现在我们要查询”平凡的世界“这本书是否存在布隆过滤器中，假如他的哈希值是3，4，6。这是判断结果就是不存在。但是如果他的哈希值为3，4，5。那么此时就会产生误判，由于之前存入的数据将”平凡的世界“这本书的映射位置都置成了1，所以现在就产生了误判。所以布隆过滤器的特点就是能够精确判断不存在，但是存在是存在误判的。

布隆过滤器实现

struct BKDRHash
{
	size_t operator()(const string& s)
	{
		size_t hash = 0;
		for (auto ch : s)
		{
			hash += ch;
			hash *= 31;
		}
		return hash;
	}
};

struct APHash
{
	size_t operator()(const string& s)
	{
		size_t hash = 0;
		for (long i = 0; i < s.size(); i++)
		{
			if ((i & 1) == 0)
			{
				hash ^= ((hash << 7) ^ s[i] ^ (hash >> 3));
			}
			else
			{
				hash ^= (~((hash << 11) ^ s[i] ^ (hash >> 5)));
			}
		}
		return hash;
	}
};

struct DJBHash
{
	size_t operator()(const string& s)
	{
		size_t hash = 5381;
		for (auto ch : s)
		{
			hash += (hash << 5) + ch;
		}
		return hash;
	}
};

//这里已经给出了三个字符串哈希函数，可以根据自己的需要进行设计哈希函数
template<size_t N
,class K = string
,class Hash1 = BKDRHash
,class Hash2 = APHash
,class Hash3 = DJBHash>
class BloomFilter
{
public:
	void set(const K& key)
	{
		size_t len = N * _X;
		size_t hashi1 = Hash1()(key) % len;
		_bitset.set(hashi1);

		size_t hashi2 = Hash2()(key) % len;
		_bitset.set(hashi2);

		size_t hashi3 = Hash3()(key) % len;
		_bitset.set(hashi3);

		cout << hashi1 << ' ' << hashi2 << ' ' << hashi3 << endl;
	}

	bool test(const string& key)
	{
		size_t len = N * _X;
		size_t hashi1 = Hash1()(key) % len;
		if (!_bitset.test(hashi1))
		{
			return false;
		}

		size_t hashi2 = Hash2()(key) % len;
		if (!_bitset.test(hashi2))
		{
			return false;
		}

		size_t hashi3 = Hash3()(key) % len;
		if (!_bitset.test(hashi3))
		{
			return false;
		}

		return true; // 注意，当判断这个关键字存在时可能会出现误判，因为其他关键值在存入时可能映射的位置跟s相同
	}
private:
	static const size_t _X = 3; 
    //为了防止存储数据过多而引起误判率的提高，所以适当延长布隆过滤器的长度
	bitset<N*_X> _bitset;
};

布隆过滤器优点

1. 增加和查询元素的时间复杂度为:O(K), (K为哈希函数的个数，一般比较小)，与数据量大小无
关
2. 哈希函数相互之间没有关系，方便硬件并行运算
3. 布隆过滤器不需要存储元素本身，在某些对保密要求比较严格的场合有很大优势
4. 在能够承受一定的误判时，布隆过滤器比其他数据结构有这很大的空间优势
5. 数据量很大时，布隆过滤器可以表示全集，其他数据结构不能
6. 使用同一组散列函数的布隆过滤器可以进行交、并、差运算