前言

我们可以通过位图一定程度上解决快速判断一个数据是否在集合，但是面对字符串等自定义类型的时候，误判率是非常大的。所以下面小编会介绍一种结合位图和哈希的数据结构：布隆过滤器。

在一定程度上减小了哈希冲突的发生。

1. 数据结构

我们可以利用字符串的哈希算法将字符串转化为具有小概率冲突的整型（下面称这个整型为哈希值）。

但是位图上解决了整型范围内在不在集合里的问题，但是对于字符串的哈希值，我们仍然需要保持一种怀疑的态度，因为我们无法保证两个不同的字符串的哈希值是不同的！

所以，为了减小这样的误判（注意，这种误差是无法消除的），我们可以将同一个字符串经过不同的哈希字符串算法转化为不同的哈希值，存储到多个不同的位置！

• 布隆过滤器：

  是由布隆(Burton Howard Bloom)在1970年提出的一种紧凑型、比较巧妙的概率型数据结构。特点是高效地插入和查询。主要运用于快速判断一个元素是否在一个集合中，但是存在一定的误判率（判断一个数据在集合中是不准确的），但是不会出现漏判（判断一个数据不在集合中是准确的）。

例如：

2. 模拟

• 我们下面主要谈布隆过滤器的两个操作：

  1. set（插入）

     • 首先将数据利用哈希函数转化为多个哈希值。
     • 再进行哈希的映射算法得到对应位置的index。
     • 最后将对于对应位图的位置设置为1。

  2. check（查询）

     • 首先将数据利用哈希函数转化为多个哈希值。
     • 再依次判断，如果有一个不存在则该数据不存在；如果全存在，则可能存在。

#pragma once

#pragma once
#include<iostream>
#include<vector>
using namespace std;

namespace LL
{
	template<size_t N>
	class bitset
	{
	public:
		bitset()
		{
			//1个整型4个字节，32个bit位
			//向上取整
			_a.resize(N / 32 + 1);
		}

		void set(size_t n)
		{
			int i = n / 32; //算出在第几个int
			int j = n % 32; //算出在i个int的第几个位置
			_a[i] |= (1 << j);
		}

		void unset(size_t n)
		{
			int i = n / 32;
			int j = n % 32;
			_a[i] &= (~(1 << j));
		}

		bool check(size_t n)
		{
			int i = n / 32;
			int j = n % 32;
			return _a[i] & (1 << j);
		}
	private:
		vector<int> _a;
	};

	// BloomFilter
	struct BKDRHash
	{
		size_t operator()(const string& val)
		{
			size_t hashi = 0;
			for (auto e : val)
			{
				hashi *= 131;
				hashi += e;
			}
			return hashi;
		}
	};


	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 Type = string,
		class Hash1 = BKDRHash,
		class Hash2 = APHash,
		class Hash3 = DJBHash>
	class BloomFilter
	{
	public:
		void set(const Type& val)
		{
			size_t hash1 = BKDRHash()(val) % N;
			size_t hash2 = APHash()(val) % N;
			size_t hash3 = DJBHash()(val) % N;

			_a.set(hash1);
			_a.set(hash2);
			_a.set(hash3);
		}
		bool check(const Type& val) //存在误判
		{
			size_t hash1 = BKDRHash()(val) % N;
			if (_a.check(hash1) == false)
				return false;

			size_t hash2 = APHash()(val) % N;
			if (_a.check(hash2) == false)
				return false;

			size_t hash3 = DJBHash()(val) % N;
			if (_a.check(hash3) == false)
				return false;

			return true;
		}
	private:
		bitset<N> _a;
	};
}

• 注意：

  标准的布隆过滤器是不支持删除操作的。因为标准的布隆过滤器是通过位图将位置置为1的，所以一个位置的删除操作应该看起来是置0操作，而置0操作会将原位图一个位置的多个映射都修改了，这就导致了标准布隆过滤器的一个数据的删除操作会影响其它的数据！！

