Ton*_*y L 5 memory algorithm scalability
假设我有 1GB 可用内存，如何在这些 url 中找到重复项？
我在“破解编码面试”一书中看到了一个解决方案，它建议在第一次扫描时使用哈希表将这些 url 分成 4000 个文件 x.txt, x = hash(u)%4000。在第二次扫描中，我们可以单独检查每个 x.txt 文件中的重复项。
但是我如何保证每个文件会存储大约 1GB 的 url 数据？我认为某些文件有可能比其他文件存储更多的 url 数据。
我对这个问题的解决方案是迭代地实现文件分离技巧，直到文件小到足以容纳我可用的内存为止。
有没有其他方法可以做到？
如果您不介意需要更多代码的解决方案，您可以执行以下操作：
只计算哈希码。每个哈希码正好是 4 个字节，因此您可以完美控制每个哈希码块将占用的内存量。您还可以在内存中放入比 URL 多得多的哈希码，因此您将拥有更少的块。
找到重复的哈希码。据推测，它们将远少于 100 亿。它们甚至可能都适合内存。
再次浏览 URL，重新计算哈希码，查看 URL 是否具有重复的哈希码之一，然后比较实际的 URL 以排除由于哈希码冲突引起的误报。（有 100 亿个 url，而哈希码只有 40 亿个不同的值，将会有很多冲突。）