![](https://csdnimg.cn/release/download_crawler_static/10618286/bg4.jpg)
出频率最大的几个)及相应的频率。然后再在这 1000 个最大的 IP 中,找出那个频率最大的 IP,即为所求。”--
十道海量数据处理面试题与十个方法大总结。
关于本题,还有几个问题,如下:
1、Hash 取模是一种等价映射,不会存在同一个元素分散到不同小文件中去的情况,
即这里采用的是 mod1000 算法,那么相同的 IP 在 hash 后,只可能落在同一个文件中,不
可能被分散的。
2、那到底什么是 hash 映射呢?简单来说,就是为了便于计算机在有限的内存中处理
big 数据,从而通过一种映射散列的方式让数据均匀分布在对应的内存位置(如大数据通过取
余的方式映射成小树存放在内存中,或大文件映射成多个小文件),而这个映射散列方式便
是我们通常所说的 hash 函数,设计的好的 hash 函数能让数据均匀分布而减少冲突。尽管
数据映射到了另外一些不同的位置,但数据还是原来的数据,只是代替和表示这些原始数据
的形式发生了变化而已。
此外,有一朋友 quicktest 用 python 语言实践测试了下本题,地址如下:
http://blog.csdn.net/quicktest/article/details/7453189。谢谢。OK,有兴趣的,还可以再了解
下一致性 hash 算法,见 blog 内此文第五部分:
http://blog.csdn.net/v_july_v/article/details/6879101。
2、寻找热门查询:搜索引擎会通过日志文件把用户每次检索使用的所有检索串都记录下来,
每个查询串的长度为 1-255 字节。
假设目前有一千万个记录(这些查询串的重复度比较高,虽然总数是 1 千万,但如果除
去重复后,不超过 3 百万个。一个查询串的重复度越高,说明查询它的用户越多,也就是
越热门),请你统计最热门的 10 个查询串,要求使用的内存不能超过 1G。
由上面第 1 题,我们知道,数据大则划为小的,但如果数据规模比较小,能一次性装入
内存呢?比如这第 2 题,虽然有一千万个 Query,但是由于重复度比较高,因此事实上只有
300 万的 Query,每个 Query255Byte,因此我们可以考虑把他们都放进内存中去,而现在
只是需要一个合适的数据结构,在这里,Hash Table 绝对是我们优先的选择。所以我们放
弃分而治之/hash 映射的步骤,直接上 hash 统计,然后排序。So,
1. hash 统计:先对这批海量数据预处理(维护一个 Key 为 Query 字串,Value 为该
Query 出现次数的 HashTable,即 hash_map(Query,Value),每次读取一个
Query,如果该字串不在 Table 中,那么加入该字串,并且将 Value 值设为 1;