海量数据处理

数据结构¶

Bloom Filter布隆过滤器¶

一种空间效率很高的随机数据结构，它利用位数组很简洁地表示一个集合，并能判断一个元素是否属于这个集合。它是一个判断元素是否存在集合的快速的概率算法。Bloom Filter有可能会出现错误判断，但不会漏掉判断。也就是Bloom Filter判断元素不再集合，那肯定不在。如果判断元素存在集合中，有一定的概率判断错误。
思想：理是，当一个元素被加入集合时，通过K个Hash函数将这个元素映射成一个位阵列（Bit array）中的K个点，把它们置为1。检索时，我们只要看看这些点是不是都是1就（大约）知道集合中有没有它了：如果这些点有任何一个0，则被检索元素一定不在；如果都是1，则被检索元素很可能在。这就是布隆过滤器的基本思想。

Hash¶

Bit-map¶

用一个bit位来标记某个元素对应的值。由于采用了Bit为单位来存储数据，因此在存储空间方面，可以大大节省。
可以应用于对不重复数据排序（计数排序）

trie字典树¶

前缀统计、词频统计

外排序¶

适用于对大数据排序、去重
外排序是处理那些无法全部装入内存的大文件的排序方法。因为数据不能完全放在内存中，外排序使用磁盘或其他外部存储来处理数据。其中，最经典的外排序方法是多路归并排序。
过程
分阶段（Split Phase）:
- 将大文件分为多个小文件块。每个文件块的大小应该适合放在内存中。
- 将每个小文件块加载到内存中并使用合适的内部排序算法（如快速排序、堆排序等）进行排序。
- 将排序后的小文件块写回到磁盘。
归并阶段（Merge Phase）:
- 使用多路归并技术合并小文件块。多路归并意味着在每一次归并步骤中，你可能会合并多个（超过两个）排序块。
- 使用一个优先队列或者小顶堆来从每个小文件块中选出最小的元素并输出到结果文件。每当一个元素被选中并输出，就从相应的文件块中读入下一个元素。
- 重复上述过程，直到所有的小文件块都被完全处理完。
输出:
- 当所有的小文件块都被合并，结果文件就是排序后的版本。

案例¶

常用hash取模分治

海量日志数据，提取出某日访问百度次数最多的那个IP¶

算法思想：分而治之+Hash

IP地址最多有2^32=4G种取值情况，所以不能完全加载到内存中处理；
可以考虑采用“分而治之”的思想，按照IP地址的Hash(IP)%1024值，把海量IP日志分别存储到1024个小文件中。这样，每个小文件最多包含4MB个IP地址；
对于每一个小文件，可以构建一个IP为key，出现次数为value的Hash map，同时记录当前出现次数最多的那个IP地址；
可以得到1024个小文件中的出现次数最多的IP，再依据常规的排序算法得到总体上出现次数最多的IP；

搜索引擎会通过日志文件把用户每次检索使用的所有检索串都记录下来，每个查询串的长度为1-255字节。假设目前有一千万个记录（这些查询串的重复度比较高，虽然总数是1千万，但如果除去重复后，不超过3百万个。一个查询串的重复度越高，说明查询它的用户越多，也就是越热门。），请你统计最热门的10个查询串，要求使用的内存不能超过1G。¶

可以在内存中处理，典型的Top K算法

算法思想：hashmap+堆

先对这批海量数据预处理，在O（N）的时间内用Hash表完成统计；
借助堆这个数据结构，找出Top K，时间复杂度为O(N*logK)。
TopK：假设要找最大的K个元素，创建一个大小为K的最小堆，对于数据集中的每一个元素，检查它是否大于最小堆的顶部元素：如果是，删除堆顶元素并插入当前元素；如果否，继续处理数据集的下一个元素。
或者：采用trie树，关键字域存该查询串出现的次数，没有出现为0。最后用10个元素的最小推来对出现频率进行排序。

有一个1G大小的一个文件，里面每一行是一个词，词的大小不超过16字节，内存限制大小是1M。返回频数最高的100个词。¶

