【C++】哈希应用之布隆过滤器

👀樊梓慕：个人主页

 🎥个人专栏：《C语言》《数据结构》《蓝桥杯试题》《LeetCode刷题笔记》《实训项目》《C++》《Linux》《算法》

🌝每一个不曾起舞的日子，都是对生命的辜负

目录

前言

1.布隆过滤器的提出

2.布隆过滤器的概念

3.布隆过滤器的模拟实现

3.1布隆过滤器的插入

3.2布隆过滤器的查找

3.3布隆过滤器不能删除

4.布隆过滤器的优点

5.布隆过滤器的缺陷

6.使用场景

7.源码

前言

布隆过滤器是哈希的又一重要应用，上篇文章我们谈到位图只能处理整型数据的问题，那么对于布隆过滤器来说它结合了哈希与位图，使数据处理扩展到了字符串甚至其他数据类型上。

欢迎大家📂收藏📂以便未来做题时可以快速找到思路，巧妙的方法可以事半功倍。 

=========================================================================

GITEE相关代码：🌟樊飞 (fanfei_c) – Gitee.com🌟

=========================================================================

1.布隆过滤器的提出

在面对海量数据时，红黑树等数据结构虽然查找效率高效，但不可避免的有空间上的巨大开销，所以我们提出了位图这种概念。

但对于位图来说，只能处理整型数据，因为数字采用『 直接定址法』计算哈希值几乎不会产生哈希冲突的问题，而假若是一个字符串呢？虽然我们可以通过不同的哈希函数将字符串转换为整型，但是字符串的组合形式复杂多样，无论通过哪种哈希函数都不可避免地会出现大量哈希冲突。

这里的哈希冲突就是不同的昵称最终被转换成了相同的整型，此时就可能会引发误判，即某个字符串明明不在数据中，却被系统判定为在，于是就出现了布隆过滤器。

2.布隆过滤器的概念

布隆过滤器是由布隆（Burton Howard Bloom）在1970年提出的一种紧凑型的、比较巧妙的概率型数据结构，特点是高效地插入和查询。

布隆过滤器其实就是位图的一个变形和延申，虽然无法避免存在哈希冲突，但我们可以想办法降低误判的概率。

原理：当一个数据映射到位图中时，『 布隆过滤器』会用多个哈希函数将其映射到多个比特位，当判断一个数据是否在位图当中时，需要分别根据这些哈希函数计算出对应的比特位，如果这些比特位都被设置为1则判定为该数据存在，否则则判定为该数据不存在。

布隆过滤器使用多个哈希函数进行映射，目的就在于『 降低哈希冲突的概率』，一个哈希函数产生冲突的概率可能比较大，但多个哈希函数同时产生冲突的概率可就没那么大了。

例子：假设布隆过滤器使用三个哈希函数进行映射，那么“张三”这个昵称被使用后位图中会有三个比特位会被置1，当有人要使用“李四”这个昵称时，就算前两个哈希函数计算出来的位置都产生了冲突，但由于第三个哈希函数计算出的比特位的值为0，此时系统就会判定“李四”这个昵称没有被使用过。

虽然布隆过滤器已经极大的降低了哈希冲突的概率，但是仍然可能会产生误判：

• 当布隆过滤器判断一个数据存在可能是不准确的，因为这个数据对应的比特位可能被其他一个数据或多个数据占用了。
• 当布隆过滤器判断一个数据不存在是准确的，因为如果该数据存在那么该数据对应的比特位都应该已经被设置为1了。

显然布隆过滤器的效率与哈希函数的个数与过滤器长度息息相关，那么他们之间究竟存在怎样的关系呢？

网上有大佬经过计算得到如下图这样的结论：

感兴趣的这是原文链接->详解布隆过滤器的原理，使用场景和注意事项 – 知乎 (zhihu.com)

 为了简化，我们取k为3，即设计3个哈希函数，最终得到m与n的关系：『 m≈4*n』。

