如何处理海量数据

目录

1.海量数据简介

海量数据的产生

海量数据的处理

2.利用位图解决

题目一

题目二 

题目三

题目一变形

3.利用布隆过滤器解决

题目一

4.哈希切割解决

题目一

题目二

5.海量数据处理总结

1.海量数据简介

海量数据的产生

随着互联网的迅速发展，互联网已经深度融合进了人们的生活，随处可见互联网的影子，数据来源日益丰富；人们对互联网的依赖，这些数据源不断产生大量数据，形成了前所未有的数据规模。并且随着人口规模的增加，互联网中的数据增长只会越来越快，越来越多。

并且，在大数据中隐藏着巨大的商业价值和社会价值。通过对海量数据的分析，企业可以洞察市场趋势、消费者行为、产品偏好等，从而做出更精准的决策，优化资源配置，提升竞争力。因此，这要求我们必须有高效的海量数据处理技术来应对。

海量数据的处理

处理海量数据时，因为数据量太大，所以通常是存储在磁盘空间，可以理解为存储在文件中；而这些大量的数据通常是无法直接加载到内存中，但是程序的运行必须要加载到内存中，这个时候，我们就需要考虑如何利用有限的内存空间，处理大量的数据？

思路一：节约的思想 —— 减少数据在内存中所占用的空间。

比如：存储一个整形数据需要占用4字节的空间，那么存储十亿个整形数据就需要占用40亿个字节的空间，换算成GB的话大约是4GB；但是如果我们能利用计算机中的最小单位bit位来标记这十亿个整数的话，就能大大的减少内存空间的占用。我们可以算一下，1字节 == 8bit位，一个整形就需要32个bit位，如果用1个bit位来标记一个整形数据，那么，标识一个整形数据就能节省31个bit位，标识十亿个整形数据就能节省310个bit位，大约是3.61GB。因此，节约的思想是处理海量数据时一种非常实用的思想。

思路二：分批的思想 —— 分批次的将大量的数据加载进内存中处理。

比如：一个文件中有100亿个字符串数据需要我们处理，这个时候我们就可以把这个大文件分割成多个小文件，然后依次处理每个小文件，也就是进行逐个击破；如果小文件还是太大了，小问题，继续切分。直到切分出的小文件能够加载到内存空间中处理为止。分批处理的思想也是处理海量数据的一种实用思想。

如果使用节约的思想，我们可以尝试使用位图和布隆过滤器来解决海量数据的问题，如果你不了解位图和布隆过滤器，可以参考这两篇文章 —— 位图 、布隆过滤器。

如果使用分批的思想，我们可以尝试使用哈希切割的方法。（文章后面会讲解哈希切割）

当然，路是死的，人是活的，我们还可以将两种方法结合使用，这样就能处理更多的数据了。接下来，笔者我将针对两种思想进行例题讲解。

2.利用位图解决

题目一

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

思路一：使用map

着眼一看，这不就是个统计次数的问题吗？嗯，可以使用STL中的map解决，但是别忘了，这是100亿个整数啊，前面我们算过，存储十亿个整形数据需要4GB的内存空间，那么存储100亿个整形数据，就需要40GB的内存空间，内存铁铁装不下，我们可以考虑使用位图解决。

思路二：位图

如果使用位图来解决，我们可以如何使用位图呢？要知道，位图中的bit位只有两个取值，只能表示两种状态；如果将该题目中的状态划分为两种状态，那只能是出现次数是一次的整数和出现次数不是一次的整数。OK我们可以尝试使用这种思路来解决一下。

数据是几，就映射第几个bit位；没有出现的数据对应的bit位肯定是0，数据出现之后，对应的bit位加1，如：2和4。判断6的时候，出现第一个6的时候，将对应的bit位置为1，出现第二个6的时候怎么办呢？好像没有办法了，毕竟bit位只有两个取值；所以一个位图是解决不了这个问题的。

一个位图不行就增加一个位图，即使是增加一个位图，空间成本也足够低。下面，我们看看如果使用两个位图解决这个问题吧。

