find-common-urls

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

题目描述

给定 a、b 两个文件，各存放 50 亿个 URL，每个 URL 各占 64B，内存限制是 4G。请找出 a、b 两个文件共同的 URL。

解答思路

1. 分治策略

每个 URL 占 64B，那么 50 亿个 URL 占用的空间大小约为 320GB。

5, 000, 000, 000 _ 64B ≈ 5GB _ 64 = 320GB

由于内存大小只有 4G，因此，我们不可能一次性把所有 URL 加载到内存中处理。对于这种类型的题目，一般采用分治策略，即：把一个文件中的 URL 按照某个特征划分为多个小文件，使得每个小文件大小不超过 4G，这样就可以把这个小文件读到内存中进行处理了。

思路如下：

首先遍历文件 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( i∈[0,999] )，把 URL 存储到一个 HashSet 集合中。然后遍历 b_i 中每个 URL，看在 HashSet 集合中是否存在，若存在，说明这就是共同的 URL，可以把这个 URL 保存到一个单独的文件中。

2. 前缀树

一般而言，URL 的长度差距不会不大，而且前面几个字符，绝大部分相同。这种情况下，非常适合使用字典树（trie tree） 这种数据结构来进行存储，降低存储成本的同时，提高查询效率。

由 @ChunelFeng 反馈。#212

方法总结

分治策略

1. 分而治之，进行哈希取余；
2. 对每个子文件进行 HashSet 统计。

前缀树

1. 利用字符串的公共前缀来降低存储成本，提高查询效率。