算法思想：分而治之 + hash统计 + 堆排序

顺序读文件中，对于每个词x，取hash(x)%5000，然后按照该值存到5000个小文件（记为x0,x1,...x4999）中。这样每个文件大概是200k左右。如果其中的有的文件超过了1M大小，还可以按照类似的方法继续往下分，直到分解得到的小文件的大小都不超过1M。
对每个小文件，采用trie树/hash_map等统计每个文件中出现的词以及相应的频率。
取出出现频率最大的100个词（可以用含100个结点的最小堆）后，再把100个词及相应的频率存入文件，这样又得到了5000个文件。最后就是把这5000个文件进行归并（类似于归并排序）的过程了。

有10个文件，每个文件1G，每个文件的每一行存放的都是用户的query，每个文件的query都可能重复。要求你按照query的频度排序。¶

方案1：

算法思想：分而治之 + hash统计 + 堆排序

顺序读取10个文件，按照hash(query)%10的结果将query写入到另外10个文件中（常见划分，好处：相同元素在一起）。这样新生成的文件每个的大小大约也1G，大于1G继续按照上述思路分。
找一台内存在2G左右的机器，依次对用hash_map(query, query_count)来统计每个query出现的次数。利用快速/堆/归并排序按照出现次数进行排序。将排序好的query和对应的query_cout输出到文件中。这样得到了10个排好序的文件（记为）。
对这10个文件进行归并排序（内排序与外排序相结合）。

方案2：

算法思想：hashmap+堆

一般query的总量是有限的，只是重复的次数比较多而已，可能对于所有的query，一次性就可以加入到内存了。这样，我们就可以采用trie树/hash_map等直接来统计每个query出现的次数，然后按出现次数做快速/堆/归并排序就可以了。

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

方案1：可以估计每个文件安的大小为5G×64=320G，远远大于内存限制的4G。所以不可能将其完全加载到内存中处理。考虑采取分而治之的方法。

算法思想：分而治之 + hash统计

遍历文件a，对每个url求取hash(url)%1000，然后根据所取得的值将url分别存储到1000个小文件（记为a0,a1,...,a999）中。这样每个小文件的大约为300M。

遍历文件b，采取和a相同的方式将url分别存储到1000小文件（记为b0,b1,...,b999）。这样处理后，所有可能相同的url都在对应的小文件（a0vsb0,a1vsb1,...,a999vsb999）中，不对应的小文件不可能有相同的url。然后我们只要求出1000对小文件中相同的url即可。

求每对小文件中相同的url时，可以把其中一个小文件的url存储到hash_set中。然后遍历另一个小文件的每个url，看其是否在刚才构建的hash_set中，如果是，那么就是共同的url，存到文件里面就可以了。

方案2：如果允许有一定的错误率，可以使用Bloom filter，4G内存大概可以表示340亿bit。将其中一个文件中的url使用Bloom filter映射为这340亿bit，然后挨个读取另外一个文件的url，检查是否与Bloom filter，如果是，那么该url应该是共同的url（注意会有一定的错误率）。

在2.5亿个整数中找出不重复的整数，注，内存不足以容纳这2.5亿个整数。¶

采用2-Bitmap（每个数分配2bit，00表示不存在，01表示出现一次，10表示多次，11无意义）进行，共需内存2^32 * 2 bit=1 GB内存，还可以接受。然后扫描这2.5亿个整数，查看Bitmap中相对应位，如果是00变01，01变10，10保持不变。所描完事后，查看bitmap，把对应位是01的整数输出即可。

40亿个不重复的unsigned int的整数，没排过序的，然后再给一个数，如何快速判断这个数是否在那40亿个数当中？¶

方案1：申请512M的内存，一个bit位代表一个unsigned int值。读入40亿个数，设置相应的bit位，读入要查询的数，查看相应bit位是否为1，为1表示存在，为0表示不存在。

方案2：因为2^32为40亿多，所以给定一个数可能在，也可能不在其中（范围差距不大）；可以使用字典树。