我们可以使用两个长度相等的位图，两个位图中相同位置的bit位共同判断。这个时候，一个位置就有四种状态了，分别是 00、01 、10、11 ；我们可以使用00表示数据出现了0次，使用01表示数据出现了1次，使用10表示数据出现了1次以上，使用11表示…… 额，不需要了，用三种状态就足够了。​

还是这组数据，通过上面的约定之后，我们很轻松的就完成了数据的映射工作。映射完数据之后，我们只需要判断相同位置的bit位组合是否为01来判断数据是否出现了一次。 

 封装两个位图的类，调用其中的接口即可；代码如下所示：

	template<size_t N>
	class two_bit_set
	{
	public:
		void set(size_t x)
		{
			// 00 -> 01
			if (_bs1.test(x) == false
				&& _bs2.test(x) == false)
			{
				_bs2.set(x);
			}
			else if (_bs1.test(x) == false
				&& _bs2.test(x) == true)
			{
				// 01 -> 10
				_bs1.set(x);
				_bs2.reset(x);
			}
		}

		bool test(size_t x)
		{
			if (_bs1.test(x) == false
				&& _bs2.test(x) == true)
			{
				return true;
			}

			return false;
		}
	private:
		bitset<N> _bs1;
		bitset<N> _bs2;
	};

题目二 

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

题目分析：

一个文件中就有100亿个整数，前面我们分析过，存储100亿个整数需要40GB的内存空间，所以我们可以使用位图来映射，以减少内存空间的使用；

那我们需要多少个bit位呢？100亿个整数是不是需要100亿bit位呢？非也，整形数据的取值范围是-2,147,483,648 ~ 2,147,483,647；满打满算也才42亿九千多万个数据，根据鸽巢原理可知，其中必然出现重复的数据，也就是说，我们要映射所有的整形数据，只需要42亿九千多万个bit位，因此，我们得出一个重要的结论 “使用位图处理海量数据时，开多少个bit位与数据量无关，而是取决于数据类型所能表示的范围” ，42亿九千多万个bit位大约等于511.367MB。

我们有1GB的内存，因此，我们最多可以使用两个位图来解决这个问题。

使用一个位图解决：

先读取一个文件中的数据，映射到位图中，再读取另一个文件中的数据，检测该数据所映射的bit位是否为1，如果bit位已经为1，说明该数据是交集。

使用两个位图解决：

将A文件中的数据映射到第一个位图中，将B文件中的数据映射到第二个位图中，将两个位图中对应位置进行按位与操作；结果为1，则表示这个数是交集。

题目三

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

题目分析：这个题目和题目一类似，我们依然可以使用两个位图来解决。两个位图中对应的位置配合起来，可以表示4种情况；00表示该数据出现0次，01表示该数据出现1次，10表示该数据出现2次，11表示该数据出现3次及以上。

除了11这种情况之外，其他所有情况都要统计。

题目一变形

给定100亿个整数，我们只有512MB内存，设计算法找到只出现一次的整数？

题目分析：

在题目二中，我们讨论过，100亿个整数映射到位图中大约需要511.367MB的内存空间；这道题和题目一高度相似，题目一我们是利用两个位图解决的，并且最少需要两个位图，使用了大概1G左右的内存空间；相比于题目一，这道题又添加了限制条件512MB内存，也就是说数据量没减少，但我们只能使用一半的内存。

那我们能不能 不使用两个位图呢？不行，这一点在题目一中已经分析过了。那怎么办呢？别忘了，处理海量数据，除了节约的思想，我们还有分批的思想，题目又没说要一次将数据全部加载到内存中，既然空间少了一半，那我们就多加载一次，并且每次只加载一半的数据。

那我们该如何分批处理呢？别忘了，数据是有大小的，我们可以先处理数据范围前一半的数据，再处理后一半的数据，代价就是要多遍历几次文件。

我们假设数据范围是 0 ~ 2^32-1，第一次加载时，将 0 ~ 2^31-1范围的数据通过直接映射的方式映射到位图中，根据我们定义的规则判断该范围中的哪些数据出现了一次。

第二次加载时，将 2^31 ~ 2^32-1 范围的数据 减去2^31 之后映射到位图中，再根据我们定义的规则判断该范围中的哪些数据出现了一次。

