由散列表到BitMap的概念与应用（三）：面试中的海量数据处理

面试题

在面试软件开发工程师时，经常会遇到海量数据排序和去重的面试题，特别是大数据岗位。

例1：给定a、b两个文件，各存放50亿个url，每个url各占64字节，内存限制是4G，找出a、b文件共同的url?

如何解答

针对上述问题，我们分治算法的思想。

step1

遍历文件a，对每个url求取hash(url)00，然后根据所取得的值将url分别存储到1000个小文件(记为a0,a1,…,a999，每个小文件约300M)，为什么是1000？主要根据内存大小和要分治的文件大小来计算，我们就大致可以把320G大小分为1000份，每份大约300M。

step2

遍历文件b，采取和a相同的方式将url分别存储到1000个小文件(记为b0,b1,…,b999)。

文件a的hash映射和文件b的hash映射函数要保持一致，这样的话相同的url就会保存在对应的小文件中。比如，如果a中有一个url记录data1被hash到了a99文件中，那么如果b中也有相同url，则一定被hash到了b99中。

所以现在问题转换成了：找出1000对小文件中每一对相同的url（不对应的小文件不可能有相同的url）

step3

因为每个小文件大约300M，所以我们再可以采用上面解答中的想法。

解题思路

常见的高效解答思路有：堆排序法、分治策略和BitMap(位图法)。

堆排序法

堆排序是4种平均时间复杂度为nlogn的排序方法之一，其优点在于当求M个数中的前n个最大数，和最小数的时候性能极好。所以当从海量数据中要找出前m个最大值或最小值，而对其他值没有要求时，使用堆排序法效果很好。

从1亿个整数里找出100个最大的数

这里采用堆排序将空间复杂度讲得很低，要排序1亿个数，但一次性只需读取100个数字，或者设置其他基数，不需要一次性读完所有数据，降低对内存要求。

分治策略

总体思想：分而治之。通过分治将大数据变成小数据进行处理，再合并。

首先区分内部排序和外部排序：

步骤：

其次要注意待排序数据的特点。如果待排序数据具有某些特点，往往能够有更加有效的方法解决。

同时，这种思想也更加贴近大数据应用的思维方式。

BitMap(位图法)

32位机器上，一个整形，比如int a; 在内存中占32bit位，可以用对应的32bit位对应十进制的0-31个数，BitMap算法利用这种思想处理大量数据的排序与查询.

其优点是运算效率高，不许进行比较和移位，且占用内存少，比如N=10000000；只需占用内存为N/8=1250000Byte=1.25M。

解答示例

例2：在特定的场合下：

对10亿个不重复的整数进行排序。

找出10亿个数字中重复的数字。

如上的题目一般会限制内存。

我们换一个与上面示例相似的题目进行演示解答过程。

例3：一台主机，2G内存，40亿个不重复的没排过序的unsigned int的整数的文件，然后再给一个整数，如何快速判断这个整数是否在那40亿个数当中？

我们可以有几种方法解答如上的题目。

遍历法

如果内存足够将40亿个数全部放到内存中，逐个遍历，此时时间复杂度为O(N)。可是现在在内存不足，需要分批读一部分数据到内存然后在做判断，加上I/O操作的时间，时间复杂度远远大于O(N)。

这时，性能问题主要集中在I/O操作，和遍历数组上。那么有没有降低时间复杂度的方法呢？答案是肯定的，如果我们假定内存是足够的，只去优化时间，可以得到下面的方法。

直接寻址表法

申请一个4G超大数组char a[0~2^32-1]，将文件中出现的数字置为1，没有出现的置为0。

例如文件存在一个整数1000022，就将a[100002211]=1。

a012…2^32-1

value

1

0

1

0

0

这时时间复杂度为O(1)，可是空间问题还没有解决。分析下我们的算法，以所需判断的整数为数组下标，用0/1来区分整数是否在。一共用了一个字节来作为标记位，而事实上1Bit就足够标记了。如果能把这部分空间优化掉，4G/8 < 2G 那么就可以解决问题了。看下面的方法。

BitMap

在前面两篇文章中，我们讲过BitMap的概念和应用。

将整数映射到bit上，例如整数10，10/8=1，10%8=2大数据排序，那么就将a[1]的b[2]置为1。这样时间复杂度即是O(1)，内存也得到了压缩。

a012…2^32/8-1

bit

0 1 2 3 4 5 6 7

0 1 2 3 4 5 6 7

0 1 2 3 4 5 6 7

0 1 2 3 4 5 6 7

0 1 2 3 4 5 6 7

flag

0 0 0 0 0 0 0 0

0 0 1 0 0 0 0 0

0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0

逆向思维优化

unsinged int只有接近43亿（unsigned int最大值为2^32-1=4294967295,最大不超过43亿），我们还可以用某种方式存储没有出现过的3亿个数（使用数组{大小为3亿中最大的数/8 bytes}存储），如果出现在3亿个数里面，说明不在40亿里面。3亿个数存储空间一般小于40亿个。ps：存储4294967296（不到43亿）需要512MB， 而存储294967296只需要35.16MB。

这里需要注意的是，BitMap排序需要的时间复杂度和空间复杂度依赖于数据中最大的数字。当数据类似（1，1000，10万）只有3个数据的时候，用BitMap时间复杂度和空间复杂度相当大，只有当数据比较密集时才有优势。

总结

在处理海量数据时，我们会想到这些数据的存储结构。在所有具有性能优化的数据结构中，大家使用最多的就是hash表，是的，在具有定位查找上具有O(1)的常量时间，多么的简洁优美。但是数据量大了，内存就不够了。当然也可以使用类似外排序来解决问题的，由于要走IO所以时间上又不行。BitMap基于位的映射，用一个Bit位来标记某个元素对应的Value， 而Key即是该元素。由于采用了Bit为单位来存储数据，因此BitMap在存储空间方面，可以大大节省。

本文总结了几种常用的海量数据处理方法，我们可以根据实际的题意（空间、时间限制）进行灵活应用。了解散列表和BitMap可以参见前面两篇文章。

思考

最后，留一个思考题给大家，和上面的解答过程类似，有兴趣的可以在文章下面留言讨论。

例4：现有3G的数据量，数据类型为整型，找出其中重复的数据。

数据：每个数据不大于20亿，且每个数据最多重复一次。

内存：最多用300M的内存进行操作。

参考大数据排序算法：外部排序，bitmap算法；大数据去重算法：hash算法，bitmap算法大量数据去重：Bitmap和布隆过滤器(Bloom Filter)

（编辑：拼字网 - 核心网）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!