当前位置：首页 > article >正文

【C++补充】第二弹---深度解析布隆过滤器与海量数据处理策略

article 2025/1/14 9:19:03

✨个人主页：熬夜学编程的小林

💗系列专栏：【C语言详解】【数据结构详解】【C++详解】

1、布隆过滤器

1.1、什么是布隆过滤器

1.2、布隆过滤器器误判率推导

1.3、布隆过滤器代码实现

1.3.1、基本结构

1.3.2、Set

1.3.3、Test

1.3.4、哈希函数实现

1.3.5、普通测试

1.3.6、误判率测试

1.4、布隆过滤器删除问题

1.5、布隆过滤器的应用

2、海量数据处理问题

1、布隆过滤器

1.1、什么是布隆过滤器

有⼀些场景下面，有大量数据需要判断是否存在，而这些数据不是整形，那么位图就不能使用了，使用红黑树/哈希表等内存空间可能不够。这些场景就需要布隆过滤器来解决。
布隆过滤器是由布隆（Burton Howard Bloom）在1970年提出的⼀种紧凑型的、比较巧妙的概率型数据结构，特点是高效地插入和查询，可以用来告诉你 “某样东西⼀定不存在或者可能存在”，它是用多个哈希函数，将⼀个数据映射到位图结构中。此种方式不仅可以提升查询效率，也可以节省大量的内存空间。
布隆过滤器的思路就是把key先映射转成哈希整型值，再映射⼀个位，如果只映射⼀个位的话，冲突率会比较多，所以可以通过多个哈希函数映射多个位，降低冲突率。
布隆过滤器这里跟哈希表不⼀样，它无法解决哈希冲突的，因为他压根就不存储这个值，只标记映射的位。它的思路是尽可能降低哈希冲突。判断⼀个值key在是不准确的，判断⼀个值key不在是准确的。

1.2、布隆过滤器器误判率推导

推导过程：

说明：这个比较复杂，涉及概率论、极限、对数运算，求导函数等知识，有兴趣且数学功底比较好的可以看细看⼀下，其他uu们记⼀下结论即可！

假设

m：布隆过滤器的bit长度。
n：插入过滤器的元素个数。
k：哈希函数的个数。

布隆过滤器哈希函数等条件下某个位设置为1的概率： $\frac{1}{m}$
布隆过滤器哈希函数等条件下某个位设置不为1的概率： $1-\frac{1}{m}$
在经过k次哈希后，某个位置依旧不为1的概率： $\left ( 1-\frac{1}{m} \right ) ^{k}$

根据极限公式：

添加n个元素某个位置不置为1的概率：

$\left ( 1-\frac{1}{m} \right )^{kn} \approx e^{\frac{-kn}{m}}$

添加n个元素某个位置置为1的概率：

查询⼀个元素，k次hash后误判的概率为都命中1的概率：

结论：
布隆过滤器的误判率为：

由误判率公式可知，在k⼀定的情况下，当n增加时，误判率增加，m增加时，误判率减少。
在m和n⼀定，在对误判率公式求导，误判率尽可能小的情况下，可以得到hash函数个数： k = $\frac{m}{n}\ln 2$ 时误判率最低。

期望的误判率p和插入数据个数n确定的情况下，再把上面的公式带入误判率公式可以得到，通过期望的误判率和插入数据个数n得到bit长度：

1.3、布隆过滤器代码实现

1.3.1、基本结构

布隆过滤器底层还是需要使用位图来实现，因此我们此处用我们自己实现的位图结构，再加一个静态常量表示位图大小。成员函数包括设置标记位和判断标记位。

template <size_t N,        // 插入布隆过滤器的元素数量
	size_t X = 5,          // 每个元素在布隆过滤器中位图中使用的哈希函数的数量
	class K = std::string, // 布隆过滤器可以处理的元素类型
	class Hash1 = HashFuncBKDR,
	class Hash2 = HashFuncAP,
	class Hash3 = HashFuncDJB>
class BloomFilter
{
public:
	void Set(const K& key);
	// 判断key是否在位图结构中，判断不在准
	bool Test(const K& key);
private:
	static const size_t M = N * X;
	lin::bitset<M> _bs;
};

1.3.2、Set

Set函数根据提供的哈希函数将计算得到的bit位设置进位图结构中。

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);
}

注意：此处只实现了三个哈希函数，个数可以根据自己需要提供。

1.3.3、Test

Test函数判断该key值是否在位图结构中，判断不在准，但是判断在不准。

// 判断key是否在位图结构中，判断不在准
bool Test(const K& key)
{
	size_t hash1 = Hash1()(key) % M;
	if (!_bs.test(hash1))
	{
		return false;
	}
	size_t hash2 = Hash2()(key) % M;
	if (!_bs.test(hash2))
	{
		return false;
	}
	size_t hash3 = Hash3()(key) % M;
	if (!_bs.test(hash3))
	{
		return false;
	}

	return true; // 可能存在误判
}

1.3.4、哈希函数实现

