海量数据面试题

前言

什么是海量数据

一、利用位图解决

二、利用布隆过滤器解决

三、利用哈希切割解决

前言

在大数据时代，海量数据处理已成为技术领域中的一项重要课题。无论是企业级应用、互联网平台，还是人工智能和机器学习的实现，都离不开对大规模数据的高效处理。而对于C++开发者来说，如何在面对海量数据时保证系统的高效性和可扩展性，已经成为面试中常见的考察内容。

C++作为一种高性能的编程语言，凭借其接近硬件的操作和精细的内存管理，常常被用于构建对性能要求极高的系统。在海量数据的处理过程中，C++开发者需要不仅具备扎实的基础知识，还需掌握一些特殊的算法和数据结构，以应对各种挑战性的问题。

本篇文章将围绕海量数据处理相关的C++面试题展开，涵盖常见的数据结构、算法优化、内存管理等方面。通过深入分析和解答这些面试题，希望能够帮助读者提升在大规模数据处理中的应对能力，进而在面试中脱颖而出。

什么是海量数据

所谓海量数据，通常指的是超出传统数据库和计算系统处理能力的数据量。这些数据集通常规模庞大，数据类型复杂，可能包含结构化、半结构化和非结构化数据。根据不同的场景，海量数据的规模可以从几GB到几TB，甚至达到PB级别。

面对如此庞大的数据量，传统的单机计算和存储方式往往力不从心，因此需要采用分布式处理框架、数据压缩技术、数据流处理等方法来有效应对。

就比如说，我们熟知一个int类型占4字节空间大小，通过计算4G，内存大概可以存储10亿个int类型的数据，但是如果有人问你，怎么存储100亿呢？现在的电脑是以16G，32G运行内存为主，对于处理100亿个int类型数据，那么就不可以处理。

这不仅仅是空间上的问题，还伴随着时间上的问题。

所以就对于此问题就有了相应的解决方法：

对于时间问题，就可以采用位图、布隆过滤器等数据结构来解决。
对于空间问题，就可以采用哈希切割等方法，将大规模的数据转换成小规模的数据逐个击破。

一、利用位图解决

简单介绍一下位图

对于传统的存储方式，一般是对于整数i，相关信息会存放到容器第i个位置，但是位图不一样，他是对于整数i，相关信息存放到第i个比特位上。所以这就大大减少了时间与空间的消耗。

题目一：给定100亿个整数，设计算法找到只出现一次的整数。

刚才我们也举例了，真要处理起来还真就是不行的，个人的电脑对空间，时间都无法对应解决问题。

但是int的范围是： -2^31到2^32 - 1。所以我们就可以创建一个”大小“（单位为比特）为2^32大小的空间，以可以存储int的所有相关数据。所以我们标记整数时可以将其分为三种状态

出现0次。
出现1次。
出现2次及以上。

一个比特位只能表示两种状态，而要表示三种状态我们至少需要用两个比特位，因此我们可以开辟两个位图，这两个位图的对应位置分别表示该位置整数的第一个位和第二个位。

我们可以将着三种状态分别定义为00、01、10，此时当我们读取到重复的整数时，就可以让其对应的两个位按照00→01→10的顺序进行变化，最后状态是01的整数就是只出现一次的整数。

#include <iostream>
#include <vector>
#include <assert.h>
#include <bitset>
using namespace std;

int main()
{
	//此处应该从文件中读取100亿个整数，但是为了方便演示，就假设已经读取了
	vector<int> v{ 12, 33, 4, 2, 7, 3, 32, 3, 3, 12, 21 };// 假设v里面有100亿个整形数据
	//在堆上申请空间
	bitset<4294967295>* bs1 = new bitset<4294967295>;
	bitset<4294967295>* bs2 = new bitset<4294967295>;
	for (auto e : v)
	{
		if (!bs1->test(e) && !bs2->test(e)) //00->01
		{
			bs2->set(e);
		}
		else if (!bs1->test(e) && bs2->test(e)) //01->10
		{
			bs1->set(e);
			bs2->reset(e);
		}
		else if (bs1->test(e) && !bs2->test(e)) //10->10
		{
			//不做处理
		}
		else //11（不会出现这种，因为我们设定上就是最大为10）
		{
			assert(false);
		}
	}
	// 统计那个整数出现了一次
	for (size_t i = 0; i < 4294967295; i++)
	{
		if (!bs1->test(i) && bs2->test(i)) //01
			cout << i << endl;
	}
	return 0;
}