• 使得布隆过滤器支持删除操作的方法：

  1. 计数布隆过滤器：

     将原bit数组改为计数数组（每个位置多位/使用多个bit数组）。添加元素时对应的位置的计算器+1；删除元素时对应位置的计数器-1；查询时，判断对应位置的原始计数器是否大于0。
     缺陷：空间占用变高、存在计数绕回（计数器溢出）

  2. 布谷鸟过滤器：

     基于布谷鸟的哈希思想，将每一个元素映射到两个位置，元素实际存储的位置只有一个（直接将元素存储起来，不是bit位置1）。

     • 插入：

       通过不同的哈希函数得到元素的两个哈希值（A、B），再选择其中一个为空的位置将元素存储进入。如果两个位置都不为空，则选择将其中一个位置的原哈希值踢出，将该元素存入，例如：原来A位置存储了一个x，B位置存储了xx。新存储的元素的也是A、B，所以该元素将旧存储在A的元素x踢出，将自己存入。而原来被踢出的元素，继续使用自己的哈希值去寻找下一个位置，完成“踢出-迁徙”的迭代过程。直到找到一个空位置/达到迁徙次数上限。

     • 删除：

       得到哈希值过后，删除对应的元素即可。

     • 查询：

       得到哈希值过后，判断是否存在即可。

     优势：无误删风险、支持精确计数
     缺点：插入冲突处理复杂、空间占用过高、哈希函数设计要求高。

3. 定时重建/分层布隆过滤器

   读者自行了解

3. 布隆过滤器的运用

1. 问题一：给定两个文件，分别由100亿个query（询问，每一个大约占30个字节），我们只有1G内存，如何找到两个文件的交集？分别给出近似算法和精确算法。

   首先想要完全存储query是行不通的

   • 近似算法：

     利用标准布隆过滤器。我们可以分别将两个文件的query存入两个布隆过滤器中，然后将两个布隆过滤器的位图直接进行&操作，再遍历其中一个文件，存在即是交集。

   • 精确算法：

     利用哈希切割、分治的思想。

     • 相同的query如果用哈希函数处理得到的哈希值一定是同一个值。所以我们可以将这些两个大文件$A$、$B$中的query根据不同的哈希值存入不同的小文件$A_i$或者$B_i$中（保证：同一个大文件的相同的query一定在同一个文件中、不同文件的相同query在同一个下标的小文件中）

     

     • 然后我们就对单个小文件分别找交集例如$A_0$和$B_0$找到交集$C_1$、$A_1$和$B_1$找到交集$C_2$、……
     • 最后将$C_i$中的数据进行集合汇总即可。
       

     需要面临的解决的问题：

     1. 如何找交集？
        两种方案：先双去重、再找交；先单去重、再找交、再去重

     2. 哈希切割的不均等性：
        哈希切割会可能导致文件的大小不均等，例如：可能存在一个超过1G的文件。例如，现在$A_0$文件有5G大小，但是我们内存仍然不可能存下，该如何处理呢？
        有两种情况：a、5G大小中大多数是相同query b、5G大小中大多数是冲突的query
        解决方案：利用set的insert（有去重效果），由于我们内存肯定是不够的，所以我们可以对异常结果进行判断。如果没有抛异常，说明大多数是相同的query，去重之后正常处理即可；如果抛异常，说明大多数是冲突的query，我们可以再选择一个哈希函数，再进行哈希切割！

4. 总结

• 布隆过滤器优点：

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

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

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

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

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

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

• 布隆过滤器缺陷：

  1. 有误判率，即存在假阳性(False Position)，即不能准确判断元素是否在集合中(补救方法：再建立一个白名单，存储可能会误判的数据)

  2. 不能获取元素本身。

  3. 一般情况下不能从布隆过滤器中删除元素。

完。希望这篇文章能够帮助你！！！