场景题有100台机器，每台机器的磁盘空间都很大。磁盘大小为1T，但内存大小只有4G。现在每台机器都会生成很多ip日志文件，假设每个文件有50G。如果计算这100台机器上访问次数最多的100个IP呢？也就是Top100。其实一开始我也想到了Bloomfilter，但是Bloomfilter只能粗略判断一个IP是否已经存在，而不能统计数量，不符合场景。那么一般这种大数据的问题是因为不能一次全部加载到内存中，所以需要拆分，那么怎么拆分呢？ip是32位的，也就是最多232个。常见的拆分方式是hash：通过hash算法将大文件分布到不同的机器上，通过hash算法将大文件分布到不同的小文件中。也就是说，一台机器的内存一定不能把所有的IP都加载进去。必须在不同的机器上通过hash来区分。首先看每台机器上的50G文件。假设我们把它们分成100个小文件，那么平均每个是500M，使用Hash函数将所有ip分流到不同的文件中。这时候同一个ip肯定是同一个文件。当然，也不排除数据全部倾向于一个文件。也就是虽然hash是散列的，但是因为单独的ip或者hash值相同的ip太多了，所以都被分成了单独的文件，那么此时分流后的文件还是很大的。这种情况下我能想到的是，如果文件还是很大的话，需要重新哈希一下。如果基本属于同一个ip，那么此时可以分批读取，比如一次只能读取1G到内存中。在处理每个小文件时，使用HashMap统计每个IP的出现频率。统计完成后，遍历使用最小的根堆，得到出现频率最高的100个IP。这时候每个小文件都拿到了频率最高的100个ips，然后可以对每个文件的前100个ips进行==排序==（每个文件的top100不一样，因为之前的hash后是保证同一个ip只会落入同一个文件）。这样就可以得到每台机器上的Top100。可以对不同机器的top100进行求和排序，得到top100的ip。为什么要求和？因为同一个ip可能存在于不同的机器上，前面的hash操作只是保证了同一台机器上不同文件中的ip一定是不同的。但是上面的操作有没有漏洞呢？当然有！假设我们有两台机器，一台机器C1的top100ip是192.128.1.1，top101是192.128.1.2，那么可能还有一台机器C2其中192.128.1.1可能永远不会出现，而是192.128。1.2也排在top101，其实192.128.1.2的总数比192.128.1.1多，可惜我们只保存了每台机器的top100，所以在计算过程中剔除了，导致结果不准确.解决方法：先用hash算法把ip根据hash值散列到不同的机器上，保证同一个ip在同一台机器上，然后把每台机器上的ip文件散列成小文件，这时候再分开统计小文件的出现频率，用最小根堆处理，对不同文件的结果进行排序，可以得到每台机器的top100，再对不同机器的结果进行排序，可以得到真正的top100.一般来说，对于这种海量数据，比如有一个包含100亿个URL的大文件，假设每个URL占用64B，请找出其中所有重复的URL。内存不能一次性读取，只能通过==分而治之==来读取。Hash到不同的小文件，一直这样划分，直到满足资源限制：hash分流哈希表统计最小堆/外部排序如果允许一定的错误，其实可以考虑使用布隆过滤器（Bloomfilter）来转换URL逐一映射到每个Bit，判断该位置之前是否映射过，证明是否已经存在。（有一定的误判概率，因为其他网址也可能映射到同一个位置）【作者简介】：秦淮，公众号【秦淮杂货店】的作者，技术之路不是一蹴而就的，山高水长，再慢也不会停下脚步。个人写作方向：Java源码分析、JDBC、Mybatis、Spring、redis、分布式、简知Offer、LeetCode等，认真写好每篇文章，不喜欢头条党，不喜欢花里胡哨，多写系列的文章，不保证我写的是完全正确的，但我保证我写的是经过实践或搜索过的资料。如有遗漏或错误，敬请指正。剑指提供所有问答PDF2020年我写了什么？开源编程笔记
