海量数据处理之--哈希分治

方法介绍
对于海量数据而言，由于无法一次性装进内存处理，不得不把海量的数据通过hash 映射的方法分割成相应的小块数据，然后再针对各个小块数据通过hash_map 进行统计或其他操作。那什么是hash 映射呢？简单来说，就是为了便于计算机在有限的内存中处理大数据，我们通过一种映射散列的方式让数据均匀分布在对应的内存位置（如大数据通过取余的方式映射成小数据存放在内存中，或大文件映射成多个小文件），而这种映射散列的方式便是我们通常所说的hash 函数，好的hash 函数能让数据均匀分布而减少冲突。

 

1. 寻找TOP IP
海量日志数据，提取出某日访问百度次数最多的那个IP。分析：百度作为国内第一大搜索引擎，每天访问它的IP 数量巨大，如果想一次性把所有IP 数据装进内存处理，则内存容量通常不够，故针对数据太大，内存受限的情况，可以把大文件转化成（取模映射）小文件，从而大而化小，逐个处理。换言之，先映射，而后统计，最后排序。解法：具体分为以下3 个步骤。
1. 分而治之/hash 映射。首先将该日访问百度的所有IP 从访问日志中提取出来，然后逐个写入到一个大文件中，接着采取Hash 映射的方法（比如hash(IP) % 10003），把整个大文件的数据映射到1000 个小文件中。
2. hash_map 统计。当大文件转化成了小文件，那么我们便可以采用hash_map(ip, value)来分别对1000个小文件中的IP 进行频率统计，找出每个小文件中出现频率最大的IP，总共1000 个IP。

3. 堆/快速排序。统计出1000 个频率最大的IP 后，依据它们各自频率的大小进行排序（可采取堆排序），找出那个出现频率最大的IP，即为所求。

 

2. 寻找热门查询
搜索引擎会通过日志文件把用户每次检索所使用的所有查询串都记录下来，每个查询串的长度为1-255 字节。假设目前有1000 万个查询记录（但因为这些查询串的重复度比较高，所以虽然总数是1000万，但如果除去重复后，不超过300 万个查询字符串），请统计其中最热门的10 个查询串，要求使用的内存不能超过1G。一个查询串的重复度越高，说明查询它的用户越多，也就是越热门。
分析：如果是一亿个IP 求Top 10，可先%1000 将IP 分到1000 个小文件中去，并保证一种IP 只出现在一个文件中，再对每个小文件中的IP 进行hash_map 统计并按数量排序，最后用归并或者最小堆依次处理每个小文件的top 10 以得到最后的结果。
但对于本题，数据规模比较小，能一次性装入内存。因为根据题目描述，虽然有1000 万个Query，但是由于重复度比较高，故去除重复后，事实上只有300 万的Query，每个Query 为255Byte，因此我们可以考虑把他们全部放进内存中去（假设300 万个字符串没有重复，都是最大长度，那么最多占用内存3M 1K/4= 0.75G，所以可以将所有字符串都存放在内存中进行处理）。
所以我们放弃分而治之/hash 映射的步骤，直接用hash_map 统计，然后排序。事实上，针对此类典型的TOP K 问题，采取的对策一般都是：分而治之/hash 映射（如有必要） + hash_map + 堆。

