海量数据处理

海量数据处理

海量日志数据

提取出某日访问百度次数最多的那个IP

分析：

IP是32位，IP地址最多有2^32=4G种取值情况，所以不能完全加载到内存中处理

解决：分治的思想

1. 按照IP地址的Hash(IP)%1024值，把海量IP日志分别存储到1024个小文件中
2. 对于每个文件，可以构建一个HashMap<IP,出现次数>,并且记录出现次数最多的那个IP地址
3. 然后对1024个文件出现最多次数的ip排序

搜索引擎会通过日志文件把用户每次检索使用的所有检索串都记录下来

假设目前有一千万个记录（这些查询串的重复度比较高，虽然总数是1千万，但如果除去重复后，不超过3百万个。一个查询串的重复度越高，说明查询它的用户越多，也就是越热门。），请你统计最热门的10个查询串，要求使用的内存不能超过1G。

解决：TOP K

1. 预处理：HashTable存储索引字符串，次数
2. 维护一个最小堆的数据结构（size为10），每次与堆顶（最小元素）作比较：
   2.1 如果比堆顶元素大，则删除堆顶元素，将本条数据加入堆后，调整最小堆
   2.2 小，继续；

文件中取出频率最高的100个词

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

解决：归并

1. 对于每个词进行hash存到5000个文件，每个文件大概200k
2. 每个文件(HashMap)统计频率，用100个节点的最小堆排序，得到频率最高的100个词
3. 将每个文件的100个词，再存入5000个文件
4. 5000个文件进行归并

两堆一样的很大的数据，

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

分文件+hash

1. a,b文件hash(url)%1000,分别分1000个文件
2. hash相同的一对文件才有可能出现相同的url，遍历比较时，可以先将一个文件的url存入hashset，然后遍历另外一个文件

在2.5亿个整数中找出不重复的整数

内存不足以容纳这2.5亿个整数。

分文件+归并

1. 分文件
2. 找出每个文件不重复的数字，并排序
3. 归并，去重

未排序过的、海量数据中查找

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

二进制+二分

1. 40亿的数换成2的32次方二进制数
2. 40亿个数分为两类：最高位0和最高位1，判断目标项的最高位，归于哪一批，进行下一步继续分。
3. 20亿文件继续分为两类：次高位0和次高位1，以此类推下去…

在海量数据中找出重复次数最多的一个

hash分文件，记录，排序

先做hash，然后求模映射为小文件，求出每个小文件中重复次数最多的一个，并记录重复次数。然后找出上一步求出的数据中重复次数最多的一个就是所求

上千万或上亿数据（有重复），统计其中出现次数最多的钱N个数据

记录+排序

1. HashMap/BST记录重复出现的次数
2. 堆排序取出前N个