这样一来，我们就利用512MB的空间统计出了100亿个整数中只出现一次的整数了。这个变形题中，我们使用了节约和分批两种思想，读者可以细细体会。

3.利用布隆过滤器解决

题目一

题目一：给两个文件，分别有100亿个字符串，我们只有1G内存，如何找到两个文件交集？给出近似算法即可。

题目分析：

一个文件中有100亿个字符串，假设一个字符串平均占用20字节的空间，就需要2000亿个字节，也就是200GB；我们可以采用节约的思想解决该问题，因为映射的数据是字符串类型的，并且题目要求给出近似算法即可，也就是说允许存在误判，那么我们可以使用布隆过滤器来解决这个问题。

先读取一个文件中的内容映射到布隆过滤器中，再读取另一个文件中的内容映射到布隆过滤器中，如果该数据映射的所有bit位都为1，则判断存在交集。

4.哈希切割解决

题目一

题目一：给两个文件，分别有100亿个字符串，我们只有1G内存，如何找到两个文件交集？给出精确算法。

题目分析：

这个题目和上面那个题目是一样的，但是要求我们给出精确算法，因此，我们不能再使用布隆过滤器了。前面我们分析过，假设一个字符串平均占用20字节，一个文件就需要整整200GB的空间，而且有两个文件，就需要400GB的空间；全部同时加载到内存中肯定不行，我们可以利用分批的思想，将这两个大文件分割成具有编号的、一个个的小文件。

那根据什么来分呢？我们可以利用字符串哈希算法，将字符串映射成一个个的整数，该整数就是该字符串所在小文件的编号。这样一来我们就将大文件中的字符串映射到了不同的小文件中，这就是哈希切割的思想。

注意：映射两个大文件中的字符串的时候，我们需要使用同一个字符串哈希算法，这样才能确保两个大文件中的相同字符串 能够进入各自相同编号的小文件中。

当我们将字符串映射到小文件中之后，因为我们划分成了1000份小文件，平均每一个小文件就是0.1GB，是可以加载到内存中的。因此，我们可以直接读取到内存中处理；因为是找交集，我们只需要知道一个数据是否出现过即可，因此，我们可以使用STL中的set依次处理相同编号的小文件即可。

一个可能出现的问题 —— 子文件过大

因为相同的字符串和产生哈希冲突的字符串都是进入相同编号的小文件中，小文件过大有以下两种情况

情况一：重复的字符串过多，导致小文件过大。这种情况是不影响处理的，因为我们使用的是set，具有去重的功能。

情况二：冲突的字符串太多，导致小文件过大。这种情况下读取到内存中，会导致set抛异常，一旦set抛异常，说明小文件中冲突的字符串太多，需要换一个哈希函数继续切分。

题目二

题目二：给一个超过100G大小的log file, log中存着IP地址, 设计算法找到出现次数最多的IP地址？与上题条件相同，如何找到top K的IP？

第一问

题目分析：与上题类似，都是数据量上百亿的大文件，因此，我们直接使用哈希切割。依次读取每个ip，i = hashfunc(ip)%1000，i是几，该ip就进入第几个小文件中。相同的ip计算出的i肯定相同，可以进入相同的小文件中。

此时，我们可以使用STL中的map依次处理每一个小文件来统计次数；如果map抛异常，说明冲突的数据量过多，当前小文件过大，我们需要换哈希函数，进行二次切分。

第二问

题目分析：

和第一问一样，我们可以使用哈希切分将大文件分割成一个个的小文件，保证相同的ip进入同一个编号的小文件；此时，我们可以使用堆这种数据结构来处理每个小文件，对应STL中的priority_queue。我们可以在堆中存放一个个的pair<string,int>类型的键值对，自定义的比较规则为根据pair<string，int>中的第二个数据来比较。

5.海量数据处理总结

在处理海量数据问题时，我们可以使用两种思想，一种是节约的思想，一种是分批的思想。当然两种思想也可以同时使用。

如何使用节约思想呢？

节约，我们节约的是内存空间，使用占用内存小的数据结构来解决，比如位图、布隆过滤器等……

如何使用分批的思想呢？

分批就是多分几批来处理，如果再对分批进行优化，我们可以使用哈希切割，哈希切割时更高级的分批思想。