struct HashFuncBKDR
{
	// 本算法由于在Brian Kernighan与Dennis Ritchie的《The CProgramming Language》
	// 一书被展示而得名，是一种简单快捷的hash算法，也是Java目前采用的字符串的Hash算法累乘因子为31。
	size_t operator()(const std::string& s)
	{
		size_t hash = 0;
		for (auto ch : s)
		{
			hash *= 31;
			hash += ch;
		}
		return hash;
	}
};

struct HashFuncAP
{
	// 由Arash Partow发明的一种hash算法。  
	size_t operator()(const std::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
{
	// 由Daniel J. Bernstein教授发明的一种hash算法。 
	size_t operator()(const std::string& s)
	{
		size_t hash = 5381;
		for (auto ch : s)
		{
			hash = hash * 33 ^ ch;
		}

		return hash;
	}
};

1.3.5、普通测试

创建一个布隆过滤器对象，将字符串设置进该对象，判断是否出现过。

void TestBloomFilter1()
{
	BloomFilter<10> bf;
	bf.Set("猪八戒");
	bf.Set("孙悟空");
	bf.Set("唐僧");

	cout << bf.Test("猪八戒") << endl;
	cout << bf.Test("孙悟空") << endl;
	cout << bf.Test("唐僧") << endl;
	cout << bf.Test("沙僧") << endl;
	cout << bf.Test("猪八戒1") << endl;
	cout << bf.Test("猪戒八") << endl;
}

1.3.6、误判率测试

误判率测试我们需要做一个对比实验，一个是使用公式计算的误判率，一个是根据实际情况计算的误判率。

公式计算的误判率：

// 获取公式计算出的误判率
double getFalseProbability()
{
	double p = pow((1.0 - pow(2.71, -3.0 / X)), 3.0);

	return p;
}

实际情况计算误判率：

1、相似字符串集：前缀一样，但是后缀不一样，误判率 = 误判的元素个数 / 总个数

2、不相似字符串集：前缀和后缀都不一样，误判率 = 误判的元素个数 / 总个数

void TestBloomFilter2()
{
	srand((unsigned int)time(0));
	const size_t N = 10000;
	BloomFilter<N> bf;
	//BloomFilter<N, 3> bf;
	//BloomFilter<N, 10> bf;

	std::vector<std::string> v1;
	//std::string url = "https://www.cnblogs.com/-clq/archive/2012/05/31/2528153.html";
	//std::string url = "https://www.baidu.com/s?ie=utf-8&f=8&rsv_bp=1&rsv_idx=1&tn=65081411_1_oem_dg&wd=ln2&fenlei=256&rsv_pq=0x8d9962630072789f&rsv_t=ceda1rulSdBxDLjBdX4484KaopD%2BzBFgV1uZn4271RV0PonRFJm0i5xAJ%2FDo&rqlang=en&rsv_enter=1&rsv_dl=ib&rsv_sug3=3&rsv_sug1=2&rsv_sug7=100&rsv_sug2=0&rsv_btype=i&inputT=330&rsv_sug4=2535";
	std::string url = "猪八戒";

	for (size_t i = 0; i < N; ++i)
	{
		v1.push_back(url + std::to_string(i));
	}

	for (auto& str : v1)
	{
		bf.Set(str);
	}

	// v2跟v1是相似字符串集（前缀一样），但是后缀不一样
	v1.clear();
	for (size_t i = 0; i < N; ++i)
	{
		std::string urlstr = url;
		urlstr += std::to_string(9999999 + i);
		v1.push_back(urlstr);
	}

	size_t n2 = 0;
	for (auto& str : v1)
	{
		if (bf.Test(str)) // 误判
		{
			++n2;
		}
	}
	cout << "相似字符串误判率:" << (double)n2 / (double)N << endl;

	// 不相似字符串集  前缀后缀都不一样
	v1.clear();
	for (size_t i = 0; i < N; ++i)
	{
		//string url = "zhihu.com";
		string url = "孙悟空";
		url += std::to_string(i + rand());
		v1.push_back(url);
	}

	size_t n3 = 0;
	for (auto& str : v1)
	{
		if (bf.Test(str))
		{
			++n3;
		}
	}
	cout << "不相似字符串误判率:" << (double)n3 / (double)N << endl;

	cout << "公式计算出的误判率:" << bf.getFalseProbability() << endl;
}

注意：测试代码可以是上面注释的任何一种可能，此处暂时使用上面的源代码进行测试！

1.4、布隆过滤器删除问题

布隆过滤器默认是不支持删除的，因为比如"猪八戒“和”孙悟空“都映射在布隆过滤器中，他们映射的位有⼀个位是共同映射的(冲突的)，如果我们把孙悟空删掉，那么再去查找“猪八戒”会查找不到，因为那么“猪八戒”间接被删掉了。

解决方案：可以考虑计数标记的方式，⼀个位置用多个位标记，记录映射这个位的计数值，删除时，仅仅减减计数，那么就可以某种程度支持删除。但是这个方案也有缺陷，如果⼀个值不在布隆过滤器中，我们去删除，减减了映射位的计数，那么会影响已存在的值，也就是说，⼀个确定存在的值，可能会变成不存在，这⾥就很坑。当然也有人提出，我们可以考虑计数方式支持删除，但是定期重建⼀下布隆过滤器，这样也是⼀种思路。

1.5、布隆过滤器的应用

首先我们分析⼀下布隆过滤器的优缺点：

优点：效率高，节省空间，相比位图，可以适用于各种类型的标记过滤
缺点：存在误判(在是不准确的，不在是准确的)，不好支持删除

布隆过滤器在实际中的⼀些应用：

爬虫系统中URL去重：
- 在爬虫系统中，为了避免重复爬取相同的URL，可以使用布隆过滤器来进行URL去重。爬取到的URL可以通过布隆过滤器进行判断，已经存在的URL则可以直接忽略，避免重复的网络请求和数据处理。
垃圾邮件过滤：
- 在垃圾邮件过滤系统中，布隆过滤器可以⽤来判断邮件是否是垃圾邮件。系统可以将已知的垃圾邮件的特征信息存储在布隆过滤器中，当新的邮件到达时，可以通过布隆过滤器快速判断是否为垃圾邮件，从而提高过滤的效率。
预防缓存穿透：
- 在分布式缓存系统中，布隆过滤器可以用来解决缓存穿透的问题。缓存穿透是指恶意用户请求⼀个不存在的数据，导致请求直接访问数据库，造成数据库压力过大。布隆过滤器可以先判断请求的数据是否存在于布隆过滤器中，如果不存在，直接返回不存在，避免对数据库的无效查询。
对数据库查询提效：
- 在数据库中，布隆过滤器可以用来加速查询操作。例如：⼀个app要快速判断⼀个电话号码是否注册过，可以使用布隆过滤器来判断⼀个用户电话号码是否存在于表中，如果不存在，可以直接返回不存在，避免对数据库进行无用的查询操作。如果在，再去数据库查询进行二次确认。

2、海量数据处理问题

1、10亿个整数里面求最大的前100个

经典topk问题，用堆解决，这个我们数据结构初阶堆章的应用具体讲解过。

堆的应用博客

2、给两个文件，分别有100亿个query，我们只有1G内存，如何找到两个文件交集？

分析：假设平均每个query字符串50byte，100亿个query就是5000亿byte，约等于500G(1G 约等于10亿多Byte)
哈希表/红黑树等数据结构肯定是无能为力的。

解决方案1：这个首先可以用布隆过滤器解决，⼀个文件中的query放进布隆过滤器，另⼀个文件依次查找，在的就是交集，问题就是找到交集不够准确，因为在的值可能是误判的，但是交集⼀定被找到了。

解决方案2：

哈希切分，首先内存的访问速度远大于硬盘，大文件放到内存搞不定，那么我们可以考虑切分为小文件，再放进内存处理。
但是不要平均切分，因为平均切分以后，每个小文件都需要依次暴力处理，效率还是太低了。
可以利用哈希切分，依次读取文件中query，i = HashFunc(query)%N，N为准备切分多少份小文件，N取决于切成多少份，内存能放下，query放进第i号小文件，这样A和B中相同的query算出的hash值 i 是⼀样的，相同的query就进入的编号相同的小文件就可以编号相同的文件直接找交集，不用交叉找，效率就提升了。
本质是相同的query在哈希切分过程中，⼀定进入的同⼀个小文件Ai和Bi，不可能出现A中的的query进入Ai，但是B中的相同query进入了和Bj的情况，所以对Ai和Bi进行求交集即可，不需要Ai和Bj求交集。（本段表述中i和j是不同的整数）
哈希切分的问题就是每个小文件不是均匀切分的，可能会导致某个小文件很大内存放不下。我们细细分析⼀下某个小文件很大有两种情况：
- 1.这个小文件中大部分是同⼀个query。
- 2.这个小文件是有很多的不同query构成，本质是这些query冲突了。
针对情况1，其实放到内存的set中是可以放下的，因为set是去重的。
针对情况2，需要换个哈希函数继续⼆次哈希切分。所以我们遇到大于1G小文件，可以继续读到set中找交集，若set insert时抛出了异常(set插⼊数据抛异常只可能是申请内存失败了，不会有其他情况)，那么就说明内存放不下是情况2，换个哈希函数进⾏⼆次哈希切分后再对应找交集。

3、给⼀个超过100G大小的log file, log中存着ip地址, 设计算法找到出现次数最多的ip地址？查找出现次数前10的ip地址

本题的思路跟上题完全类似，依次读取文件A中ip，i = HashFunc(ip)%500，ip放进Ai号小文件，然后依次用map<string, int>对每个Ai小文件统计ip次数，同时求出现次数最多的ip或者topkip。本质是相同的ip在哈希切分过程中，⼀定进入的同⼀个小文件Ai，不可能出现同⼀个ip进入Ai和Aj的情况，所以对Ai进行统计次数就是准确的ip次数。