A、 B 文件中各存放50亿条URL，每条URL占用64字节

[单选题]

A、 B 文件中各存放50亿条URL，每条URL占用64字节，在内存限制是4G的情况下，以下哪种方法能够找到A、B文件之间的重复URL（）

```
哈希表
```
```
布隆过滤器
```
```
字典树
```
```
红黑树
```

查看正确选项

Nickqiao

可以估计每个文件的大小为 5G*64=300G ，远大于 4G 。所以不可能将其完全加载到内存中处理。考虑采取分而治之的方法。
遍历文件 a ，对每个 url 求取 hash(url)%1000 ，然后根据所得值将 url 分别存储到 1000 个小文件（设为 a0,a1,...a999 ）当中。这样每个小文件的大小约为 300M 。遍历文件 b ，采取和 a 相同的方法将 url 分别存储到 1000 个小文件 (b0,b1....b999) 中。这样处理后，所有可能相同的 url 都在对应的小文件 (a0 vs b0, a1 vs b1....a999 vs b999) 当中，不对应的小文件（比如 a0 vs b99 ）不可能有相同的 url 。然后我们只要求出 1000 对小文件中相同的 url 即可。
比如对于 a0 vs b0 ，我们可以遍历 a0 ，将其中的 url 存储到 hash_map 当中。然后遍历 b0 ，如果 url 在 hash_map 中，则说明此 url 在 a 和 b 中同时存在，保存到文件中即可。
如果分成的小文件不均匀，导致有些小文件太大（比如大于 2G ），可以考虑将这些太大的小文件再按类似的方法分成小小文件即可

发表于 2017-03-18 12:19:20 回复(1)