674-求两个文件中的QQ交集

妖狐艹你老母 2022-08-28 06:46 172阅读 0赞

**A文件有30亿个QQ号码，B文件有40亿个QQ号码，求A文件和B文件中QQ号码的交集，内存大小限制为1GB**

## 一. 直接暴力比较 ##

最简单的方法是直接暴力比较，如下：  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16]  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 1]  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 2]  
显然，这种方法要比较的次数是：30亿\*40亿，时间复杂度太大了

## 二. 利用hashmap ##

既然时间复杂度不符合要求，那就要反思一下暴力比较的算法了，显然，应该用哈希表，优化查找速度，如下：  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 3]

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 4]  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 5]  
显然，时间复杂度大大降低，只需要遍历上面一层即可。然而，空间的占用还是太大了，1GB的内存根本无法容纳40亿个QQ号。

## 三. 分治切割文件 ##

既然内存容纳不下，那就想办法进行切割吧，比如：根据QQ号码的最后一位的值来切割A文件和B文件，使文件变小。显然，尾数为j的QQ号码只可能在Aj文件和Bj文件中，只需要比较Aj和Bj文件即可。  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 6]  
通过切割的方法，可以化大为小，让内存容纳得下，对应的图示如下：

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 7]  
需要强调的是，仅仅以QQ号最后一位来划分，那么每个小文件的数据量大约是原来文件的1/10, 可能还是偏大，怎么办？  
可以考虑以QQ号的最后3位来划分，那么每个小文件的数据量大约是原来大文件的1/1000，甚至还可以更细地来进行划分。  
通过一定的规则进行分割，把A文件和B文件中同类型数据划分到对应的小文件中，解决了内存问题

## 四. 利用bitmap ##

我们回头看一下，要么是时间不符合要求，要么是空间不符合要求，那有没有时间和空间都符合要求的数据结构呢？  
显然有的！我们可以对hashmap进行优化，采用bitmap这种数据结构，可以顺利地同时解决时间问题和空间问题。  
在很多实际项目中，bitmap经常用到。我看了不少组件的源码，发现很多地方都有bitmap实现，bitmap图解如下：  
![在这里插入图片描述][21786c1045014bce8f3441cbd34b5622.png]  
这是一个unsigned char类型，可以看到，共有8位，取值范围是\[0, 255\]，如上这个unsigned char的值是255，它能标识0~7这些数字都存在。

同理，如下这个unsigned char类型的值是254，它对应的含义是：1~7这些数字存在，而数字0不存在：  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 8]  
由此可见，一个unsigned char类型的数据，可以标识0~7这8个整数的存在与否。以此类推：

一个unsigned int类型数据可以标识0~31这32个整数的存在与否。

两个unsigned int类型数据可以标识0~63这64个整数的存在与否。

显然，可以推导出来：512MB大小足够标识所有QQ号码的存在与否，请注意：QQ号码的理论最大值为2^32 - 1，大概是43亿左右。接下来的问题就很简单了：  
用512MB的unsigned int数组来记录B文件中QQ号码的存在与否，形成一个bitmap. 然后遍历A文件中的QQ, 看是否在bitmap中，如果在，那么该QQ号码就同时存在于A和B两个文件中。

[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16]: /images/20220828/a43bfe5fb4194ea381632ea7347fdc85.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 1]: /images/20220828/be5f24a09444438e8055ae30f92e1598.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 2]: /images/20220828/a3adeb478972411493bf0f770e0335da.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 3]: /images/20220828/a976c0aac2aa454693c6b04560ec5461.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 4]: /images/20220828/fdab03d4464645e78761a395ded968bd.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 5]: /images/20220828/a8e7045787954234be1c72c4d92ee875.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 6]: /images/20220828/7632be3c8e694c1d84dfc0d51ae1043d.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 7]: /images/20220828/1639308a0bdc4f28aa8899691197df16.png
[21786c1045014bce8f3441cbd34b5622.png]: /images/20220828/3a7018b834e9425d87ae4d9743a22433.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 8]: /images/20220828/b4a495d45dcb4061ad7d46a2df373ee0.png