海量数据处理-案例
从大量的URL中找出相同的URL
给定a、b两个文件，各存放50亿个URL，每个URL各占64B，内存限制是4G。如何找出a，b两个文件中共同的URL
假设每个URL占64B，50亿个URL文件的大小为320G，无法直接读取到内存中进行处理
解决方法
分治处理
将大文件分解为小文件，通过处理小文件，来保证内存不会溢出。
本题可以将a中的每个URL进行hash(URL) % 1000，得到取模后的hash值
i，将URL保存到对应的 ai 文件中。对于 b 文件，采取相同的处理策略，这样可以保证，共同的URL一点保存在相同hash值对应的ai、bi文件中，然后遍历得到的所有文件，得到全部共同的URL。前缀树
本题的瓶颈是内存不足以存储巨量的数据，可以换一种存储的思路。根据URL的特点可以知道，大部分的URL的前面几个字符都是相同的，可以使用前缀树来减少内存的使用量。同时提升查询的效率。
从大量的数据中找出高频词
有一个1GB大小的文件，文件中的每一行是一个词，每个词的大小不超过 16B，内存的限制是 1MB，要求返回频数最高的 100个词语。
解决方法
分治处理
本题依然是内存不足导致的瓶颈，对于内存不足的问题，使用分治来处理是比较合适的，1MB = 2 ^ 20B = 2 ^ 16 * 16B，可以将 1GB的文件分为5000个小文件，对于 1GB文件中的每个词，进行hash(word) % 5000的处理，将其保存到对应的hash值的文件中。每个小文件中的词语都是相对独立的，也就是某个小文件中的词语是不会出现在其他的小文件中的。
使用 HashMap 来统计词语的频率，遍历所有的小文件，依次读取，更新HashMap的统计值。每统计完一个小文件，就可以丢弃hashmap中存储的数据。
为了得到频率最高的 100个词语，可以建立一个大小为 100 的小根堆，每次更新HashMap的时候，同步更新对应小根堆，如果新统计的词频率大于堆顶的词，就替换堆顶，并重新调整为小根堆
找出某一天访问百度网站最多的IP
现有海量日志数据保存在一个超大的文件中，该文件无法直接读入内存，要求从中提取出某天访问百度最多的那个IP
解决方法
类似上述题目，首先遍历这个超大的文件，从中提取出需要统计的那一天的IP数据到一个文件A中。
对文件A中的IP进行哈希映射，将文件A分为若干个小文件。
对于区分的小文件，使用HashMap来统计每个IP对应的访问频率。
使用一个max变量，实时更新得到最大的访问量的IP地址。
在大量数据中找出不重复的整数
在2.5亿个整数中找出不重复的整数。注意：内存不足以容纳这2.5亿个整数
分治处理
将这2.5亿个整数拆分到多个小文件，使用HashSet找到每个小文件中不重复的整数，再合并每个子结果，得到最终的结果
位图法
位图：使用一个或者多个bit来标记某个元素对应的值，对应的key就是元素。采用位作为单位来存储数据，可以大大节省空间。
位图使用位数组来表示某些元素是否存在。它可以用于快速查找、判重、排序等。
一个整数的范围是 -2^31 ~ 2^31 - 1, 一共有 2^32个key，需要表示的状态有三种分别是1. 没有出现 2. 出现过 1 次 3. 出现过多次
表示状态需要使用 2Bit，所有需要的空间为 2^32 * 2 bit = 2^30B = 1GB的空间。
操作过程：默认的状态是 00，若是存在key，则 00 -> 01 -> 10 -> 10 -> …
遍历结束后，查看位图，把对于位是01的整数输出即可。
使用位图对于内存有特殊的要求
在大量的数据中判断一个数是否存在
- 位图法
- 分治法
分治法的核心在于分治的过程，分治的每个子过程是不会互相影响的，每个分治的子过程都可以独立的得到有效的结果才是合理的分治。
查询最热门的字符串
搜索引擎会通过日志文件把用户每次检索使用的所有查询串都记录下来，每个查询串的长度不超过 255 字节
假设目前有 1000w 个记录 （这些查询串的重复度比较高，虽然总数就是 1000w，但是如果除去重复后，则不超过 300w 个）。请统计最热门的 10 个查询串，要求使用的内存不能超过 1G。(一个查询串的重复度越高，说明查询它的用户越多，也就越热门)
思路：
每个查询串最长为 255B, 1000w个串需要占用约 2.55G 内存，因此，我们无法将所有字符串全部读入到内存中去处理。
解决方法
分治法
划分为多个小文件，保证单个小文件中的字符串能被直接加载到内存中处理，然后求出每个文件中出现次数最多的 10 个字符串；最后通过一个小顶堆统计出所有文件中出现最多的 10 个字符串。
HashMap法
虽然字符串总数比较多，但去重后不超过 300w，因此，可以考虑将所有字符串及出现次数保存在一个 HashMap中，所占用的空间 为 300w*(255 + 4) = 777M，由此可见，1G的内存空间完全够用。
过程
首先，遍历字符串，若不在 map 中，直接存入 map，value 记为 1；若是在 map 中，则把对于的 value 加 1，这一步时间复杂度 O(N)。
接着遍历 map，构建一个 10 个元素的小跟堆，若遍历到的字符串的出现次数大于堆顶字符串的出现次数，则进行替换，并将堆调整为小根堆。
遍历结束后，堆中的10个字符串就是出现次数最多的字符串。这一步时间复杂度为 O(logN)
前缀树法
方法二使用了HashMap来统计次数，当这些字符串有大量的相同前缀的时候，可以考虑使用前缀树来统计字符串出现的次数，树的节点保存字符串出现的次数，0表示没有出现
过程
在遍历字符串的时候，在前缀树中查找，如果找到，则把节点中保存的字符串次数加 1，否则为这个字符串构建新节点，构建完成后把叶子节点中的字符串出现次数设置为1。
最后依然使用小跟堆来堆字符串出现的次数进行统计。
统计不同电话号码的个数
本质是求数据重复的问题，对于这类问题，一般考虑位图法。
8位的电话号码可以表示的号码个数位 10^8 = 1亿个，每个号码使用一个bit来表示，大约需要 12M。
过程
申请一个位图数组，长度为 1亿，初始化为 0。然后遍历所有的电话号码，把号码对于位图中的位置重置为 1。遍历完成后，如果bit 为 1，则表示这个电话号码在文件中存在，否则不存在。bit 值为1的数量就是不同电话号码的个数
从5亿个数中找到中位数
从5亿个数中找到中位数。数据排序后，位置在最中间的就是中位数。当样本数为奇数的时候，中位数为第 (N + 1) / 2个数；当样本数为偶数的时候，中位数为 N / 2个数，与第 (N + 1) / 2 个数的均值
思路
如果没有内存限制，可以将所有数读取到内存中进行排序，时间复杂度为 O(NlogN)
双堆法
维护一个大根堆、一个小根堆，大根堆最大的数小于等于小根堆最小的数，保证这两个堆中元素个数的差不超过 1.
若数据总数为偶数，当这两个堆建好后，中位数就是这两个堆顶元素的平均值。当数据总数为奇数的时候，根据两个堆的大小，中位数一定在数据多的堆的堆顶。
分治法
思路是将一个较大的问题转换为规模较小的问题来求解。
对于这道题，顺序读取这5亿个数字，对于读取到的数字Num，根据最高位为1 或者 0来区分，将之前的所有数，分到两个文件f0、f1中去，划分后，可以很容易的知道中位数在f0还是在f1中，假设f1中有1亿个数，那么中位数一定在f0按照顺序排序的第1.5亿个数中。对于f0可以继续按照次高位来分治，直到分治后的文件可以被加载到内存中去，将文件加载到内存中，直接得到中位数。
如何按照query的频度排序
有10个文件，每个文件大小为 1G，每个文件的每一行存放都是用户的query，每个文件的query都可能重复。要求按照query的频度排序。
思路
如果query的重复度比较大，可以考虑一次性读取全部query处理；如果query的重复度不高，那么可用内存不足以容纳所有query，这时候就需要采用分治法。
HashMap法
如果query的重复度大，说明不同query总数比较小，可用考虑把所有query都加载到内存中的hashmap。接着就可以根据query出现的次数进行排序。
分治法
分治法需要根据数据量的大小以及可用内存的大小来确定问题划分的规模。对于这道题，可用顺序遍历10个文件中的query，通过hash函数hash() % 10将这些query分散到10个小文件中。之后对每个小文件使用HashMap来统计 query出现的次数，根据次数排序并写入到另外一个单独文件中。
接着对所有文件按照query进行排序，这里可以使用归并排序(由于无法把全部query都读入内存，因此需要使用外排序)
如何找出排名前500的数
有20个数组，每个数组有 500个元素，并且有序排列。如何在这 20*500个数中找到前500的数
求Topk，可以使用堆排序，先对这500个数组进行降序排序。建立一个大小为数组个数 20的大根堆，初始化将这20个数组的最大值放入堆中，接着删除堆顶元素，保存到另外一个大小为500的数组中，并将堆顶元素对于数组的下一个元素插入堆中，这样删除500个元素，也就找到了数组所在的下一个元素。