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

03-27 1681阅读

👀樊梓慕：个人主页

🎥个人专栏：《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
class BloomFilter
{
public:
	//...
private:
	bitset _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  3));
			}
			else
			{
				value ^= (~((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  3));
			}
			else              // 奇数位字符
			{
				hash ^= (~((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
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* _bs = new std::bitset;
};

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

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

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

🌟~ 点赞收藏＋关注 ~🌟

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

VPS购买请点击我