algorithm - 给定 100 亿个 URL，每个 URL 的平均长度为 100 个字符，检查是否重复

Question

假设我有 1GB 可用内存，如何在这些 url 中找到重复项？

我在《Cracking the Coding Interview》这本书上看到一个解决方案，它建议使用hashtable将这些url分成4000个文件x.txt，x = hash(u)%4000在初次扫描。在第二次扫描中，我们可以检查每个 x.txt 单独文件中的重复项。

但是我如何保证每个文件存储大约 1GB 的 url 数据呢？我认为有些文件可能会比其他文件存储更多的 url 数据。

我对这个问题的解决方案是反复实现文件分离技巧，直到文件小到足以容纳我可用的内存为止。

还有其他方法吗？

Answer 1

如果您不介意需要更多代码的解决方案，您可以执行以下操作:

1. 仅计算哈希码。每个哈希码恰好是 4 个字节，因此您可以完美控制每个哈希码 block 将占用的内存量。您还可以在内存中容纳比 URL 更多的哈希码，因此您将拥有更少的 block 。

2. 找到重复的哈希码。据推测，它们将远少于 100 亿。它们甚至可能都适合内存。

3. 再次检查 URL，重新计算哈希码，查看 URL 是否具有重复的哈希码之一，然后比较实际的 URL 以排除由于哈希码冲突导致的误报。 (有 100 亿个 url，哈希码只有 40 亿个不同的值，将会有很多冲突。)