利用分治思想可以解决许多面试常见的设计题。
问一：有一个文件，里面存放着大量的 url，文件很大以至于无法完全加载进内存，
要求找出其中重复出现的 url。
如果文件不大，我们肯定会创建一个 HashSet，依次遍历 url，如果它没出现在 HashSet 中就将其加入，
否则我们就找到了一个重复的 url。其实，我们现在也可继续用 Hash 的方法，不同的是现在要在磁盘上作 Hash。
我们把所有的 url Hash 到若干个小文件中去，每个小文件其实就相当于内存 HashSet 的一个槽。
因为哈希碰撞的存在，几乎每个小文件中都有不止一个 url，同一个小文件中的 url 未必都相同，但重复的 url 一定会被 Hash 到同一个小文件中去。
接下来，如果这个小文件足够小，我们可以把它加载到内存中去查重，否则可以递归地进行磁盘 Hash。
这里其实就是利用了分治的思想，把一个大规模问题分解成了一些小规模问题。
问二：有一个文件，里面存放着大量的 IP，文件很大以至于无法完全加载进内存，
要求对于每个查询请求，尽快判断待查 IP 是否存在于文件中。
这也是一个典型的用 HashSet 就能轻松完成的任务。我们可以同样地作磁盘 Hash，对于每个待查 IP 作 Hash，
定位到特定的小文件（磁盘 HashSet 的槽），再在小文件中查找。或者，我们可以把 IP 看成是一个 32bit 长的整数，
我们可以直接在内存中实现 bitset，bitset 大小仅有 2^32bit = 512MB，对于某个 IP 对应的 4 字节整数 x，
我们把 bitset 的第 x 位设为 1 以表示它的存在。倘若 512MB 的内存都给不起，我们还可尝试把 bitset 放在磁盘上，
每次查询需要一次随机 IO 读。
问三：有一个文件，里面存放着大量的 IP，文件很大以至于无法完全加载进内存，
要求对于每个查询请求，尽快判断待查 IP 在文件中的出现次数是否大于 2。
这是“问二”的变种，我们用变种的 bitset 来解决。现在每个 IP 对应的 4 字节整数 x 占用 bitset 中的第 x*2 与第 x*2+1 位，
这两位有四种状态，我们用“00”表示不存在，用“01”表示出现一次，“10”表示出现两次，“11”表示两次以上。剩下的同理。
问四：有一个文件，里面存放着大量的长整数，文件很大以至于无法完全加载进内存， 要求对其中所有长整数排序。
这种外部排序问题通常用归并排序解决。把大文件任意切分成若干个可以加载进内存的小文件，
在内存中对小文件中的长整数进行排序并输出为新的小文件。接下来我们可以递归地两两合并排序的小文件，
或者利用堆来一次性合并所有的小文件。注意合并操作只关心各个有序序列的头部，所以我们同时只需要加载各个有序小文件的一部分即可，
IO 输入流可以应对这一场景，排序结果也可利用 IO 输出流顺序地写入一个新的大文件。
问五：有一个文件，里面存放着大量的 url，文件很大以至于无法完全加载进内存，
要求找出其中重复出现次数最多的 K 个 url。
首先我们可以效仿“问一”的解答，利用磁盘 Hash 完成 url 计数，然后就可以得到一个包含“频数-url”键值对的大文件。
接下来就是一个超大文件 top K 的问题，它与常规的内存 top K 问题没有太大区别，我们在内存中建立一个大小为 K 的最小堆，
遍历数据用 IO 输入流进行。
思考题：有两个文件，各自存放着大量的 url，文件很大以至于无法完全加载进内存，
求两个文件的交集。
提示：分别作磁盘 Hash。
推荐阅读：
如果你喜欢我的文章，请我吃根冰棒吧 (o゜▽゜)o ☆
最后附上 GitHub：https://github.com/gonearewe