注意：为了简化计算我们取ln2≈0.7。

3.布隆过滤器的模拟实现

注意这里我们需要三个哈希函数，所以需要三个仿函数设计：

//布隆过滤器
template<size_t N, 
    class K = string,         //默认为字符串（常用）
    class Hash1 = BKDRHash,   //三种哈希函数
    class Hash2 = APHash, 
    class Hash3 = DJBHash>
class BloomFilter
{
public:
	//...
private:
	bitset<N> _bs;
};

这三种哈希函数的实现如下，原理感兴趣的自行研究：

struct BKDRHash
{
	size_t operator()(const string& s)
	{
		size_t value = 0;
		for (auto ch : s)
		{
			value = value * 131 + ch;
		}
		return value;
	}
};
struct APHash
{
	size_t operator()(const string& s)
	{
		size_t value = 0;
		for (size_t i = 0; i < s.size(); i++)
		{
			if ((i & 1) == 0)
			{
				value ^= ((value << 7) ^ s[i] ^ (value >> 3));
			}
			else
			{
				value ^= (~((value << 11) ^ s[i] ^ (value >> 5)));
			}
		}
		return value;
	}
};
struct DJBHash
{
	size_t operator()(const string& s)
	{
		if (s.empty())
			return 0;
		size_t value = 5381;
		for (auto ch : s)
		{
			value += (value << 5) + ch;
		}
		return value;
	}
};

3.1布隆过滤器的插入

布隆过滤器当中需要提供一个Set接口，用于插入元素到布隆过滤器当中。插入元素时，需要通过三个哈希函数分别计算出该元素对应的三个比特位，然后将位图中的这三个比特位设置为1即可。

代码如下：

void Set(const K& key)
{
	//计算出key对应的三个位
	size_t i1 = Hash1()(key) % N;
	size_t i2 = Hash2()(key) % N;
	size_t i3 = Hash3()(key) % N;

	//设置位图中的这三个位
	_bs.set(i1);
	_bs.set(i2);
	_bs.set(i3);
}

3.2布隆过滤器的查找

布隆过滤器当中还需要提供一个Test接口，用于检测某个元素是否在布隆过滤器当中。检测时，需要通过三个哈希函数分别计算出该元素对应的三个比特位，然后判断位图中的这三个比特位是否被设置为1。

只要这三个比特位当中有一个比特位未被设置则说明该元素一定不存在。

如果这三个比特位全部被设置，则返回true表示该元素存在。

注意：判断存在的情况可能是误判。

代码如下：

bool Test(const K& key)
{
	//依次判断key对应的三个位是否被设置
	size_t i1 = Hash1()(key) % N;
	if (_bs.test(i1) == false)
	{
		return false; //key一定不存在
	}

	size_t i2 = Hash2()(key) % N;
	if (_bs.test(i2) == false)
	{
		return false; //key一定不存在
	}

	size_t i3 = Hash3()(key) % N;
	if (_bs.test(i3) == false)
	{
		return false; //key一定不存在
	}

	return true; //key对应的三个位都被设置，key存在（可能误判）
}

3.3布隆过滤器不能删除

为什么布隆过滤器不能删除呢？

• 首先我们在布隆过滤器的概念部分已经提到过，布隆过滤器判断一个元素在时可能会出现误判，既然会出现误判，我们如何删除这个可能不存在的元素呢？
• 其次就算要删除的元素确实在布隆过滤器当中，也可能该元素映射的多个比特位当中有些比特位是与其他元素共用的，此时将这些比特位清0也会影响其他元素。

如何让布隆过滤器支持删除？

• 首先要保证要删除的元素在布隆过滤器当中，简单的通过布隆过滤器判断存在后，再确认该昵称是否真正存在，比如通过遍历的方式（这也是布隆过滤器为什么叫过滤器，只能简单过滤，要确保严谨还得加其他手段）。
• 其次保证删除后不会影响到其他元素。可以为位图中的每一个比特位设置一个类似引用计数，当插入元素映射到该比特位时将该比特位的计数值++，当删除元素时将该元素对应比特位的计数值–即可。

