假设有一个3TB的TXT文件,其中每一行都是一个字符串,如何在其中找到那些重复的字符串？这是我朋友的采访问题.在接下来的一次采访中,我们最好让这些问题足够清楚.
PS:如果我是受访者,我会告诉采访者:你们怎么能在TXT文件中存储这么多字符串？这真是个坏主意!
一种可能性是使用布隆过滤器.
布隆过滤器很快(如使用哈希码)并且没有错误否定.它也非常节省空间.可以调整各种参数(大小(m)和函数数量(k))以便以大小和时间为代价实现更好的误报率.
您将所有字符串逐个添加到过滤器所代表的集合中.在插入时,您可以确定是否存在重复项.由于它没有漏报,因此您只需要仔细检查过滤器出现的"重复"字符串.
如果您想了解有关Bloom过滤器的更多信息,请访问维基百科
这是解决此问题的最佳方法.代理服务器使用Bloom过滤器来确定URL是否在其缓存中.代理服务器看到数十亿个URL,并且需要能够非常快速地告知URL是新的还是以前被"看到"的.如果URL是"新",则代理服务器立即从原始URL中提取网站,而不是在其缓存中查找.
这里的所有其他答案,甚至远程使用"排序"显然是错误的.