如何从大量的 URL 中找出相同的 URL？

题目描述

有两个很大的文件a和b，内存有限，找到a b中相同的URL。

解决方案1

首先遍历文件 a，对遍历到的 URL 求 hash(URL) % 1000 ，根据计算结果把遍历到的 URL 存储到 a, a, a, …, a，这样每个大小约为 300MB。使用同样的方法遍历文件 b，把文件 b 中的 URL 分别存储到文件 b, b, b, …, b 中。这样处理过后，所有可能相同的 URL 都在对应的小文件中，即 a 对应 b, …, a 对应 b，不对应的小文件不可能有相同的 URL。那么接下来，我们只需要求出这 1000 对小文件中相同的 URL 就好了。
接着遍历 a( i∈[0,999] )，把 URL 存储到一个 HashSet 集合中。然后遍历 b 中每个 URL，看在 HashSet 集合中是否存在，若存在，说明这就是共同的 URL，可以把这个 URL 保存到一个单独的文件中。

这种方案能解决，但效率较低

解决方案2

用一个很大的布隆过滤器，然后a中URL进行多次hash后，放入布隆过滤器中；接着遍历b中的URL，如果多次hash的结果都是1，那么就认为这个URL是相同的。

这种方式效率更高，但是存在误判的可能，并且受限于数据量

如何从大量数据中找出高频词？

题目描述

有一个 1GB 大小的文件，文件里每一行是一个词，每个词的大小不超过 16B，内存大小限制是 1MB，要求返回频数最高的 100 个词(Top 100)。

解决方案

首先遍历大文件，对遍历到的每个词x，执行 hash(x) % 5000 ，将结果为 i 的词存放到文件 a 中。遍历结束后，我们可以得到 5000 个小文件。每个小文件的大小为 200KB 左右。如果有的小文件大小仍然超过 1MB，则采用同样的方式继续进行分解。
接着统计每个小文件中出现频数最高的 100 个词。最简单的方式是使用 HashMap 来实现。其中 key 为词，value 为该词出现的频率。具体方法是：对于遍历到的词 x，如果在 map 中不存在，则执行 map.put(x, 1) ；若存在，则执行 map.put(x, map.get(x)+1) ，将该词频数加 1。
上面我们统计了每个小文件单词出现的频数。接下来，我们可以通过维护一个小顶堆来找出所有词中出现频数最高的 100 个。具体方法是：依次遍历每个小文件，构建一个小顶堆，堆大小为 100。如果遍历到的词的出现次数大于堆顶词的出现次数，则用新词替换堆顶的词，然后重新调整为小顶堆，遍历结束后，小顶堆上的词就是出现频数最高的 100 个词。