那么我们要不要让布隆过滤器支持删除？

• 答案是不要！！
• 布隆过滤器的提出就是为了高效，快速过滤。在删除时还需要遍历文件或磁盘中确认待删除元素确实存在，而文件IO和磁盘IO的速度相对内存来说是很慢的，并且为位图中的每个比特位额外设置一个计数器，就需要多用原位图几倍的存储空间，本末倒置。

4.布隆过滤器的优点

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

5.布隆过滤器的缺陷

1. 有误判率，即存在假阳性（False Position），即不能准确判断元素是否在集合中（补救方法：自建一个白名单，存储可能会误判的数据）
2. 不能获取元素本身。
3. 一般情况下不能从布隆过滤器中删除元素。

6.使用场景

当我们在某网站注册账号需要填入信息时，比如昵称，往往很快地在输入框的右面显示✅或❎以此提示我们该条昵称是否被人注册过。

但是用户的数据往往存储在数据库中，通过网络查询数据库的延迟不会这么快，所以这里一般都是使用了布隆过滤器。

当用户输入信息后，优先到布隆过滤器中查找：

• 如果在布隆过滤器中查找后发现该昵称不存在，则说明该昵称没有被注册过，此时就可以让用户进行注册，并且避免了磁盘IO或者数据库查询。
• 如果在布隆过滤器中查找后发现该昵称存在，此时还需要进一步访问数据库进行复核，确认该昵称是否真的被注册过，因为布隆过滤器在判断元素存在时可能会误判。

通过布隆过滤器的过滤作用，我们可以减轻服务器和数据库的压力，从而提升用户体验。

7.源码

#include<bitset>
struct HashFuncBKDR
{
	// BKDR
	size_t operator()(const string& s)
	{
		size_t hash = 0;
		for (auto ch : s)
		{
			hash *= 131;
			hash += ch;
		}

		return hash;
	}
};

struct HashFuncAP
{
	// AP
	size_t operator()(const string& s)
	{
		size_t hash = 0;
		for (size_t 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 HashFuncDJB
{
	// DJB
	size_t operator()(const string& s)
	{
		size_t hash = 5381;
		for (auto ch : s)
		{
			hash = hash * 33 ^ ch;
		}

		return hash;
	}
};

template<size_t N, 
	class K = string,
	class Hash1 = HashFuncBKDR,
	class Hash2 = HashFuncAP,
	class Hash3 = HashFuncDJB>
class BloomFilter
{
public:
	void Set(const K& key)
	{
		size_t hash1 = Hash1()(key) % M;
		size_t hash2 = Hash2()(key) % M;
		size_t hash3 = Hash3()(key) % M;

		_bs->set(hash1);
		_bs->set(hash2);
		_bs->set(hash3);
	}

	bool Test(const K& key)
	{
		size_t hash1 = Hash1()(key) % M;
		if (_bs->test(hash1) == false)
			return false;

		size_t hash2 = Hash2()(key) % M;
		if (_bs->test(hash2) == false)
			return false;

		size_t hash3 = Hash3()(key) % M;
		if (_bs->test(hash3) == false)
			return false;

		return true; // 存在误判(有可能3个位都是跟别人冲突的，所以误判)
	}

private:
	static const size_t M = 10 * N;
    //STL库中位图实现为静态数组（即int arr[]这种），存储在对象中，数据量大时可能会导致栈溢出，所以这里我们new一个，使用堆空间避免栈溢出
	std::bitset<M>* _bs = new std::bitset<M>;
};

=========================================================================

如果你对该系列文章有兴趣的话，欢迎持续关注博主动态，博主会持续输出优质内容

🍎博主很需要大家的支持，你的支持是我创作的不竭动力🍎

🌟~ 点赞收藏＋关注 ~🌟

=========================================================================