海量数据处理：找出相同的URL
今天做了一下字节青训营的后端笔试，遇到一道经典问题。
题目
给定a、b两个文件，各存放50亿个url，每个url各占64字节，内存限制是4G，找出a、b文件共同的url？
自己的思路
对于这类问题，一般都会使用到位值表示来存储数据，还有就是使用Hash等一系列算法，将url内容映射到位值路径中。先将a文件进行读取，过一遍Hash算法，将得到的数据位置置为1，最终得到一个数据空间。然后读取b文件夹中的每一个url，将url进行hash计算得出位值，查找数据空间的位值是否为1，如果为1，则为相同的url，输出这条记录。
位值表示
一般来说，我们存储数字都是用int，而int有4字节大小，即32位大小。毫无疑问，这种方式是及其浪费空间的，尤其是在内存特别小的情况下。这情况下，我们使用位值存储，1——>00000001,0------->00000000,8-->00001000,使用这样进行记录可以更加节省空间。
网上的参考
方案一
- 将每个文件分成较小的块，每个块包含一部分url。每个块的大小应该小于等于可用内存的大小，以确保可以同时加载两个块到内存中。
- 遍历文件a的所有块，并将每个块加载到内存中。使用哈希集合（hash set）来存储当前块中的所有url。
- 遍历文件b的所有块，并将每个块加载到内存中。对于每个加载的块，遍历其中的url，并与文件a的哈希集合进行比较。如果找到共同的url，将其保存到结果集中。
- 重复步骤3，直到遍历完文件b的所有块。
- 完成遍历后，得到的结果集即为文件a和文件b共同的url。
优化
- 对于每个块，为了保证比较的准确性，可能需要进行排序操作。可以使用外部排序算法来对块进行排序。
- 为了简化实现和提高效率，可以使用布隆过滤器来过滤掉一些不可能匹配的url，减少哈希集合的大小和比较次数。(但布隆过滤器存在一定的误判率)
方案二（分治法+哈希取模）
和第一种类似
分析
50亿URL，每个64字节。如果要一次读入内存，需要50亿x64字节÷ 2^30≈300G，不能一次加入只有4G的内存中。我们假设将每个文件分割为1000个小文件（当然，可以更大或更小），小文件大概为300M，4G内存可以加载多个小文件。
步骤
- 要划分文件大小，不能简单划分，否则小文件读取不到相同的URL。我们使用相同的哈希函数将url分解为1000个哈希值相同的小文件。（即哈希值范围为0-999）
- 对于这种划分来说，哈希值相同url必然存在于序号相同的文件中，只需要对两个序号相同的文件进行url的相互匹配就能找到。
- 对于两个序号相同的小文件，我们可以把a_n为文件的url放到hash_set中，再放入b_n的url，利用set元素唯一的特性，对于不能存放的url进行输出，即为相同的URL。
总结
这类问题，本质都是一个信息压缩和在抽取的问题，我们一般都能使用hash+分治将问题规模变小来进行处理。大致思路是这样，但实际在构建过程中，我们可以使用不同的数据结构如布隆过滤器等进行优化。