给定 100 亿 URL，每个 url 的平均长度为 100 个字符，请检查重复项
given 10 billion URL with average length 100 characters per each url, check duplicate
假设我有 1GB 可用内存，如何在 url 中找到重复项？
我在书上看到一个解决方案"Cracking the Coding Interview"，它建议使用哈希表将这些url分成4000个文件x.txt，x = hash( u)%4000 在第一次扫描中。在第二次扫描中，我们可以检查每个 x.txt 个单独文件中的重复项。
但是我如何保证每个文件存储大约 1GB url 数据？我认为有些文件可能会比其他文件存储更多 url 数据。
我对这个问题的解决方案是反复实施文件分离技巧，直到文件小到足以容纳我可用的内存为止。
还有其他方法吗？
评论有点长
事实是，您不能保证文件会小于 1 GB。我不确定这 4,000 是从哪里来的。总数据量约为 1,000 GB，因此平均文件大小为 250 MB。
您的尺寸不太可能偏离 4 倍。当然，这是可能的。在这种情况下，只需将文件再次拆分为少数其他文件即可。这增加了微不足道的复杂性。
这没有说明的是一个简单的案例。如果其中一个 URL 的长度为 100 并且在数据中出现了 10,000,000 次怎么办？哎哟!在这种情况下，您需要读取一个文件，然后 "reduce" 通过将每个值与一个计数相结合来读取它。
如果您不介意需要更多代码的解决方案，您可以执行以下操作：
只计算哈希码。每个哈希码恰好是 4 个字节，因此您可以完美控制每个哈希码块将占用的内存量。您还可以在内存中容纳比 URL 多得多的哈希码，因此您将拥有更少的块。
找到重复的哈希码。据推测，它们将远少于 100 亿。它们甚至可能都适合记忆。
再次检查 URLs，重新计算哈希码，查看 URL 是否有重复的哈希码之一，然后比较实际的 URLs排除由于哈希码冲突导致的误报。 （有 100 亿个 url，哈希码只有 40 亿个不同的值，将会有很多冲突。）
假设我有 1GB 可用内存，如何在 url 中找到重复项？
我在书上看到一个解决方案"Cracking the Coding Interview"，它建议使用哈希表将这些url分成4000个文件x.txt，x = hash( u)%4000 在第一次扫描中。在第二次扫描中，我们可以检查每个 x.txt 个单独文件中的重复项。
但是我如何保证每个文件存储大约 1GB url 数据？我认为有些文件可能会比其他文件存储更多 url 数据。
我对这个问题的解决方案是反复实施文件分离技巧，直到文件小到足以容纳我可用的内存为止。
还有其他方法吗？
评论有点长
事实是，您不能保证文件会小于 1 GB。我不确定这 4,000 是从哪里来的。总数据量约为 1,000 GB，因此平均文件大小为 250 MB。
您的尺寸不太可能偏离 4 倍。当然，这是可能的。在这种情况下，只需将文件再次拆分为少数其他文件即可。这增加了微不足道的复杂性。
这没有说明的是一个简单的案例。如果其中一个 URL 的长度为 100 并且在数据中出现了 10,000,000 次怎么办？哎哟!在这种情况下，您需要读取一个文件，然后 "reduce" 通过将每个值与一个计数相结合来读取它。
如果您不介意需要更多代码的解决方案，您可以执行以下操作：
只计算哈希码。每个哈希码恰好是 4 个字节，因此您可以完美控制每个哈希码块将占用的内存量。您还可以在内存中容纳比 URL 多得多的哈希码，因此您将拥有更少的块。
找到重复的哈希码。据推测，它们将远少于 100 亿。它们甚至可能都适合记忆。
再次检查 URLs，重新计算哈希码，查看 URL 是否有重复的哈希码之一，然后比较实际的 URLs排除由于哈希码冲突导致的误报。 （有 100 亿个 url，哈希码只有 40 亿个不同的值，将会有很多冲突。）