面试题-海量数据处理题

问题一:给你A,B两个文件,各存放50亿条URL,每条URL占用64字节,内存限制是4G,让你找出A,B文件共同的URL。如果是三个乃至n个文件呢?

方案:

先算一下4G有多少位(bit),4G = 2^32 * 8 bit = 320亿 bit,n才50亿,可以用位图法。将其中一个文件中的url使用Bloom filter映射为这340亿bit,然后挨个读取另外一个文件的url,检查是否与Bloom filter,如果是,那么该url应该是共同的url(注意会有一定的错误率)。

如果是3个或多个呢?2-bitmap或者两两查找。

参考链接:https://juejin.im/entry/5a27cb796fb9a045104a5e8c

原文地址:https://www.cnblogs.com/lfri/p/12426489.html