共计 1678 个字符，预计需要花费 5 分钟才能阅读完成。
场景题
有 100 机器，每个机器的磁盘特地大，磁盘大小为 1T，然而内存大小只有 4G，当初每台机器上都产生了很多 ip 日志文件，每个文件假如有 50G，那么如果计算出这 100 太机器上访问量最多的 100 ip 呢？也就是 Top 100。
思路
其实，一开始我有往布隆过滤器那边思考，然而布隆过滤器只能大抵的判断一个 ip 是否曾经存在，而不能去统计数量，不合乎该场景。
那么个别这种大数据的问题，都是因为一次不能齐全加载到内存，因而须要拆分，那怎么拆呢？ip 是 32 位的，也就是最多就 232 个，常见的拆分办法都是 哈希：
- 把大文件通过哈希算法调配到不同的机器
- 把大文件通过哈希算法调配到不同的小文件
下面所说，一台机器的内存必定不能把所有的 ip 全副加载进去，必须在不同机器上先 hash 辨别，先看每台机器上，50G 文件，假如咱们分成 100 个小文件，那么均匀每个就 500M，应用 Hash 函数将所有的 ip 分流到不同的文件中。
这个时候雷同的 ip 肯定在雷同的文件中，当然不能排除数据全副歪斜于一个文件的状况，也就是尽管 hash 了，然而因为个别 ip 或者 hash 值雷同的 ip 太多了，都分到了个别文件上，那么这个时候分流后的文件仍旧很大。这种状况我能想到的就是要是文件还是很大，须要再 hash，如果根本属于同一个 ip，那么这个时候就能够分批次读取，比方一次只读 1G 到内存。
在解决每个小文件时，应用 HashMap 来统计每个 ip 呈现的频率，统计实现后，遍历，用最小根堆，获取呈现频率最大的 100 个 ip。这个时候，每个小文件都获取到了呈现频率最大的 100 个 ip，而后每个文件的 Top 100 个 ip 再进行 == 排序 == 即可（每个文件的 top100 都是不一样的，因为后面进行 hash 之后保障雷同的 ip 只会落到同一个文件里）。这样就能够失去每台机器上的 Top 100。
不同机器的 Top 100 再进行 加和 并 排序, 就能够失去 Top 100 的 ip。
为什么加和？因为不同机器上可能存在同样的 ip，后面的 hash 操作只是确保同一个机器的不同文件外面的 ip 肯定不一样。
然而下面的操作有什么瑕疵么？当然有！
假如咱们又两台机器，有一台机器 C1 的 top 100 的 ip 是 192.128.1.1，top 101 是 192.128.1.2, 那么就可能存在另一台机器 C2 上 192.128.1.1 可能素来没有呈现过，然而 192.128.1.2 却也排在 top 101, 其实总数上 192.128.1.2 是超过192.128.1.1，然而很可怜的是，咱们每台机器只保留了 top100，所以它在计算过程中被淘汰了，导致后果不精确。
解决方案：
先用 hash 算法，把 ip 依照 hash 值哈希到不同的机器上，保障雷同的 ip 在雷同的机器上，再对每个机器上的 ip 文件再 hash 成小文件，这个时候再别离统计小文件的呈现频次，用最小根堆解决，不同文件的后果排序，就能够失去每台机器的 top 100，再进行不同机器之间的后果排序，就能够失去真正的 top 100。
一般而言，像这种海量数据，比方 有一个蕴含 100 亿个 URL 的大文件, 假如每个 URL 占用 64B, 请找出其中所有反复的 URL. , 内存一次性读不下，只能通过 == 分而治之 ==。
hash 到不同的小文件，始终这样划分，直到满足资源的限度：
- hash 分流
- hash 表统计
- 最小堆 / 内部排序
如果容许肯定的误差存在，其实还能够思考应用布隆过滤器（Bloom filter）, 将 URL 挨个映射到每一个 Bit，在此之前判断该地位是否映射过，来证实它是否曾经存在。（有肯定的概率呈现误判，因为其余的 URL 也可能会映射到同一地位）
【作者简介】：
秦怀，公众号【秦怀杂货店 】作者，技术之路不在一时，山高水长，纵使迟缓，驰而不息。集体写作方向：Java 源码解析，JDBC，Mybatis，Spring，redis， 分布式 ， 剑指 Offer，LeetCode等，认真写好每一篇文章，不喜爱题目党，不喜爱花里胡哨，大多写系列文章，不能保障我写的都完全正确，然而我保障所写的均通过实际或者查找材料。脱漏或者谬误之处，还望斧正。
剑指 Offer 全副题解 PDF
2020 年我写了什么？
开源编程笔记