需要注意以下几点：

存储100亿个整数大概需要40G的内存空间，因此题目中的100亿个整数肯定是存储在文件当中的，代码中直接从vector中读取数据是为了方便演示，我也不能真正去读取100亿个数据，那时间也需要很长。
为了能映射所有整数，位图的大小必须开辟为2^32位，也就是代码中的4294967295，因此开辟一个位图大概需要512M的内存空间，两个位图就要占用1G的内存空间，所以代码中选择在堆区开辟空间，若是在栈区开辟则会导致栈溢出。
最后的检查中循环写的是：for (size_t i = 0; i < 4294967295; i++)，而不是for (int i = INT_MIN; i < INT_MAX; i++)，就是因为位图是无符号类型，不支持负数的表示。如果你想传递负数，需要处理负数的映射。

题目二：给两个文件，分别有100亿个整数，我们只有1G内存，如何找到两个文件的交集？

首先明确一点创建一个存整形的位图需要512M的内存。

方法一：仅使用512M

第一个文件中的数据，我们将其转化为位图，并存储在内存中。
第二个文件中的数据，我们读取其中的所有整数，然后判断在不在位图中，在就是交集，不在就不是交集。

方法二：刚好使用1G

文件 1： 第一个文件中的数据，我们将其转化为位图，并存储在内存中。
文件 2： 第二个文件中的数据，我们按照同样的方式逐块处理。

每次加载文件 1 的一个块并标记其位图后，我们可以将文件 2 的当前块与文件 1 的位图进行比较，计算交集。具体方法是，遍历文件 2 的当前块中的每个整数，并检查文件 1 中的位图对应位置是否为 1。如果是，说明该整数在两个文件中都出现了，这就是交集的一部分。

说明一下： 对于32位的整型，无论待处理的整数个数是多少，开辟的位图都必须有2^32个比特位，也就是512M，因为我们要保证每一个整数都能够映射到位图当中，因此这里位图的空间的消耗是不可避免的，即便位图在规定上不允许存负数。

题目三：一个文件有100亿个整数，1G内存，设计算法找到出现次数不超过2次的所有整数。

该题目和题目一的方法是一样的，在该题目中我们标记整数时可以将其分为四种状态：

出现0次。
出现1次。
出现2次。
出现2次以上。

一个整数要表示四种状态也是只需要两个位就够了，此时当我们读取到重复的整数时，就可以让其对应的两个位按照00→01→10→11的顺序进行变化，最后状态是01或10的整数就是出现次数不超过2次的整数。

#include <iostream>
#include <vector>
#include <assert.h>
#include <bitset>
using namespace std;

int main()
{
	//此处应该从文件中读取100亿个整数，但是为了方便演示，就假设已经读取了
	vector<int> v{ -12, 33, 4, 2, 7, 3, 32, 3, 3, 12, 21 };// 假设v里面有100亿个整形数据
	//在堆上申请空间
	bitset<INT_MAX>* bs1 = new bitset<INT_MAX>;
	bitset<INT_MAX>* bs2 = new bitset<INT_MAX>;
	for (auto e : v)
	{
		if (!bs1->test(e) && !bs2->test(e)) //00->01
		{
			bs2->set(e);
		}
		else if (!bs1->test(e) && bs2->test(e)) //01->10
		{
			bs1->set(e);
			bs2->reset(e);
		}
		else if (bs1->test(e) && !bs2->test(e)) //10->10
		{
			//不做处理
		}
		else //11（不会出现这种，因为我们设定上就是最大为10）
		{
			assert(false);
		}
	}
	// 统计那个整数出现了一次
	for (size_t i = 0; i < 4294967295; i++)
	{
		if ((!bs1->test(i) && bs2->test(i)) || (bs1->test(i) && !bs2->test(i))) //01或10
			cout << i << endl;
	}
	return 0;
}

二、利用布隆过滤器解决