解法：
1. hash_map 统计。先对这批海量数据进行预处理，用hash_map 完成频率统计。具体做法是：维护一个Key 为Query，Value 为该Query 出现次数的hash_map，即hash_map(Query, Value)，每次读取一个Query，如果该Query 不在hash_map 中，那么将该Query 放入hash_map 中，并将它的Value 值设为1；如果该Query在hash_map 中，那么将该Query 的计数Value 加1 即可。最终我们用hash_map 在O(n)的时间复杂度内完成了所有Query 的频率统计。
2. 堆排序。借助堆这个数据结构，找出Top K，时间复杂度为N'O(logK)。即借助堆结构，我们可以在log 量级的时间内查找或调整移动。因此，维护一个K(该题目中是10)大小的小根堆，然后遍历300 万的Query，分别和根元素进行比较。所以，最终的时间复杂度是：O(n) + N' O(logK），其中，N 为1000万，N'为300 万。关于第2 步堆排序，进一步讲，可以维护k 个元素的最小堆，即用容量为k 的最小堆存储最先遍历到的k 个数，并假设它们即是最大的k 个数，建堆费时O(k)，并调整堆(每次调整堆费时O(logk))后，有k1 >
k2 ... > kmin（kmin 设为最小堆中最小元素）。继续遍历数列，每次遍历一个元素x，与堆顶元素比较，若x > kmin，则更新堆（x 入堆，用时O(logk)），否则不更新堆。这样下来，总费时O( k + k logk + (n-k)logk )= O(n logk)。此方法得益于在堆中，查找等各项操作的时间复杂度均为O(logk)。

当然，你也可以采用trie 树，关键字域存该查询串出现的次数，没有出现则为0，最后用10 个元素的最小堆来对出现频率进行排序。

 

3. 寻找频数最高的100 个词
有一个1G 大小的文件，里面每一行是一个词，词的大小不超过16 字节，内存限制大小是1M。返回频数最高的100 个词。
解法：
1.分而治之/hash 映射。按先后顺序读取文件，对于每个词x，执行hash(x)%5000，然后将该值存到5000个小文件（记为x0, x1, ..., x4999）中。如此每个文件的大小大概是200k 左右。当然，如果其中有的小文件超过了1M 大小，则可以按照类似的方法继续往下分，直到分解得到的小文件的大小都不超过1M。
2.hash_map 统计。对每个小文件，采用trie 树/hash_map 等统计每个文件中出现的词及相应的频率。
3.堆/归并排序。取出出现频率最大的100 个词（可以用含100 个结点的最小堆）后，再把100 个词及相应的频率存入文件，这样又得到了5000 个文件。最后把这5000 个文件进行归并（可以用归并排序）。

 

4. 寻找TOP 10
海量数据分布在100 台电脑中，请想个办法高效统计出这批数据的TOP 10。

解法一：如果同一个数据元素只出现在某一台机器中，那么可以采取以下步骤统计出现次数为TOP 10的数据元素。
1.堆排序。在每台电脑上求出TOP 10，可以采用包含10 个元素的堆完成（求TOP 10 小用最大堆，求TOP 10 大用最小堆，比如求TOP10 大，我们首先取前10 个元素调整成最小堆，假设这10 个元素就是TOP10 大，然后扫描后面的数据，并与堆顶元素比较，如果比堆顶元素大，那么用该元素替换堆顶，然后再调整为最小堆，否则不调整。最后堆中的元素就是TOP 10 大）。
2.组合归并。求出每台电脑上的TOP 10 后，然后把这100 台电脑上的TOP 10 组合起来，共1000 个数据，再利用上面类似的方法求出TOP 10 就可以了。

解法二：但如果同一个元素重复出现在不同的电脑中呢？举个例子，给定两台机器，第一台的数据及各自出现频率为：a(50)，b(50)，c(49)，d(49)，e(0)，f(0)，第二台的数据及各自出现频率为：a(0)，b(0)，c(49)，d(49)，e(50)，f(50)，求TOP 2。其中，括号里的数字代表某个数据出现的频率，如a(50)表示a 出现了50 次。
这个时候，有两种方法可以解决：
● 要么遍历一遍所有数据，重新hash 取模，如此使得同一个元素只出现在单独的一台电脑中，然后
采取上面所说的方法，统计每台电脑中各个元素的出现次数找出TOP 10，继而组合100 台电脑
上的TOP 10，找出最终的TOP 10。
● 要么暴力求解，直接统计每台电脑中各个元素的出现次数，然后把同一个元素在不同机器中的出
现次数相加，最终从所有数据中找出TOP 10。

 

5. 查询串的重新排列
有10 个文件，每个文件1G，每个文件的每一行存放的都是用户的query，每个文件的query 都可能重复。要求你按照query 的频度排序。
解法一：分为以下3 个步骤，如下：
1.hash 映射。顺序读取10 个文件，按照hash(query)%10 的结果将query 写入到另外10 个文件（记为a0,a1,..a9）中。这样新生成的每个文件的大小约为1G（假设hash 函数是随机的）。
2.hash_map 统计。找一台内存在2G 左右的机器，依次对用hash_map(query, query_count)来统计每个query 出现的次数。注：hash_map(query, query_count)是用来统计每个query 的出现次数，不是存储他们的值，出现一次，则count+1。
3.堆/快速/归并排序。利用快速/堆/归并排序按照出现次数进行排序，将排序好的query 和对应的query_cout 输出到文件中，这样得到了10 个排好序的文件（记为b0, b1, ..., b9）。最后，对这10 个文件进行归并排序（内排序与外排序相结合）。
解法二：一般query 的总量是有限的，只是重复的次数比较多而已，可能对于所有的query，一次性就可以加入到内存了。这样，我们就可以采用trie 树/hash_map 等直接来统计每个query 出现的次数，然后按出现次数做快速/堆/归并排序就可以了。
解法三：与解法1 类似，但在做完hash，分成多个文件后，可以交给多个文件来处理，采用分布式的
架构来处理（比如MapReduce），最后再进行合并。

 

总结：解决此类问题，一般步骤：

1、hash映射

2、采用trie 树/hash_map 等统计

3、堆/归并排序

 

转自：july-海量数据处理