c# - 3TB TXT 文件中的重复字符串

Question

假设有一个 3TB 的 TXT 文件，其中每一行都是一个字符串，如何找到其中重复的字符串？这是我一个 friend 的面试题。我们最好在面试后把这些问题弄清楚，以防下次面试。

PS:如果我是面试官，我会跟面试官说:你们一个TXT文件怎么存那么多字符串？这真是个坏主意!

Answer 1

一种可能是使用布隆过滤器。

布隆过滤器速度很快(就像使用哈希码一样)并且没有漏报。它也非常节省空间。可以调整各种参数(大小 (m) 和函数数量 (k))，以牺牲大小和时间为代价实现更好的误报率。

您将所有字符串一个一个地添加到过滤器表示的集合中。在插入时，您可以确定是否存在重复项。由于它没有漏报，您只需仔细检查过滤器出现的“重复”字符串。

如果您想了解有关 Bloom 过滤器的更多信息，请转至 wikipedia

这是迄今为止解决此问题的最佳方法。代理服务器使用布隆过滤器来确定 URL 是否在其缓存中。代理服务器会看到数十亿个 URL，并且需要能够非常快速地判断一个 URL 是新的还是以前被它“看到”过。如果 URL 是“新的”，则代理服务器会立即从原始 URL 获取网站，而不是在其缓存中查找。

此处所有其他甚至远程使用“排序”的答案显然都是错误的。