简单介绍一下布隆过滤器

布隆过滤器底层其实是套用的位图，但是在此基础上对第i个位置的相关信息存放到第i个比特位的设定进行了修改，改为了：第i个位置的相关信息存放到第X，Y，Z......（X，Y，Z是通过多个哈希函数计算而得，越多其误差和错误越小）个比特位。

给两个文件，分别有100亿个string，我们只有1G内存，如何找到两个文件的交集？给出近似算法。

题目要求给出近视算法，也就是允许存在一些误判，那么我们就可以用布隆过滤器。

文件 1： 第一个文件中的数据，我们将其转化为布隆过滤器，并存储在内存中。
文件 2： 第二个文件中的数据，我们按照同样的方式逐块处理。

每次加载文件 1 的一个块并标记其布隆过滤器后，我们可以将文件 2 的当前块与文件 1 的布隆过滤器进行比较，计算交集。具体方法是，遍历文件 2 的当前块中的每个string，并检查文件 1 中的布隆过滤器对应位置是否为 1。如果是，说明该string在两个文件中都出现了，这就是交集的一部分。

扩展：如何扩展BloomFilte使得它支持删除元素的操作

如果存放的基数大到一定程度时，那么错误是无法避免的。

所以一般不支持删除，删除一个值可能会影响其他值（）原因如下：

因为布隆过滤器判断一个元素存在时可能存在误判，因此无法保证要删除的元素确实在布隆过滤器当中，此时将位图中对应的比特位清0会影响其他元素。比方说，"qbs"（只出现一次存放在第20个比特位，"sss"（出现多次）也在此，如果删除"qbs"，但是第20个比特位--后不为0，还是会判断"qbs"依旧存在，出现误判。
此外，就算要删除的元素确实在布隆过滤器当中，也可能该元素映射的多个比特位当中有些比特位是与其他元素共用的，此时将这些比特位清0也会影响其他元素。

如果要让布隆过滤器支持删除，也可以，比方说：用多个位标记一个值，存引用计数，但是这样话，空间消耗的就变大了。得不偿失！！！

三、利用哈希切割解决

给两个文件，分别有100亿个string，我们只有1G内存，如何找到两个文件的交集？给出精确算法。

还是刚才那道题目，但现在要求给出精确算法，那么就不能使用布隆过滤器了，此时需要用到哈希切分。

首先需要估算一下这里一个文件的大小，便于确定将一个文件切分为多少个小文件。
假设平均每个string为20字节，那么100亿个strng就是200G，由于我们只有1G内存，这里可以考虑将一个文件切分成400个小文件。
我们决定要分割成400个小文件后，就需要创建400个文件，然后先访问前1G的数据，然后通过哈希函数，计算其应该被分到第几个文件。
需要注意的是，对于两个文件的分割必须使用同一个哈希函数。

这里就拿其中一个文件举例

切割完成后，每一个小文件都是512M的数据，那么我们就可以通过上面的思路求其交集

那各个小文件之间又应该如何找交集呢？

经过哈希切分后，理论上每个小文件的平均大小约为 512MB，因此我们可以将其中一个小文件加载到内存，并将其内容存入一个 set 容器中。然后，遍历另一个小文件中的查询（string），依次判断每个查询是否存在于 set 容器中。如果存在，则该查询为交集元素；如果不存在，则不是交集。
然而，由于哈希切分并不一定会将文件平均切分，有些小文件的大小可能仍然超过 1GB。在这种情况下，如果与之对应的另一个小文件的大小小于 1GB，我们可以将该小文件加载到内存进行查询，因为我们只需要将其中一个小文件加载到内存。
但如果两个小文件的大小都大于 1GB，我们可以考虑对这两个小文件再进行一次切分，将它们切成更小的文件。这一过程与之前对 A 文件和 B 文件的切分方法类似，具体就是通过哈希函数将其再次分割成多个更小的文件，然后分别加载其中的一个小文件到内存进行交集计算。

本质这里在进行哈希切分时，就是将这些小文件看作一个个的哈希桶，将大文件中的string通过哈希函数映射到这些哈希桶中，如果是相同的string，则会产生哈希冲突进入到同一个小文件中。